上一篇介绍了一维数据结构的关系，算是开篇了数据结构这个系列。这篇详细说一下链表的实现。
链表实现也是我面试时喜欢出的一道题，因为有层次，能提现区分度。看似简单的三个操作，需要处理的异常和边界情况并不少，能一次完美写对并不容易。
而且这里还有一个哨兵的概念，合理运用能减少边界处理，是一个递进的层次，可为候选人增加区分度。

链表的操作：
（1）SEARCH(x)：链表的搜索
（2）INSERT(i,x)：链表的插入，在第i个位置插入x
（3）DELETE（x）:链表的删除

哨兵（sentinel）：
为了减少边界条件的判断（是否为空链表等等），引入哨兵，使得链表永远不为“空”。

下面就细讲一下链表实现

插入

上面说了为了减少边界，我们使用了一个哨兵的概念，那么都有哪些边界呢？

1.不用哨兵

插入的核心操作如下：

// pre: 前置节点; p: 当前第i个节点
// item: 待插入节点
pre.next -> item;
item.next -> p;

进行插入，就需要知道两个节点指针，这时就出现了两个边界情况，是不存在前置节点的：

• 链表为空
• 插入位置是0

需要对两种情况做特殊处理，直接看代码

void insert(i,item) {
  // 空链表的处理
  if (head == NULL) {
    head == item;
  }

  // 插入到第一个位置的情况
  if (i == 0) {
    // 插入
    head.next -> item;
    item.next -> head;
    head = item;
  } else {
     // 第一个节点
    Node *pre = head;
    Node *p = head -> next;
    int idx = 0;
    // 添加 p 非空条件，处理 i > length 情况 
    while (idx < i && p != NULL) {
      pre = pre -> next;
      p = p -> next;
    }
    // 插入
    pre.next -> item;
    item.next -> p;
  }
}

处理下来27行，进行了两次if-else判断

2.使用哨兵

但如果引入哨兵概念，会怎么样呢？

void insert(i,item) {
  // 获取哨兵和实际上第一个节点
  Node *pre = sentinel;
  Node *p = sentinel -> next;
  int idx = 0;
  // 添加 p 非空条件，处理 i > length 情况 
  while (idx < i && p != NULL) {
    pre = pre -> next;
    p = p -> next;
  }
  // 插入
  pre.next -> item;
  item.next -> p;
}

可以看到，整个操作简单归一，14行就搞定了，没有额外边界处理逻辑处理，也不需要再进行头结点变更，哨兵的内存开销也不大。是一个优雅的解决方式。

再看看剩下两个方法的实现细节

搜索

比较简单，没有对前置节点的依赖，所以无需做特殊处理。

Node* search(x) {
    Node *p = head;
    // Node *p = sentinel -> next;

    while (p != NULL) {
        if (*p.data == x) {
            break;
        }
        p = p -> next;
    }

    return p;
}

删除

先简单介绍下两种链表删除操作

1.依赖前置节点pre

1>将 pre->next 指向 found->next
2>去除 found->next指向
3>删除found节点

方法一

但是对于单链表操作，拿到前置节点非常困难，为了避免使用前置节点，我们可以使用一次拷贝，将删除节点从found变成found->next，比如：

2.不依赖前置节点 pre

1>将next节点内容copy到found
2>found->next指向next->next
3>删除next

方法二

顺利避免了对前置节点依赖，还可以复用上面的 search 函数。但是这种设计，存在一个问题：就是当删除的是最后一个节点时，依然有对前置节点的依赖。这时引入一个末尾哨兵，保证我们的 next 节点永远不为 NULL，让我们避免这种情况。

需要对插入、查找做修改

3.引入末尾哨兵

init() {
  head_sentinel = new Node();
  tail_sentinel = new Node();
  head_sentinel->next = tail_sentinel;
  tail_sentinel->next=NULL:
}

void insert(i,item) {
  // 获取头部哨兵和实际上第一个节点
  Node *pre = head_sentinel;
  Node *p = head_sentinel -> next;
  int idx = 0;
  // 添加 p ≠ tail_sentinel，处理 i > length 情况 
  while (idx < i && p != tail_sentinel) {
    pre = pre -> next;
    p = p -> next;
  }
  // 插入
  pre.next -> item;
  item.next -> p;
}

Node* search(x) {
    Node *p = head_sentinel -> next;

        // 结束条件，变为不等于末尾哨兵
    while (p != tail_sentinel) {
        if (*p.data == x) {
            break;
        }
        p = p -> next;
    }

    return p;
}

void delete(x) {
    Node *found = search(x);
    if (found == NULL) return;

    Node *next = found->next;
    *found.data = copy(*next.data);
        // 因为有末尾哨兵的存在，next永远不为NULL
    found->next = next->next;
    next->next = NULL;
    delete(next);
}

小结

综上，哨兵的作用就是保持链表非空，将所有操作去差异化，减少边界条件的处理。从广义上来说，链表的操作过程中产生了对“邻居节点”的依赖，当这种依赖是不稳定的时候，我们就可以使用哨兵，将这种依赖补齐，或者是转化为对“哨兵”的稳定依赖。
此外，在删除过程中，因为单链表获取前置节点困难，所以针对该点进行优化，这也是很多数据结构和算法调优的思路。熟悉后可以举一反三。

参考

https://www.jianshu.com/p/afbfc784238a
https://www.zhihu.com/question/27155932