PEP Request: Advanced Data Structures

[cs at zip.com.au]

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>