go - 如何在不使用尾部指针的情况下实现双向链表

Question

在双向链表中是否必须有一个尾部指针？如何在没有尾指针的情况下实现双链列表插入，如果这样做的话，时间的复杂度是多少。

Answer 1

不，没有必要。以下是不使用tail指针的双向链接列表的时间复杂度。

附加到列表: O(1)

(头<-> newNode <-> x)

在列表的两个节点之间插入:O(n)

(头<-> x <-> newNode <-> y)

追加到列表:O(n)

(头<-> x <-> y <-> newNode)

注意:利用双向链表的tail会使复杂度为O(1)


TL; DR :不，除了附加性能较低的O(n)外，它的功能几乎相同。