如何轻松编写出无误的链表代码？

本文共计3047个文字，预计阅读时间需要13分钟。

链表虽然是基础的数据结构，但要写好数据结构并非简单的事情，而是那些复杂的链表操作，例如链表反转、有序链表等，写的时候非常容易出错。当你愿意投入整个精力去学习和实践时，才能掌握这些复杂的链表操作。

  链表虽然是基础的数据结构，但是要写好数据结构并不是简单的事情，尤其是那些复杂的链表操作，比如链表反转、有序链表等操作，写的时候非常容易出错。当然你愿意投入一整周末或者一天就去写这些代码，那最后肯定能熟能生巧。
  那今天我们就以了解链表、写好链表、写个练手的 LRU 链表为目标。

五花八门的链表

  相较于数组，链表也是一个线性结构的数据结构，但不同点在于，数组需要一块连续的内存空间，而链表不用，它不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。
  链表结构五花八门，需要重点了解的三种最常见的链表结构，他们分别式：单链表、双向链表、循环链表。

单链表

  刚刚讲到，为了使得不连续的内存空间“串联”起来，链表的中我们称为“结点”的内存块，除了保存自身的数据之外还需要保存下一个结点的内存地址。就好比我们排队一样，每一个人都会知道自己下一个人是谁。
  这张图里的单链表有两个特殊的结点，一个是头结点（第一个结点），一个是尾结点（最后一个结点）。其中，头结点用来记录链表的首地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。
  与数组一样，链表也可以插入、删除、查找等操作。