如何以O(1)时间复杂度删除Python列表首元素？del l[0]可行吗？

del l[0]无法达到O(1)时间复杂度 #

Python的内置列表本质是动态数组，依赖连续内存空间存储元素。执行del l[0]时，必须将索引0之后的所有元素依次向前移动一位来填补空缺，这个操作的时间复杂度为O(n)，完全不符合常数时间的要求。

满足O(1)删除首元素的实现方案 #

要实现常数时间删除首元素，需要采用基于链表的结构，具体有两种可行方式：

1. 自定义单链表 #

自己实现单链表结构，删除头节点仅需修改头指针的指向，操作耗时固定为O(1)：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def add_front(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
    
    def remove_front(self):
        if not self.head:
            return None
        removed_val = self.head.value
        self.head = self.head.next
        return removed_val

调用remove_front()方法即可在O(1)时间内删除首元素。

2. 使用collections.deque #

Python标准库中的deque基于双向链表实现，它的popleft()方法天然支持O(1)时间删除首元素，这是最简便的方案（该结构不属于列表预定义函数范畴）：

from collections import deque

dq = deque([1, 2, 3, 4])
dq.popleft()  # 常数时间删除首元素

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