链表

概念

1. 一种线性表数据结构
2. 用指针将一组零散的内存块(结点)串联起来使用
3. 插入、删除数据非常快速

操作

• 单链表
  • 查找 O(n)
  • 插入和删除 O(1)
• 循环链表 尾结点next指向头结点
• 双向链表 next后继指针，prev前驱指针

应用

1. 链表适合插入、删除操作频繁的场景
2. 双向链表比单链表插入、删除等操作简单、高效，适用更多情况
3. 循环链表适合处理具有环型特点的数据，比如约瑟夫问题

练习

1. 单链表反转
2. 链表中环的检测
3. 两个有序链表合并
4. 删除链表倒数第 n 个结点
5. 求链表的中间结点

编码技巧

1. 理解指针和引用的含义(地址)
2. 警惕指针丢失和内存泄露
3. 利用哨兵简化实现难度
4. 重点留意边界条件处理
5. 举例画图，辅助思考
6. 多写多练，没有捷径