链表：由浅入深

今天又到了算法的主题了，上次我们聊到了数组：面试中的疑难点，这次我们来聊另外一种线性结构，链表。

本质

虽然链表与数组一样都是线性结构，但它们之间还是有本质的区别的。

数组在内存中是一块连续的存储区域，而链表可以支持随机存储，非连续的存储空间。

链表的种类可以分为，单链表、双向链表、循环链表、双向循环链表。

它们的本质都是一样的，不同的是具体的表现与应用。

简单来说，对于单链表是每一个节点都有一个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. 放下心来仔细思考，理清整个过程，再动手写代码。
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. 单链表判断回文

我这里也提供了全部的源码，kotlin与java都有，希望对你有所帮助。

daily_algorithm: https://github.com/idisfkj/daily_algorithm