PEP Request: Advanced Data Structures

[Chris Angelico]

On Sun, Jul 17, 2016 at 8:33 AM, Shrey Desai <shrey.desai at gmail.com> wrote:
> Hi Chris, thanks for the reply. There's a couple of reasons why I would need a Linked List (and other data structures):
> - Education: the Linked List is a core data structure that CS undergraduates (among others) use and study, so it is vital that they have hands on access to them. A list is basically a dynamic array; the only property it shares with a Linked List is that it's dynamic.
> - Development: the use of correct data structures is important when developing applications, especially for issues like scaling and efficiency. For instance, when working with polynomials, Linked Lists provide a great interface to access and edit them.
>

For education, I wouldn't worry too much about performance or edge
cases, and just use something really simple:

class LinkedList:
    def __init__(self):
        self.head = self.tail = None
    def append(self, item):
        if self.tail: self.tail = self.tail.append(item)
        self.head = self.tail = _listitem(item)

class _listitem:
    def __init__(self, item):
        self.item = item
        self.next = None
    def append(self, item):
        self.next = type(self)(item)
        return self.next

Then add other methods as you teach them (iteration, item removal,
etc). Performance is probably terrible, but who cares? You won't
notice it in sample code.

For development, I'm pretty sure the native CPython list type is going
to out-perform anything you could implement as a linked list. Even
more so if you're using PyPy, where it knows how to optimize the list
(but won't necessarily be able to optimize your type). Instead of
messing around with data types, just implement your code using the
most simple and obvious style, and worry about
performance/scaling/efficiency only if and when you find out that
that's a bottleneck. I very much doubt that it will be.

ChrisA