Skip to main content

链表

概念

种类

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

技巧

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

复杂度

插入删除

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

查找

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