1. 链表

1.1. 概念

1.2. 种类

1. 单项链表
2. 双向链表
3. 循环链表

1.3. 技巧

1. 有些时候需要创建新链表, 并在之后连接数据, 而在创建时值为空, 可以直接 $list->next 使用, 最后=返回 $list->next
2. 使用数组或者hash表来缓存 list 中的值
3. 涉及到链表查询时, 使用双指针可能会解决一些找重合点的问题
4. 链表实现大数加法: 002_两数相加.php
5. 链表在修改时核心操作为, 修改next指向, 即可快速改变链表的属性

1.4. 复杂度

1.4.1. 插入删除

时间复杂度: O(1), 只需要考虑相邻的节点指针修改

1.4.2. 查找

时间复杂度: O(n), 需要重头遍历查找