How can I create a linked list in Python?

[Jorgen Grahn]

On Wed, 17 Jan 2007 10:11:40 +0100, Marc 'BlackJack' Rintsch <bj_666 at gmx.net> wrote:
> In <1168983652.192715.235580 at a75g2000cwd.googlegroups.com>, bearophileHUGS
> wrote:
>
>> In CPython they are dynamic arrays, they aren't lists. Try adding
>> elements at the beginning of a list compared to adding elements at the
>> beginning or in the middle of a python "list" and you will see the
>> efficiency differences.
>
> Python has a list type without the "s, it's a real list.  Don't confuse
> the *ADT list* with *linked lists* which are just one implementation of
> the ADT list.

I think the terminology is already so confused that you cannot say "list"
unless context implies that you mean e.g. a Python list. For example, SML (a
language favored by people interested in types and type systems) uses the
term "list", but a SML "list" really acts like a stack.

FWIW, I oppose the idea (paraphrased from further up the thread) that linked
lists and other data structures are obsolete and dying concepts, obsoleted
by Python and other modern languages.

99% of the time. a Python list is the right tool for the job, but that's
only because we have CPU cycles to spare and the 'n' in our 'O(n)' is
limited. You cannot call yourself a computer scientist without understanding
things like linked lists.  No other data structure has the same
characteristics (good and bad) as that one. Or those two, really.

I mean, what would Knuth say? ;-)

/Jorgen

-- 
  // Jorgen Grahn <grahn@        Ph'nglui mglw'nafh Cthulhu
\X/     snipabacken.dyndns.org>  R'lyeh wgah'nagl fhtagn!