PEP Request: Advanced Data Structures

[Chris Angelico]

On Sun, Jul 17, 2016 at 1:27 PM,  <cs at zip.com.au> wrote:
>> 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.
>

Sure, that makes sense. The ability to hang onto a "list position" is
a useful one, I don't deny that. (Indices work if all you ever do is
append, but your add_after will invalidate any indices after that.) I
just very much doubt that the linked list will afford any overall
performance improvement over the standard CPython built-in list object
- and if it does, you're definitely in the realm of special-purpose
code for a specific situation. And there's nothing wrong with that.

Having not myself had a good early grounding in data structure design,
I think it's something worth teaching. And Python's fine at doing that
- the concepts of a linked list translate nicely into Python objects
and attributes - even though it'll never actually be something Python
needs. Once you've learned what the different fundamental structures
are, you'll have a better understanding of what's going on (for
instance, knowing the advantages and critical disadvantages of
hashtables like CPython's dict), and possibly know when to roll your
own instead of using someone else's (knowing that "lst.insert(0,
lst.pop(idx))" is slow, you might instead "lst.append(lst.pop(idx))"
and have your list in reverse order - a good start, but maybe you'd
decide to go linked-list anyway).

But for most jobs, just think in terms of abstract data structures,
and trust the language to do the details.

ChrisA