On 2016-07-17 03:33, Paul Rubin wrote:
Chris Angelico <ros...@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.
--
https://mail.python.org/mailman/listinfo/python-list
