是否需要在双链表中有一个尾部指针？如何在没有尾指针的情况下实现双链表插入，如果我们这样做，时间复杂度会是多少
如果您知道在之前或之后插入的节点，那么复杂性为O(1(。您只将上一个/下一个节点中的指针设置为指向新节点，并将新节点中的指示器设置为前一个/后一个节点。如果插入到列表的开头，也可以更新头指针。
如果在双链接列表(或单链接列表(中没有尾指针，并且没有对最后一个元素的引用，则追加到列表中会变成O(n(，因为必须遍历列表才能找到最后一个图元。
不，没有必要。以下是不使用tail指针的双链表的时间复杂性。
准备列表：O(1(
(head<->newNode<->x(
在列表中的两个节点之间插入：O(n(
(head<->x<->newNode<>->y(
附加到列表：O(n(
(head<->x<-->y<->newNode(
注意：使用双链表的
tail会使复杂性O(1(
TL；DR：不，它的功能几乎相同，除了性能较差的附加情况O(n(。