PEP Request: Advanced Data Structures
cs at zip.com.au
cs at zip.com.au
Sat Jul 16 23:27:09 EDT 2016
On 17Jul2016 12:43, Chris Angelico <rosuav at gmail.com> wrote:
>On Sun, Jul 17, 2016 at 12:33 PM, Paul Rubin <no.email at nospam.invalid> 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.
>
>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 <cs at zip.com.au>
More information about the Python-list
mailing list