Path: csiph.com!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: Chris Angelico <rosuav@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: PEP Request: Advanced Data Structures
Date: Sun, 17 Jul 2016 08:45:12 +1000
Lines: 45
Message-ID: <mailman.43.1468709115.2307.python-list@python.org>
References: <21fcec53-cf5b-4529-9790-63a1c46f534b@googlegroups.com> <CAPTjJmpQk9SwLRct-WpZMywFFLhX3A459eNzB5eHGVFyhBiDoA@mail.gmail.com> <mailman.42.1468707584.2307.python-list@python.org> <7af57bf9-72d7-4d0f-8db4-3ea02d701a5f@googlegroups.com> <CAPTjJmp2Bog+raRYVn+3GyjfLXY8=abEpVCCevjVB353DquNLQ@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <7af57bf9-72d7-4d0f-8db4-3ea02d701a5f@googlegroups.com>
Precedence: list
Xref: csiph.com comp.lang.python:111528

On Sun, Jul 17, 2016 at 8:33 AM, Shrey Desai <shrey.desai@gmail.com> wrote:
> Hi Chris, thanks for the reply. There's a couple of reasons why I would n=
eed a Linked List (and other data structures):
> - Education: the Linked List is a core data structure that CS undergradua=
tes (among others) use and study, so it is vital that they have hands on ac=
cess to them. A list is basically a dynamic array; the only property it sha=
res with a Linked List is that it's dynamic.
> - Development: the use of correct data structures is important when devel=
oping applications, especially for issues like scaling and efficiency. For =
instance, when working with polynomials, Linked Lists provide a great inter=
face 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 =3D self.tail =3D None
    def append(self, item):
        if self.tail: self.tail =3D self.tail.append(item)
        self.head =3D self.tail =3D _listitem(item)

class _listitem:
    def __init__(self, item):
        self.item =3D item
        self.next =3D None
    def append(self, item):
        self.next =3D 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