双向链表(Doubly linked list)删除头节点的操作逻辑疑问
双向链表删除头节点操作逻辑解答
我们先明确双向链表的核心规则:
- 整个链表仅维护
head(头节点)、tail(尾节点)两个对外访问入口 - 头节点的
prev指针必须为null,尾节点的next指针必须为null - 仅需要维护链表内有效节点的
prev、next指针,已被移出链表的节点不需要再调整指针状态
对应你给出的1->2->3的序列例子,删除头节点的执行逻辑拆解:
- 初始状态:
head指向节点1,节点1的next指向2,节点2的prev指向1,节点2的next指向3,节点3的prev指向2 - 执行
this.head=removedHead.getNextNode()后,链表的head指针已经指向节点2,但此时节点2的prev还指向已经被移除的节点1,不符合头节点的规则 - 这时候仅需要把新头节点(节点2)的
prev调用setPreviousNode(null)设为null,就完全符合双向链表的正常运行要求,不需要额外操作的原因有三个:- 被移除的旧头节点1已经没有被链表的任何有效指针引用,Java的垃圾回收机制会自动回收它的内存,不需要额外修改它的
next指针 - 新头节点2的
next本来就正确指向节点3,不需要做任何修改 - 后续节点3的
prev本来就正确指向节点2,也不需要调整
- 被移除的旧头节点1已经没有被链表的任何有效指针引用,Java的垃圾回收机制会自动回收它的内存,不需要额外修改它的
你贴的代码里还有额外的兼容逻辑:如果被删除的头节点同时是尾节点,说明原来的链表只有1个节点,这时候改完head为null之后,调用removeTail处理尾指针的重置,整体逻辑是自洽的。
内容的提问来源于stack exchange,提问作者mario
相关产品推荐
相关产品推荐

