CPython的deque被实现为64项的双向链表大小的"块"(阵列).除了链表两端的那些块外,这些块都是满的.在IIUC中,当pop/ popleft删除块中的最后一项时,块被释放; 当append/ appendleft尝试添加新项目并且相关块已满时,将分配它们.
我理解使用链接列表而不是链接项列表所列出的优点:
malloc/ free添加/删除的每个项目执行/的运行时成本但是为什么不是首先使用单个动态大小的圆形数组而不是双链表呢？
AFAICT,圆形阵列将保留所有上述优点,并维持(atortized)成本pop*/ append*at O(1)(通过分配,就像在中list).此外,它还可以提高从当前O(n)到索引的索引查找成本O(1).循环数组也可以更简单地实现,因为它可以重用大部分list实现.
我可以在C++这样的语言中看到支持链表的论证,其中可以O(1)使用指针或迭代器从中间删除项目; 但是,python deque没有API来执行此操作.