<p>这里有一个<a href="http://www.algorithm.co.il/blogs/index.php/programming/python/lru-cache-solution-a-case-for-linked-lists-in-python/" rel="noreferrer">blog post</a>分享你的痛苦。它包括链表的实现和性能比较</p>
<hr/>
<p>也许<code>blist</code>会更好,但是(从<a href="http://pypi.python.org/pypi/blist/0.9.4" rel="noreferrer">here</a>)</p>
<blockquote>
<p>The use cases where the BList is
slightly slower than Python's list are
as follows (O(log n) vs. O(1)):</p>
<ol>
<li>A large list that never changes length.</li>
<li>A large lists where inserts and deletes are only at the end of the
list (LIFO).</li>
</ol>
<p>With that disclaimer out of the way,
here are some of the use cases where
the BLists is dramatically faster than
the built-in list:</p>
<ol>
<li>Insertion into or removal from a large list (O(log n) vs. O(n))</li>
<li>Taking large slices of large lists (O(log n) vs O(n))</li>
<li>Making shallow copies of large lists (O(1) vs. O(n))</li>
<li>Changing large slices of large lists (O(log n + log k) vs. O(n + k))</li>
<li>Multiplying a list to make a large, sparse list (O(log k) vs.
O(kn))</li>
</ol>
</blockquote>
<p>请注意,它实际上是作为B+树实现的,允许所有这些操作都有很好的性能</p>