ArrayList与LinkedList

ArrayList底层数据结构为名为elementData的Object数组,它实现了List接口，
继承了 实现了List接口 的抽象类 AbstractList,
实现了RandomAccess：支持快速随机访问，根据下标获取元素。
Cloneable:可以使用Object.Clone方法。
Serializable:可以进行序列化和反序列化。

1.ArrayList默认长度为10，最大长度为 Integer.MAX_VALUE - 8。

//==============================
2.ArrayList有三种构造方法，一个无参和两个有参，无参构造方法在调用时并不会设置容量为10，而是在有add操作时才会设置容量。有参方法，一个是指定容量大小的，一个是传入 Collection<? extend E> c ，第一步elementData获得c的地址，第二步判断elementData的长度，如果大于0，构造方法会将其用Arrays.copyof(目标数组，被返回副本的长度，被返回副本的类型)深拷贝存进elementData，如果等于0，则elementData将成为默认的容量为0的数组。

//==============================
3.扩容为1.5倍扩容，维护一个minarray_size和一个maxarray_size，每次有add相关的操作时，minarray_size都会被设置为当前ArrayList.size()+1,当minarray_size大于容量时会通过grow()方法进行扩容，当需要的最小容量大于了 Integer.MAX_VALUE - 8，那么ArrayList的容量将被直接设置为Integer.MAX_VALUE。

//==============================
4.add或remove时都是基于下标操作的，每次改动ArrayList时，都会调用***System.copy(原数组，起始位置，新数组，起始位置，操作元素个数)***方法，将需要移动位置的所有元素进行移位操作，并且使size加或减，再使结构改动计数modCount增加。
//==============================
5.list1.retainAll(Collection<?> c),list1.retainAll(list.2)，从List1中删除不在list2/不是c的元素。
//==============================
6.进行删除替换操作的时候，方法是有返回值的，返回值为被删除/替换的元素。
//==============================
7.因为arrayList实现了RandomAccess，根据下标访问，所以遍历时尽量用for循环。
//==============================
8.clear方法是for循环从前往后遍历所有元素，将它们全置为null，并且设置size=0。

//======================================
//======================================
//======================================
***LinkedList***底层为一个双向链表，

实现了List接口可以有队列的操作，
实现了Deque接口有双端队列操作，
实现了Cloneable可用Object.clone()，
实现了Serializable可以进行序列化和反序列化。

1.插入替换删除都要用到LinkedList的查找方法node(int index)，node方法有个折半查询的优化，index小于当前链表中元素的一半，就从前往后遍历，否则就从后往前。

2.增删查改在源码中除了默认的尾插、getFirst、getLast、remove(Object o)之外，其他情况均是要用到索引 index 的。

3.增删的操作都是双向的，需要改变前后节点的关系，所以每次都得有引用来记录目标节点前后节点。每次结构性改动，都会使结构改动计数modCount增加。

3.LinkedList的toArray()方法是新建一个大小为链表size的Object[]。

4.clear方法是从前往后遍历，将每一个节点的前后引用和元素都置为null,使size=0。

5.进行删除替换操作的时候，方法是有返回值的，返回值为被删除/替换的元素。

//===============================================================================================

总结其区别就是，ArrayList底层是数组，LinkedList是双向链表，改查操作ArrayList更快(RandomAccess优势)，增删操作LinkedList更快(Deque优势)。

本文地址：https://blog.csdn.net/rushrush1/article/details/107691536