05 链表
单链、循环链、双链与节点连接
第 01 题 问题 1
Node(10, Node(20)) 中 first.next.value 是多少？
参考答案
20。
解析
next 引用下一个节点；值不通过地址连续性决定。
第 02 题 问题 2
为什么普通链表按下标读取第 i 项通常需要 O(i) 时间？
参考答案
需从已知入口沿 next 逐步前进。
解析
没有数组的按偏移随机访问机制。
第 03 题 问题 3
在 head 前插入 node，应按什么顺序修改引用？
参考答案
先 node.next=head，再 head=node。
解析
先保留旧入口，避免旧链失去入口。
第 04 题 问题 4
在已知节点 p 后插入新节点，链接操作复杂度是什么？
参考答案
O(1)。
解析
先 new.next=p.next，再 p.next=new；若还需查找 p，要另计搜索成本。
第 05 题 问题 5
删除单链表中已知值的节点，为什么可能为 O(n)？
参考答案
先查找节点及前驱可能走完整条链。
解析
知道值不等于已有前驱引用；删除链接本身可以是常数工作。
第 06 题 问题 6
删除单链表首节点与删除普通中间节点，引用处理有什么差异？
参考答案
首节点更新 head；中间节点更新前驱 next。
解析
哨兵可统一部分边界，但不能忽略空链和末节点。
第 07 题 问题 7
哨兵节点会让按值搜索从 O(n) 自动变成 O(1) 吗？
参考答案
不会。
解析
哨兵简化边界处理，不改变搜索遍历的增长阶。
第 08 题 问题 8
维护 tail 时删除最后一项，要注意什么？
参考答案
更新 tail 到新末节点；变空时 head/tail 要一致。
解析
单链表找末节点前驱可能仍需遍历；tail 不会自动提供前驱。
第 09 题 问题 9
循环链表遍历还能一直等到 None 才停止吗？
参考答案
不能。
解析
闭环没有 None 终点，应检查是否回到起点或使用限定步数。
第 10 题 问题 10
双向链表给定节点 p，删除通常需要哪些连接更新？
参考答案
让 p.prev.next 指向 p.next，并让 p.next.prev 指向 p.prev，边界单独处理。
解析
两向链接必须保持一致；是否有哨兵决定具体边界写法。
第 11 题 问题 11
链表在头部增删快，是否意味着比 list 在所有任务上更快？
参考答案
不是。
解析
随机访问、缓存局部性、节点额外空间及 Python 对象开销也影响性能。
第 12 题 问题 12
del p 是否一定把节点从链表中移除？
参考答案
不一定。
解析
只删除名称绑定；前驱 next 若仍指向它，节点仍属于可达链。