链表

定义

单链表

删除结点中“值等于某个给定值”的结点：O(n)
删除给定指针指向的结点：O(n)

循环链表

循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。
比如著名的约瑟夫问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O（nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。

双向链表

删除结点中“值等于某个给定值”的结点：O(n)
删除给定指针指向的结点：O(1)

双向循环链表

对比数组

实现链表的注意事项

理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

警惕指针丢失和内存泄漏

插入结点时，一定要注意操作的顺序
删除链表结点时，也一定要记得手动释放内存空间

利用哨兵简化实现难度

引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。

// 插入
new_node->next = p->next;
p->next = new_node;
// 删除
p->next = p->next->next;

重点留意边界条件处理

• 如果链表为空时，代码是否能正常工作？
• 如果链表只包含一个结点时，代码是否能正常工作？
• 如果链表只包含两个结点时，代码是否能正常工作？
• 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？