为何Python中deque实现的BFS代码比list+pop(0)更慢？

理论上deque.popleft()操作的时间复杂度为O(1)，而list.pop(0)为O(n)，但在LeetCode的BFS问题测试中，使用list的代码击败了30%的提交，而使用deque的仅击败6%。以下是两段实现同一BFS问题的代码：

使用deque的实现 #

if not root:
    return root
lev = 0
dummy = Node(0)
prev = dummy

q = deque()
q.append((root, 0))

while q:
    curr = q.popleft()
    print(curr[0].val)
    if curr[1] != lev:
        prev.next = None
        prev = curr[0]
        lev = curr[1]
    else:
        prev.next = curr[0]
        prev = curr[0]
    
    if curr[0].left:
        q.append((curr[0].left, curr[1] + 1))
    if curr[0].right:
        q.append((curr[0].right, curr[1] + 1))


prev.next = None
return dummy.next

使用普通list的实现 #

if not root:
    return root
lev = 0
dummy = Node(0)
prev = dummy

q = []
q.append((root, 0))

while q:
    curr = q.pop(0)
    print(curr[0].val)
    if curr[1] != lev:
        prev.next = None
        prev = curr[0]
        lev = curr[1]
    else:
        prev.next = curr[0]
        prev = curr[0]
    
    if curr[0].left:
        q.append((curr[0].left, curr[1] + 1))
    if curr[0].right:
        q.append((curr[0].right, curr[1] + 1))


prev.next = None
return dummy.next

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