稍微有点常识的都知道，这两个类底层的数据结构一个是数组一个是链表，数组和链表的优缺点学过数据结构的都知道，这是最基础的知识了，面试官却喜欢反复问起来，那肯定是想听点不一样的，我们今天就巴拉巴拉这两个类到底有啥区别。
ArrayList
先说总结，ArrayList底层是一个数组，可以根据索引快速访问数据，效率比较高(但是查找一个特定数据还是要遍历)，插入删除数据需要进行数据移动，效率较低；数组初始容量为10(延迟初始化)，容量不够时会扩容到1.5倍大小(申请一块儿新内存，然后把数据拷贝到新内存)。
我们先看下源码并不长，所以直接从源码看几个关键函数的实现。
初始化
可以看到ArrayList有三个构造函数：
public ArrayList()
public ArrayList(int initialCapacity)
public ArrayList(Collection<? extends E> c)
第一个默认构造函数在jdk7上面默认初始化数组长度为10，但是在jdk8上面做了优化，默认数组为空，第一次插入数据时才初始化素组长度为10，最后有源码链接。
第二个构造函数根据参数声明数组的长度。
第三个构造函数是直接参数的数据拷贝到数组。
插入数据和扩容
插入数据很简单，就是先检查数组长度，够的话就直接插入数据(插入到最后或者移动数据后插入到对应位置)，不够的话就申请新空间，长度为当前的1.5倍。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
访问数据
根据索引访问数据就是直接访问数组的第几个数据，如果查找指定数据是直接遍历数组。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
序列化
在源码中可以看到数组是被transient修饰的，意思是这个变量不会被序列化。可是ArrayList明明是集成Serializable接口的，如果数据数组不能被序列化这个类被序列化也没意义了。我们在后面发现了writeObject()、readObject()两个函数，而这两个函数则是实现序列化和反序列化的。因为数组可能申请的空间比较大，而实际存储的数据比较少，用系统默认的序列化就会浪费空间，所以自己实现了序列化。
transient Object[] elementData;
private void writeObject(java.io.ObjectOutputStream s)
private void readObject(java.io.ObjectInputStream s)
LinkedList
LinkedList是个双向循环链表，在jdk7中取消了循环，实现了队列接口，可以当做栈、队列、双向队列使用。它插入删除数据时只做指针修改，所以效率比较高，但是根据索引查询时需要遍历，相比较ArrayList效率比较低。
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
注意：源码基于android API 28对应的open SDK
在线源码: http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/8deef18bb749/src/share/classes/java/util/ArrayList.java
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/ArrayList.java
网友评论