链表

链表是一种常见的数据结构，是一组有序的数据，每个链表中的数据项称为元素。

它跟数组很像，二者对比学习会更容易理解和记忆。数组是内存中连续的一块，不会间断。链表在内存中不一定是连续的一块。如果内存只剩 10M，且不是连续的，定义数组就会失败，定义链表就是成功的。数组为了保证内存地址的连续性，当做删除和插入时，需要做大量迁移工作，而链表是不需要迁移操作的。所以数组更适合快速查找，链表更适合插入、删除操作。

链表中会有一些常见属性或方法，比如链表中的元素个数，链表当前的位置，向链表增加一个元素，从链表中删除一个元素，清空链表等一系列操作。

最常见的链表结构

链表结构有很多种，其中三种比较常见：单链表、双向链表、循环链表以及双向循环链表。

单链表

链表是一组节点组成的集合，为了将不连续的内存串联起来，每个节点除了存储数据外，还需要记录下一个节点的地址。

如图：data 中保存着数据，next 保存着下一个节点的地址。
链表中，二个节点比较特殊，分别是第一个节点和最后一个节点。第一个节点被叫做头结点，用来记录链表的基地址，由此我们可以轻松找到该链表了。最后一个节点叫做尾节点，它是最后一个节点，没有下一个节点，所以它的指针指向一个空地址。实现LRU就可以用单链表实现。

图上，演示了链表的插入和删除操作。也说明了，链表的删除和插入操作不需要移动其他节点。

循环链表

循环链表和和单链表的区别就是尾节点，单链表最后一个节点指向null，而循环链表指向链表的头结点。

相比单链表，循环链表在找首节点时有着很大的优势，很方便就可以找到首节点。这使得它更适合处理有环形结构的数据，比如约瑟夫问题。

双向链表

双向链表也叫双链表，它的每个结点都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

相比单链表，在删除或插入特定指针指向的节点时，双链表在删除或插入更具优势。删除操作的时间复杂度都是 O(1) ，但是删除时需要知道前驱指针，双向链表存储了前驱指针，所以可以直接获取到。双链表消耗了更多的空间，但是执行时间少了，是空间换时间的设计思路。

双向循环链表

双向循环链表就是循环链表个双链表的结合，感兴趣可以自己看看，本质差不多。

建议

以上内容很好理解，难点在于实际编码过程。大家可以试试编写，插入和删除操作、单链表的反转、二个链表合并、删除倒数第 n 个节点、找链表的中间节点。以上操作是常见的操作，但真正动手可能没有想象中那么简单。

1. 理解指针和引用的含义， 初学者在 p->next 、q->next处就会开始犯错，导致链表断裂或者指针丢失（ 我就是 ）。
2. 特殊情况要格外小心，bug多出现在这里 。例如链表为空时，链表只有一个节点时。
3. 可以画图辅助。
4. 多练习，刷刷题。

本作品采用《CC 协议》，转载必须注明作者和本文链接