January
29th,
2023
概念
- 一种线性表数据结构
- 用
指针
将一组零散的内存块(结点
)串联起来使用 - 插入、删除数据非常快速
操作
- 单链表
- 查找 O(n)
- 插入和删除 O(1)
- 循环链表 尾结点
next
指向头结点 - 双向链表
next
后继指针,prev
前驱指针
应用
- 链表适合插入、删除操作频繁的场景
- 双向链表比单链表插入、删除等操作简单、高效,适用更多情况
- 循环链表适合处理具有环型特点的数据,比如约瑟夫问题
练习
- 单链表反转
- 链表中环的检测
- 两个有序链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
编码技巧
- 理解指针和引用的含义(地址)
- 警惕指针丢失和内存泄露
- 利用哨兵简化实现难度
- 重点留意边界条件处理
- 举例画图,辅助思考
- 多写多练,没有捷径