作者
码海
来源
码海
前言
如果说数据结构是算法的基础，那么数组和链表就是数据结构的基础。因为像堆，栈，对，图等比较复杂的数组结基本上都可以由数组和链表来表示，所以掌握数组和链表的基本操作十分重要。
今天就来看看链表的基本操作及其在面试中的常见解题思路,本文将从以下几个点来讲解链表的核心知识
什么是链表，链表的优缺点链表的表示及基本操作链表常见解题思路---翻转链表常见解题思路---快慢指针
什么是链表
相信大家已经开始迫不及待地想用链表解题了，不过在开始之前我们还是要先来温习下链表的定义，以及它的优势与劣势，磨刀不误砍柴功！
链表的定义
链表是物理存储单元上非连续的、非顺序的存储结构，它是由一个个结点，通过指针来联系起来的，其中每个结点包括数据和指针。
链表的非连续，非顺序，对应数组的连续，顺序，我们来看看整型数组1，2，3，4在内存中是如何表示的
可以看到数组的每个元素都是连续紧邻分配的，这叫连续性，同时由于数组的元素占用的大小是一样的，在Java中int型大小固定为4个字节,所以如果数组的起始地址是，由于这些元素在内存中都是连续紧邻分配的，大小也一样，可以很容易地找出数组中任意一个元素的位置，比如数组中的第三个元素起始地址为+2*4=,这就叫顺序性。查找的时间复杂度是O(1),效率很高！
那链表在内存中是怎么表示的呢
可以看到每个结点都分配在非连续的位置，结点与结点之间通过指针连在了一起，所以如果我们要找比如值为3的结点时，只能通过结点1从头到尾遍历寻找，如果元素少还好，如果元素太多（比如超过一万个），每个元素的查找都要从头开始查找，时间复杂度是O(n)，比起数组的O(1)，差距不小。
除了查找性能链表不如数组外，还有一个优势让数组的性能高于链表,这里引入程序局部性原理，啥叫程序局部性原理。
我们知道CPU运行速度是非常快的，如果CPU每次运算都要到内存里去取数据无疑是很耗时的，所以在CPU与内存之间往往集成了挺多层级的缓存，这些缓存越接近CPU，速度越快，所以如果能提前把内存中的数据加载到如下图中的L1,L2,L3缓存中，那么下一次CPU取数的话直接从这些缓存里取即可，能让CPU执行速度加快，那什么情况下内存中的数据会被提前加载到L1,L2,L3缓存中呢，答案是当某个元素被用到的时候，那么这个元素地址附近的的元素会被提前加载到缓存中
以上文整型数组1，2，3，4为例，当程序用到了数组中的第一个元素（即1）时，由于CPU认为既然1被用到了，那么紧邻它的元素2，3，4被用到的概率会很大，所以会提前把2，3，4加到L1,L2,L3缓存中去，这样CPU再次执行的时候如果用到2，3，4，直接从L1,L2,L3缓存里取就行了，能提升不少性能
画外音：如果把CPU的一个时种看成一秒，则从L1读取数据需要3秒，从L2读取需要11秒，L3读取需要25秒，而从内存读取呢，需要1分40秒，所以程序局部性原理能对CPU执行性能有很大的提升
而链表呢，由于链表的每个结点在内存里都是随机分布的，只是通过指针联系在一起，所以这些结点的地址并不相邻，自然无法利用程序局部性原理来提前加载到L1,L2,L3缓存中来提升程序性能。
画外音：程序局部性原理是计算机中非常重要的原理，这里不做展开，建议大家查阅相关资料详细了解一下
如上所述，相比数组，链表的非连续，非顺序确实让它在性能上处于劣势，那什么情况下该使用链表呢？考虑以下情况
大内存空间分配由于数组空间的连续性，如果要为数组分配M的空间，这M的空间必须是连续的，未使用的，所以在内存空间的分配上数组的要求会比较严格，如果内存碎片太多，分配连续的大空间很可能导致失败。而链表由于是非连续的，所以这种情况下选择链表更合适。
元素频繁删除和插入如果涉及到元素的频繁删除和插入，用链表就会高效很多，对于数组来说，如果要在元素间插入一个元素，需要把其余元素一个个往后移（如图示），以为新元素腾空间（同理，如果是删除则需要把被删除元素之后的元素一个个往前移），效率上无疑是比较低的。
(在1，2间插入5，需要把2，3，4同时往后移一位)
而链表的插入删除相对来说就比较简单了，修改指针位置即可，其他元素无需做任何移动操作（如图示：以插入为例）
综上所述：如果数据以查为主，很少涉及到增和删，选择数组，如果数据涉及到频繁的插入和删除，或元素所需分配空间过大，倾向于选择链表。
说了这么多理论，相信读者对数组和链表的区别应该有了更深刻地认识了，尤其是程序局部性原理，是不是开了不少眼界^_^，如果面试中问到数组和链表的区别能回答到程序局部性原理，会是一个非常大的亮点！
接下来我们来看看链表的表现形式和解题技巧
需要说明的是有些代码像打印链表等限于篇幅的关系没有在文中展示，我把文中所有相关代码都放到github中了，大家如果需要，可以访问我的github