http://www.orangecube.net/python-time-complexity

本文中，’n’代表容器中元素的数量，’k’代表参数的值，或者参数的数量。

列表（list）

以完全随机的列表考虑平均情况。列表是以数组（Array）实现的。最大的开销发生在超过当前分配大小的增长，这种情况下所有元素都需要移动；或者是在起始位置附近插入或者删除元素，这种情况下所有在该位置后面的元素都需要移动。如果你需要在一个队列的两端进行增删的操作，应当使用collections.deque（双向队列）

双向队列（collections.deque）

deque（double-ended queue，双向队列）是以双向链表的形式实现的(Well, a list of arrays rather than objects, for greater efficiency)。双向队列的两端都是可达的，但从查找队列中间的元素较为缓慢，增删元素就更慢了。