编写链表的技巧

前言

接触编程满打满算已经两年多了，数据结构一直都是我绕不过去的坎，链表也是我最早接触的数据结构之一，对其中的原理倒是了熟于心，但是到真真需要使用他的时候反而写起来感觉非常的吃力，看了一些博客，总结了一些编写链表的技巧，方便于我以后的学习以及复盘。

理解指针与引用

其实链表并不是一个很难的数据结构，但是把她和指针揉在了一起，就会很容易让人琢磨不到头脑，所以想要学好链表，就需要好好的理解指针。 我们知道很多语言都会有指针的概念，例如c，golang等等，但是也有很多语言并没有指针的概念，例如java，python等，取而代之的是引用的概念，其实无论是指针还是引用他们的本质都是相同的，都是储存所指对象的地址。

实际上，对于指针的理解，你只需要记住下面这句话就可以了：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。 在编写链表代码的时候，我们经常会有这样的代码：p->next=q。这行代码是说，p 结点中的 next 指针存储了 q 结点的内存地址。还有一个更复杂的，也是我们写链表代码经常会用到的：p->next=p->next->next。这行代码表示，p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址。掌握了指针或引用的概念，也就能很轻松的看懂链表的代码了。

防止内存泄漏以及指针的丢失

不知道你们在写代码的时候有没有遇到过这样的问题：一个链表其中的节点指针指来指去的一会儿就不知道指到哪去了，这样往往会引起一些很严重的问题，所以我们在写链表的时候千万不要弄丢了指针。 我们看一下下面这张图：

如图所示，我们希望在结点 a 和相邻的结点 b 之间插入结点 x，假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露

p->next = x; // 将p的next指针指向x结点； x->next = p->next; // 将x的结点的next指针指向b结点；

初学者经常会在这儿犯错。p->next 指针在完成第一步操作之后，已经不再指向结点 b 了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next，自己指向自己。因此，整个链表也就断成了两半，从结点 b 往后的所有结点都无法访问到了。 对于有些语言来说，内存的管理也是需要程序员手动操作的，例如c语言，每当我们删除了一个节点时，我们需要手动去释放他的内存，如果是java这种虚拟机自动管理内存的语言就不用管。

利用哨兵简化难度

首先，我们先来回顾一下单链表的插入和删除操作。如果我们在结点 p 后面插入一个新的结点，只需要下面两行代码就可以搞定。

new_node->next = p->next; p->next = new_node;

但是，当我们要向一个空链表中插入第一个结点，刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理，其中 head 表示链表的头结点。所以，从这段代码，我们可以发现，对于单链表的插入操作，第一个结点和其他结点的插入逻辑是不一样的。

if (head == null) { head = new_node; }

从前面的一步一步分析，我们可以看出，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错。如何来解决这个问题呢？技巧三中提到的哨兵就要登场了。哨兵，解决的是国家之间的边界问题。同理，这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。还记得如何表示一个空链表吗？head=null 表示链表中没有结点了。其中 head 表示头结点指针，指向链表中的第一个结点。 如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。我画了一个带头链表，你可以发现，哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。