On 17Jul2016 12:43, Chris Angelico <ros...@gmail.com> wrote:
On Sun, Jul 17, 2016 at 12:33 PM, Paul Rubin <no.email@nospam.invalid> 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.
Right, but how did you *get* that deep into the list? By following a
chain of pointers. That's a relatively costly operation, so the
benefit of not having to move all the following elements is damaged
some by the cost of chasing pointers to get there in the first place.
No, you're assuming too much here. Consider:
LL = LinkedList()
item = LL.insert( (some, tuple, value) )
... do lots of stuff with the list ...
... now item refers to something that might be anywhere ...
item.add_after( (context, for, a, new, item, in , the, list) )
...
and any number of other scenarios of similar nature: note a node in the list
and get to done things at or near that node at an arbirary other time.
This applies to _any_ graph like data structure where nodes would have to be
found by traversal.
Anyway, I'm not arguing that Pythons basic list type doesn't address a great
many needs. I'm arguing that no one size fits all. The core strength of a
linked list is O(1) insertion at any point, provided you have a reference to
that point. Whether that is enough benefit depends on the use case.
Cheers,
Cameron Simpson <c...@zip.com.au>
--
https://mail.python.org/mailman/listinfo/python-list
