今天又到了算法的主题了，上次我们聊到了数组：面试中的疑难点，这次我们来聊另外一种线性结构，链表。
本质
虽然链表与数组一样都是线性结构，但它们之间还是有本质的区别的。
数组在内存中是一块连续的存储区域，而链表可以支持随机存储，非连续的存储空间。
链表的种类可以分为：单链表、双向链表、循环链表、双向循环链表。
它们的本质都是一样的，不同的是具体的表现与应用。
简单来说，对于单链表是每一个节点都有一个 next 后续指针，它都指向当前节点的下一个链表节点；对于链表的尾节点，由于是链表的最后一个节点，所以它的 next 为 null 。
双向链表与单链表所不同的是，它除了有 next 指针之外，还有 prev 前驱指针，它指向于当前节点的上一个节点；特殊的，链表的头节点的 prev 为 null 。
循环链表与单链表的区别是，它的最后一个节点的 next 将不再为 null ，而是指向头节点或者链表的其它位置节点。
而对于双向循环链表也是同样的原理。
插入
我们都听过这么一句话，链表适合插入与删除。这主要是由于链表自身的数据结构决定的。
对于单链表来说，向已知的一个节点后插入一个新的节点，它所要做的事情就是将当前节点的 next 指针指向新的节点，然后再将新节点的 next 指向指向当前节点的之前的后续节点。
而这个过程不需要任何数据的迁移，只需改变节点的 next 指针指向，所以它的时间复杂度为 O(1) 。
看图很简单，但真正去实现的话，不一定都会，尤其是首次接触到链表的读者。容易犯的是下面这个错误：
node.next = newNode
newNode.next = node.next
犯这个错误的本质绝大多数还是对链表的指针理解不到位。其实对于指针的理解，我们只需记住一点，指针指向的是节点在内存中的地址。
改变指针就是改变指向的地址。
正确的做法是下面这种：
newNode.next = node.next
node.next = newNode
当然，为了杜绝这个问题，还有一个简单的方法就是多练，写多了自然就会了。
所谓书读百遍其义自见，应该就是这个道理。
还有上面的时间复杂的是基于一个前提的：已经找到了插入节点的位置。而查找当前插入点，需要通过遍历整个链表的，所以链表中查找一个节点的时间复杂度为 O(n) 。
可能有的读者一直都有一个疑问，为什么有了单链表还有出来一个双向链表，你看这插入双向链表也是与单链表一样，时间复杂度都为 O(1) ，而双向链表由于它每个节点都额外需要 prev前驱节点，导致它更加浪费内存。
针对这类问题，我们将上面的插入位置做一下调整。
现在已知了当前节点的位置，下面需要将新节点插入到当前节点的前面。
如果是单链表，由于只有 next 指针，所以只能重新遍历链表，找到当前节点的上一个节点，然后再重复上面的转移指针的步骤，此时时间复杂度为 O(n) 。
而对于双向链表，由于它还有 prev 执行，所以它可以直接改变 prev 的指向，来将新节点插入到当前节点的前面，所以它的时间复杂度为 O(1) 。
正是由于这特性，在实际运用中，双向链表比单链表更加普遍，例如我们所熟悉的 LinkedList：
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; } }
删除
链表的删除与插入原理类似，都是改变节点的指针指向。
对于单链表，如果删除当前节点的后续节点，只需将当前节点的 next 指针指向当前节点的后续节点的后续节点。文字有点绕，还是直接看代码
node.next= node.next.next
而对于双向链表来说，除了改变 next 节点，还要改变 next 指向的 prev 节点。
node.next= node.next.next
node.next.prev= node
它们的时间复杂度都为 O(1)
另外的删除节点为当前节点的前驱节点。这个与插入原理类似，这里就不做详细分析。单链表的时间复杂度为 O(n) ，双向链表的时间复杂度为 O(1) 。
注意点：
现在我们已经对链表有了一个较全面的了解。但开始上手写的时候还是会很容易犯错。
下面我结合自己的一点经验还对容易犯的错误做一个总结，并对其提出相应的解决方案。
1、指针的指向问题
首先是写链表时，对于指针的指向错乱问题。
如果遇到简单的插入删除，步骤不是很频繁的情况，相信大家都能够很容易的完成。一旦涉及到链表的指针频繁改变，亦或者是双向链表(再加一个前驱指针)，这时犯错率就会直线提升。
解决方案是：
（1）放下心来仔细思考，理清整个过程，再动手写代码。
（2）借助辅助工具，例如停下手来，找只笔找张纸，把链表的结构画出来，然后在画它们间的指针指向。
（3）简单粗暴，多看多练。基本上做个每天做个一两道，坚持一星期基本就可以了。
2、边界问题
在写链表的过程中，还有一种情况就是对边界的处理。可能是忘了对边界的处理；也可能是直接处理错误。
对于链表的边界就是它的头节点与尾节点。由于它们的特殊性，针对它们的插入与删除，可能与别的节点不同，需要额外进行特殊处理。
针对这种问题，我们需要做的就是，写完链表之后，时刻都要提醒自己是否对边界做了处理，如果做了也要停下来思考一遍是否处理正确。
这样就能很好的保证边界处理的正确性。
千万不要偷懒，别因为这个边界问题导致在面试过程中的评分打折扣。因为这能从侧面体现一个人的思维的全面与缜密性。
3、哨兵优化
针对上面的边界问题，有没有代码上的优化呢？
有的，这里要说的就是哨兵优化。
所谓的哨兵，简单的理解就是固定一个标识，让它像边界的士兵一样，一直屹立在他的边界岗位，守卫国土的安全。
例如，我们拿上面的双向链表的删除来说。
对于非头节点的删除，我们只需找到当前的节点，然后改变它前后节点的 next 与 prev 指针的指向即可：
node.prev.next = node.next
node.next.prev = node.prev
现在如果当前节点是头节点，上面的代码就不能运行，因为头节点的 prev 节点为 null ，所以常规的做法是做特殊判断
if (node == head) {
node.next.prev = null
}
这样就是边界问题的处理，如果你记得处理那还好，一旦忘了就导致异常。
而使用哨兵就能够完全规避边界的判断，我们来看具体使用方式：
// 建立哨兵，新建#节点，并将其next指针指向头节点 val guard = LinkedNode("#") val newLinked = guard.next = head head.prev = guard ... // 节点删除(包括头节点) node.prev.next = node.next node.next.prev = node.prev // 返回删除后的链表 return newLinked.next
经典实例
下面是一些关于链表的经典的实例，如果对链表还不熟悉的推荐亲自去写一遍。写完之后你将对链表有一个全新的认识。
1、环的检测；2、单链表反转；3、删除链表倒数第n个结点；4、LRU；5、求链表的中间结点；6、两个有序链表的合并；7、单链表判断回文。
—— 加油 ——
最后，不管你是转行也好，初学也罢，进阶也可，如果你想学编程~
【值得关注】我的 C/C++编程学习交流俱乐部！【点击进入】
问题答疑，学习交流，技术探讨，还有超多编程资源大全，零基础的视频也超棒~