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