在双向链表中是否必须有一个尾部指针？如何在没有尾指针的情况下实现双链列表插入，如果这样做的话，时间会很复杂。
biyesheng630 回答：如何在不使用尾部指针的情况下实现双向链表
否，没有必要。以下是不使用tail指针的双向链接列表的时间复杂度。
添加到列表中：O（1）
（头 newNode x）
插入列表中的两个节点：O（n）
（head x newNode y）
附加到列表：O（n）
（头 x y newNode）
注意：利用双向链接列表的
tail会使复杂度为O（1）
TL; DR ：不，除了附加性能较低的O（n）外，它的功能几乎相同。
,如果您知道要插入的节点之前或之后，则复杂度为O（1）。您只能将上一个/下一个节点中的指针设置为指向新节点，而将新节点中的指针设置为上一个/下一个节点。如果要插入到列表的开头，还可以更新头指针。
如果在双向链接列表（或单链接列表）中没有尾部指针，并且对最后一个元素没有引用，则追加到列表将变为O（n），因为您必须遍历列表以找到最后一个元素。