寻找比deque更快的、仅支持O(1)时间头部前置插入的数据结构

嘿，我来帮你拆解这个问题。首先得说，你碰到的测试结果完全符合预期——Python的deque本身就是为高效首尾操作量身优化的，而自定义链表因为单次插入的额外开销太高，自然跑不过它。

为什么链表比deque慢这么多？ #

你的测试数据背后有明确的性能逻辑：

• Python的deque采用**分段连续内存（块实现）**设计，appendleft操作大多时候只是在当前内存块的头部位置写入数据，只有当块满了才会批量申请新的内存块——这种批量分配的开销远小于每次创建单个对象的零散开销。
• 而你的链表实现，每次prepend都要实例化一个Node对象，这涉及到Python的对象初始化、属性赋值，还有零散的内存分配（每个Node的内存地址不连续），这些琐碎的开销累积100万次，就会被deque的批量优化远远甩开。

有没有比deque更快的仅前置插入结构？ #

在Python生态里，deque.appendleft已经是通用场景下最快的前置插入实现之一了。不过如果你的需求非常特殊（比如不需要中间访问、只需要最终转成列表），还有几个可以尝试的优化方向：

1. 反向使用列表（append代替prepend，最后反转）

这是个取巧但高效的思路：列表的append操作是均摊O(1)时间，而且因为是连续内存预分配，速度极快。你可以先把所有元素尾插到列表，最后再反转得到正确顺序，整体速度会比deque.appendleft还快：

class ReverseListFrontOnly:
    def __init__(self):
        self.data = []
    
    def prepend(self, value):
        self.data.append(value)  # 用高速尾插代替前置插入
    
    def get_list(self):
        return self.data[::-1]  # 最后反转得到正确顺序

2. 针对特定类型使用array.array

如果你的元素是同一基础类型（比如整数、浮点数），可以用array.array代替列表——它的内存开销更小，操作速度也会略快：

import array

class TypedReverseFrontOnly:
    def __init__(self):
        self.data = array.array('i')  # 'i'表示存储整数类型
    
    def prepend(self, value):
        self.data.append(value)
    
    def get_list(self):
        return self.data[::-1].tolist()

3. 去掉不必要的对象封装

你的FrontOnlyDeque类其实是对deque的冗余封装，直接使用原生deque能省掉一点点（虽少但存在）的属性访问开销：

# 直接使用原生deque，跳过封装类
raw_deque = deque()
start = time.time()
for i in range(1000000):
    raw_deque.appendleft(i)
print(f"Raw deque prepend time: {time.time() - start} seconds")

你提供的测试代码整理（修正语法+格式优化） #

我把你的代码修正了语法问题，并调整了可读性：

import time
from collections import deque

# 链表实现
class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def get_list(self):
        current = self.head
        result = []
        while current:
            result.append(current.value)
            current = current.next
        return result

# 基于deque的仅前置实现
class FrontOnlyDeque:
    def __init__(self):
        self.deque = deque()

    def prepend(self, value):
        self.deque.appendleft(value)

    def get_list(self):
        return list(self.deque)

# 通用计时函数
def time_operations(impl, n):
    start_time = time.time()
    for i in range(n):
        impl.prepend(i)
    return time.time() - start_time

# 测试100万次前置插入
n = 1000000

# 链表测试
linked_list = LinkedList()
linked_list_time = time_operations(linked_list, n)

# Deque测试
deque_impl = FrontOnlyDeque()
deque_time = time_operations(deque_impl, n)

print(f"Linked List prepend time: {linked_list_time} seconds")
print(f"Deque prepend time: {deque_time} seconds")

最终总结 #

• 通用场景下，deque.appendleft已经是Python里的最优解，几乎找不到更高效的通用仅前置插入实现。
• 如果可以接受“先尾插再反转”的流程，列表的append+reverse会比deque更快。
• 自定义链表在Python里几乎不可能超越deque，因为对象创建和零散内存分配的开销是无法避免的。

内容来源于stack exchange