链表

概念

种类

• 单项链表
• 双向链表
• 循环链表

技巧

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

复杂度

插入删除

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

查找

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