擅长:python、mysql、java
<p>Python列表是<a href="http://wiki.python.org/moin/TimeComplexity" rel="noreferrer">O(1) for operations at the end of the list</a>。如果您将以半连续的方式进行所有插入操作(与C类似,只将一个指针作为某种“游标”保留在列表的中间),那么只需使用两个Python列表就可以节省大量的工作量。一个列表显示光标前的内容,一个列表显示光标后的内容;移动光标涉及从一个列表中拖出下一个项目并将其附加到另一个列表中。这使您可以在光标位置进行任意O(1)插入,与创建一个完整的新数据结构相比,所需的工作量和重复性要少得多,从而可以重用许多现有的列表函数</p>
<p>但是,对于允许列表中有多个引用的完全通用的情况,您可能无法创建某种类型的链接列表</p>
<p><strong>编辑:</strong>您没有认真考虑对链接列表进行“二进制搜索”,是吗?二进制搜索在本质上是连续的数据结构上甚至没有意义</p>
<p>无论如何,如果你对线性时间搜索没问题,并且你的插入总是保持列表顺序而不重新排序,那么一个简单的链表可能就是你所需要的。如果你像迭代一样做大量的搜索,你应该考虑快速索引,如果需要诉诸的话,像树之类的东西会更好。p>