为何单/双链表的尾节点删除查询可实现O(1)时间复杂度？

要让双向链表的尾节点删除操作达到O(1)时间复杂度，核心是额外维护一个指向尾节点的tail指针，再结合双向链表节点自带的prev前驱指针，具体逻辑和复杂度解释如下：

• 常规遍历删除的问题：如果没有tail指针，你需要从链表头节点开始循环遍历到最后一个节点，这个过程要走n-1步（n是链表长度），操作次数和n成正比，所以时间复杂度是O(n)。
• O(1)实现的关键操作：
  1. 直接通过tail指针获取当前尾节点，这一步不需要遍历，是常数时间操作。
  2. 利用尾节点的prev指针，直接拿到倒数第二个节点（也就是新的尾节点）。
  3. 将倒数第二个节点的next指针置为null，然后把tail指针更新为这个倒数第二个节点。
  4. 最后返回并释放原尾节点的内存。

这些步骤里，所有操作都是固定的几步，不管链表长度n是10还是10000，操作次数都不会变——完全不依赖n的大小，所以时间复杂度是O(1)。

简单说，时间复杂度的判定看的是操作次数和输入规模（这里就是链表长度）的关系：O(1)表示操作次数是固定常数，和输入规模无关；而O(n)表示操作次数随输入规模线性增长。这里的优化方法刚好满足前者的条件。

内容的提问来源于stack exchange，提问作者LearningToCode