链表
概念
种类
- 单项链表
- 双向链表
- 循环链表
技巧
- 有些时候需要创建新链表, 并在之后连接数据, 而在创建时值为空, 可以直接 $list->next 使用, 最后=返回 $list->next
- 使用数组或者hash表来缓存 list 中的值
- 涉及到链表查询时, 使用双指针可能会解决一些找重合点的问题
- 链表实现大数加法: 002_两数相加.php
- 链表在修改时核心操作为, 修改next指向, 即可快速改变链表的属性
复杂度
插入删除
时间复杂度: O(1), 只需要考虑相邻的节点指针修改
查找
时间复杂度: O(n), 需要重头遍历查找