上篇文章说了下，数据和ArrayList，这篇文章我们说下在面试中有很大概率两者作为兄弟同时出现的LinkedList，希望大家看完这篇文章后能够有恍然大悟的感觉。
LinkedList底层是 链表 实现的，那么我们首先说下什么是链表。
和上篇文章的数组相比，链表要相对于更复杂一点，两者也是非常基础、常用，而且在面试中同时出现的概率也是很大的。
上篇文章我们说到，数据是需要连续的内存空间来存储的，而链表刚好与它相反，链表是不需要连续的内存空间的，它是通过将好多的零散的内存使用“指针”串联起来使用，如果数组和链表都想在计算机中申请大小为10M的内存，而计算机中只有10M的零散内存，那么数组就会申请内存失败，链表就会成功。
想对数组和ArrayList有多些了解的小伙伴可以看我的上篇文章
既然链表在内存中都是零散的块，那么我们是怎么称呼这些小块块呢？
我们把这些块叫做“结点”，为了把每个结点都串联起来，结点中不仅会存储数据，还有存储下一个结点的 地址 。
那我们怎么称呼记录下个结点地址的指针呢？
我们把他们叫做“后继指针next”。
链表中最特殊的是头结点和尾结点，顾名思义，也就是链表的第一个结点和最后一个结点，第一个结点保存着链表的基地址，通过这个结点，我们就能定位到它，最后一个结点的指针指向的是NULL，说明这个是链表的最后一个结点。
LinkedList中元素的所有操作都是在这样的数据结构上进行的，大家可以脑补下。
链表也可以进行插入、删除和查询操作。数组在进行插入和删除操作的时候，会进行数据的搬移操作，因为数据要保证他的内存空间是连续的，而链表则不需要，因为他的内存空间本就不是连续的 ，它只需要改变相邻结点的指针改变就够了，所以速度是非常快的。
但是查询就不会那么快了，链表查询数据要一个一个的遍历结点，直到找到相应的结点。
链表还有 双向链表 和循环链表，我们要说的LinkedList就是一个双向链表，上面说到的单向链表是只存了后一个结点的地址，而双向链表呢，是同时保存了前一个和后一个共两个元素的地址，所以就可以很方便的获取到一个结点的前后两个元素，而且我们也可以从前后两个方向来遍历。
接下来我们看下LinkedList的源码：
首先是继承关系：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
也是同时继承了Cloneable 和 Serializable ，Deque是一个双端队列，说明在LinkedList中同时也支持对队列的操作。
LinkedList的属性只有三个：
transient int size = 0; transient Node<E> first; transient Node<E> last;
头结点，尾结点，链表中的元素数量，三者都是被 transient关键字修饰的，有小伙伴不理解这个关键字的，欢迎看我上上篇文章：
Node是它的一个内部类，用来保存数据：
中间省略一万字（因为头条贴上源码可读性实在是太差了，所以如果大家有意愿看我的文章，欢迎移步公众号，里面是完整的文章，完整等等源码解析）。。。
从代码中可以看得出来，链表获取指定元素效率还是很低的，需要将元素遍历才能找到目标元素。需要的时间复杂度是O(n)的，但是我们在工作中不能仅仅利用复杂度分析就决定使用哪个数据结构。
数组简单易用，在实现上使用的是连续的内存空间，可以通过CPU的缓存机制，来实现预读，访问速度会比较快。而链表，由于内存不是连续的，所以不能通过这种方法来实现预读。链表本身没有大小限制，天然支持动态扩容，这也是和数组最大的区别。
如果你的程序对内存使用要求很高，那么就可以选择数组，因为链表中的每一个结点都需要消耗额外的内存去存储指向下一个结点的指针，所以内存消耗会翻倍，而且对于链表的频繁删除和插入，会导致频繁的内存申请和释放，造成内存碎片，就会引起频繁的GC（Garbage Collection 垃圾回收）。
这次只分析了这几个比较核心的方法源码，大家也可以自己尝试着去看看源码，学习下JDK中代码的风格，多思考下为什么要这么写，相信会有不少的进步。
简单分析完之后，我们总结下问题吧。
ArrayList和LinkedList的区别是什么？（老经典的面试题）
欢迎大家能在留言区中留言，说出你的答案。
如果对本文有任何异议或者说有什么好的建议，可以加我好友（有没有问题都欢迎大家加我好友，公众号后台联系作者，公众号同名：java技术情报局），也可以在下面留言区留言，我会及时修改。希望这篇文章能帮助大家在面试路上乘风破浪。
这样的分享我会一直持续，你的关注、转发和点赞是对我最大的支持，感谢。关注我，我们一起成长。
