共计 4315 个字符，预计需要花费 11 分钟才能阅读完成。
前言
明天介绍一下 Java 的两个汇合类，ArrayList 和 LinkedList，这两个汇合的知识点简直能够说面试必问的。
对于这两个汇合类，置信大家都不生疏，ArrayList 能够说是日常开发中用的最多的工具类了，也是面试中简直必问的，LinkedList 可能用的少点，但大多数的面试也会有所波及，尤其是对于这两者的比拟能够说是粗茶淡饭，所以，无论从应用上还是在面试的筹备上，对于这两个类的知识点咱们都要有足够的理解。
ArrayList
ArrayList 是 List 接口的一个实现类，底层是基于数组实现的存储构造，能够用于装载数据，数据都是寄存到一个数组变量中，
transient Object[] elementData;transient 是一个关键字，它的作用能够总结为一句话：将不须要序列化的属性前增加关键字 transient，序列化对象的时候，这个属性就不会被序列化。你可能会感觉奇怪，ArrayList 能够被序列化的啊，源码可是实现了 java.io.Serializable 接口啊，为什么数组变量还要用 transient 定义呢？
别急，对于这个问题，咱们前面会探讨到，不卖个关子，你们怎么会看到最初，而后给我点在看呢？
当咱们新建一个实例时，ArrayList 会默认帮咱们初始化数组的大小为 10
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;但请留神，这个只是数组的容量大小，并不是 List 真正的大小，List 的大小应该由存储数据的数量决定，在源码中，获取实在的容量其实是用一个变量 size 来示意，
private int size;在源码中，数据默认是从数组的第一个索引开始存储的，当咱们增加数据时，ArrayList 会把数据填充到上一个索引的前面去，所以，ArrayList 的数据都是有序排列的。而且，因为 ArrayList 自身是基于数组存储，所以查问的时候只须要依据索引下标就能够找到对于的元素，查问性能十分的高，这也是咱们十分青眼 ArrayList 的最重要的起因。
然而，数组的容量是确定的啊，如果要存储的数据大小超过了数组大小，那不就有数组越界的问题？
对于这点，咱们不必放心，ArrayList 帮咱们做了动静扩容的解决，如果发现新增数据后，List 的大小曾经超过数组的容量的话，就会新增一个为原来 1.5 倍容量的新数组，而后把原数组的数据一成不变的复制到新数组中，再把新数组赋值给原来的数组对象就实现了。
扩容之后，数组的容量足够了，就能够失常新增数据了。
除此之外，ArrayList 提供反对指定 index 新增的办法，就是能够把数据插入到设定的索引下标，比如说我想把元素 4 插入到 3 前面的地位，也就是当初 5 所在的中央，
插入数据的时候，ArrayList 的操作是先把 3 前面的数组全副复制一遍，而后将这部分数据往后挪动一位，其实就是一一赋值给后移一位的索引地位，而后 3 前面就能够空出一个地位，把 4 放入就实现了插入数据的操作了
删除的时候也是一样，指定 index，而后把前面的数据拷贝一份，并且向前挪动，这样原来 index 地位的数据就删除了。
到这里咱们也不难发现，这种基于数组的查问尽管高效，但增删数据的时候却很耗性能，因为每增删一个元素就要挪动对应 index 前面的所有元素，数据量少点还无所谓，但如果存储上千上万的数据就很吃力了，所以，如果是频繁增删的状况，不倡议用 ArrayList。
既然 ArrayList 不倡议用的话，这种状况下有没有其余的汇合可用呢？
当然有啊，像我这样的暖男必定是第一工夫通知你们的，这就引出了咱们上面要说的LinkedList。
LinkedList
LinkedList 是基于双向链表实现的，不须要指定初始容量，链表中任何一个存储单元都能够通过向前或者向后的指针获取到后面或者前面的存储单元。在 LinkedList 的源码中，其存储单元用一个 Node 类示意：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}Node 中蕴含了三个成员，别离是存储数据的item，指向前一个存储单元的点 prev 和指向后一个存储单元的节点 next，通过这两个节点就能够关联前后的节点，组装成为链表的构造，
因为有保留前后节点的地址，LinkedList 增删数据的时候不须要像 ArrayList 那样挪动整片的数据，只须要通过援用指定 index 地位前后的两个节点即可，比方咱们要在李白和韩信之间插入孙悟空的节点，只须要像这样解决下节点之间的指向地址：
删除数据也是同样原理，只须要扭转 index 地位前后两个节点的指向地址即可。
这样的链表构造使得 LinkedList 能十分高效的增删数据，在频繁增删的情景下能很好的应用，但不足之处也是有的。
尽管增删数据很快，但查问就不怎么样了，LinkedList 是基于双向链表存储的，当查问对应 index 地位的数据时，会先计算链表总长度一半的值，判读 index 是在这个值的右边还是左边，而后决定从头结点还是从尾结点开始遍历，
Node<E> node(int index) {// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}尽管曾经二分法来做优化，但仍然会有遍历一半链表长度的状况，如果是数据量十分多的话，这样的查问无疑是十分慢的。
这也是 LinkedList 最无奈的中央，鱼和熊掌不可兼得，咱们既想查的快，又想增删快，这样的坏事怎么可能都让咱们遇到呢？所以，个别倡议 LinkedList 应用于增删多，查问少的情景。
除此之外，LinkedList 对内存的占用也是比拟大的，毕竟每个 Node 都保护着前后指向地址的节点，数据量大的话会占用不少内存空间。
两者哪个更占空间？
讲到这，你是不是对题目的那个问题成竹在胸了？
下次有面试官问你，ArrayList 和 LinkedList 哪个更占空间时，你就能够山盟海誓的说，LinkedList 更占空间，我看了薛大佬的文章，必定不会错。说完你就能够安心坐着，期待面试官露出称心的笑容，通知你通过面试的音讯，胜利拿下 offer 不可企及。
如果你真的这么答的话，我也置信面试官肯定会被你的答复所驯服，他听完肯定会点点头，嘴角开始上扬，而后笑容满面的通知你，
感激你明天过去面试，你能够回去等告诉了。。。。
哈哈，开个玩笑，不凑多点字可不是我的格调。
言归正传，外表上看，LinkedList 的 Node 存储构造仿佛更占空间，但别忘了后面介绍 ArrayList 扩容的时候，它会默认把数组的容量扩充到原来的 1.5 倍的，如果你只增加一个元素的话，那么会有将近原来一半大小的数组空间被节约了，如果原先数组很大的话，那么这部分空间的节约也是不少的，
所以，如果数据量很大又在实时增加数据的状况下，ArrayList 占用的空间不肯定会比 LinkedList 空间小，这样的答复就显得审慎些了，听下来也更加让人容易认同，但你认为这样答复就完满了吗？非也
还记得我后面说的那个 transient 变量吗？它的作用曾经说了，不想序列化的对象就能够用它来润饰，用 transient 润饰 elementData 意味着我不心愿 elementData 数组被序列化。为什么要这么做呢？
这是因为序列化 ArrayList 的时候，ArrayList 外面的 elementData，也就是数组未必是满的，比方说 elementData 有 10 的大小，然而我只用了其中的 3 个，那么是否有必要序列化整个 elementData 呢？显然没有这个必要，因而 ArrayList 中重写了 writeObject 办法：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {throw new ConcurrentModificationException();
}
}每次序列化的时候调用这个办法，先调用 defaultWriteObject()办法序列化 ArrayList 中的非 transient 元素，elementData 这个数组对象不去序列化它，而是遍历 elementData，只序列化数组外面有数据的元素，这样一来，就能够放慢序列化的速度，还可能缩小空间的开销。
加上这个知识点后，咱们对下面那个问题就能够有更加全面的答复了，如果你下次也遇到这个问题的话，你能够参考一下我的说法：
个别状况下，LinkedList 的占用空间更大，因为每个节点要保护指向前后地址的两个节点，但也不是相对，如果刚好数据量超过 ArrayList 默认的长期值时，ArrayList 占用的空间也是不小的，因为扩容的起因会节约将近原来数组一半的容量，不过，因为 ArrayList 的数组变量是用 transient 关键字润饰的，如果汇合自身须要做序列化操作的话，ArrayList 这部分多余的空间不会被序列化。
怎么样，这样的答复是不是更加的说服力，不仅更加全面，还可能会给面试官留下好印象，让他感觉你是个有本人思考的求职者，说不定当场就让你面试通过了呢。就冲这点，你们是不是应该给我来点个赞啊，哈哈。
作者：鄙人薛某，一个不拘于技术的互联网人，欢送关注我的公众号，这里不仅有技术干货，还有吹水~~~
