PEP Request: Advanced Data Structures

[Paul Rubin]

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.