This wiki.python.org https://wiki.python.org/moin/TimeComplexity关于某些数据结构的算法复杂性的页面说以下内容collections.deque object:
deque（双端队列）在内部表示为双向链表。 （好吧，为了提高效率，使用数组列表而不是对象列表。）两端都是可访问的，但即使查看中间也很慢，并且从中间添加或删除更慢。
两个问题：
1）添加到 a 的中间deque甚至可能吗？我没有看到任何方法可以做到这一点API https://docs.python.org/2/library/collections.html#collections.deque.
2）为什么删除（或添加）比中间的查找慢deque？它是一个双向链表，因此一旦找到要添加的对象，添加/删除应该是一个恒定时间的操作。
- 可以使用以下命令删除项目
remove()方法或del关键词。无法插入项目。 （API 文档中没有出现的插入的唯一可能方法是切片分配，这在deque.)
- 因为，正如描述所说，它实际上是一个双向链表的数组。因此，插入或删除内容可能需要将元素从一个数组移动到另一个数组。 （我没有看过实现，但我知道
deque在查找元素时使用步幅技术，并且我假设所使用的数组的大小与步幅长度相同，即 62。）您必须以常规方式移动大量内存list删除项目时也是如此，但至少所有内容都在一个块中，并且可以有效地移动。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
