PEP Request: Advanced Data Structures

[MRAB]

On 2016-07-17 03:33, Paul Rubin wrote:
> Chris Angelico <rosuav at gmail.com> writes:
>>> keep a reference to an element deep in the list, and insert a new
>>> element in O(1) time at that point.
>> at the C level, wouldn't tracing the links cost massively more than
>> the occasional insertion too? I'm not sure O(1) is of value at any
>> size, if the costs of all your other operations go up.
>
> I think the idea is that you're already deep in the list when you decide
> to insert an element or do other surgery on the list.  An example might
> be a lookup table with linear search, where you want to bring the LRU
> item to the front of the list after finding it.  Really though, that's
> an ugly thing to be doing in any language, and it definitely isn't
> something that comes up much in Python.
>
I once sped up lookups on a doubly-linked list by adding a dict that 
would take me straight to the appropriate node. This was in C, though.