How can I create a linked list in Python?

[Bruno Desthuilliers]

Re: How can I create a linked list in Python?

sturlamolden a écrit :

Bruno Desthuilliers wrote:
>
>

>>Have you considered using tuples ? If you go the FP way, why not use an
>>immutable type ?

>
>
Well, good question. Tuples are immutable, which means they are
immutable. So you cannot use a cursor to change an element inside the
list. So instead of changing the original items, you just replace the
cursor with a new reference. But it it is read only, sure, use tuples.
>
>
>

>>But how are Lisp lists implemented then ?-)

>
>
They are defunct binary trees, some think they are not really lists at
all :-)
>
Actually, nesting tuples or lists doesn't really duplicate Lisp cons,
as one can only create a stack-like object with the nesting. Python
really need a cons type like Lisp. I think it is time to write one, in
a plain C extension.
>

[Jorgen Grahn]

Re: How can I create a linked list in Python?

On Wed, 17 Jan 2007 10:11:40 +0100, Marc 'BlackJack' Rintsch <bj_666@gmx.net wrote:

In <1168983652.192 715.235580@a75g 2000cwd.googleg roups.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.dyn dns.org R'lyeh wgah'nagl fhtagn!

[sturlamolden]

Re: How can I create a linked list in Python?


Paul Rubin wrote:

But that's what Lisp does too.

Ok, I may have to reread Paul Graham's book on ANSI Common Lisp then.

[Neil Cerutti]

Re: How can I create a linked list in Python?

On 2007-01-18, sturlamolden <sturlamolden@y ahoo.nowrote:

>
Paul Rubin wrote:
>

>But that's what Lisp does too.

>
Ok, I may have to reread Paul Graham's book on ANSI Common Lisp
then.

Here's something silly I whipped up to play with.

r""" Lisp style singly-linked lists called llist.

"""

def consp(o):
return isinstance(o, Cons)

def car(c):
""" Return the car of a lisp-list. Undefined for nil. """
if null(c):
raise AttributeError( "nil has no cdr")
return c.car

def cdr(c):
""" Return the cdr of a lisp=list. """
if null(c):
return nil
return c.cdr

def cons(o, c):
""" Build a new cons cell from an object and a Cons. """
return Cons(o, c)

def null(c):
return c is nil

def rplaca(c, o):
c.car = o
return c

def rplacd(c, o):
c.cdr = o
return c

def llist(li):
""" Build a llist from a list. """
c = nil
for a in reversed(li):
if isinstance(a, list):
c = cons(llist(a), c)
else:
c = cons(a, c)
return c

class Cons(object):
def __init__(self, car, cdr):
self.car = car
self.cdr = cdr
def __repr__(self):
def helper(li, s):
if null(li):
return s + ")"
else:
return helper(cdr(li), s + " %s" % repr(car(li)))
return helper(self.cdr , "(" + repr(self.car))

class Nil(Cons):
def __init__(self):
Cons.__init__(s elf, None, None)
def __repr__(self):
return '()'

nil = Nil()

print cons(5, nil)
print cons(5, cons(3, nil))
print cons(cons(5, (cons(7, nil))), cons(cons(5, cons(3, nil)), nil))
print nil
print llist([1, ['a', 'b', 'c'], 2, 3])

There's lots more more stuff to add, but the fun wore out. I'd
like if it the cdr of nil could actually be nil, instead of None
with a special case in cdr, but I couldn't figure out a neat way
to do it.

--
Neil Cerutti
I've had a wonderful evening, but this wasn't it. --Groucho Marx

--
Posted via a free Usenet account from http://www.teranews.com

[Hendrik van Rooyen]

Re: How can I create a linked list in Python?

"Jorgen Grahn" <grahn+nntp@sni pabacken.dyndns .orgwrote:

>
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.

+1

The concept of storing a pointer that points to the "next thing" is so basic
that it will never go away. One meets it all time in chained buffer blocks,
in tag sorts, etc...

And if you add a pointer to the "previous thing" too, then adding or taking
something out of what could become a ring is a constant effort. Until you
run out of memory.

Ye Olde Universal Controlle Blocke:

- pointer to the start of data block
- length of allocated data block
- pointer to next control block
- pointer to previous control block
- next in pointer into data block
- next out pointer into data block
- optional length of data
- optional here starts or ends the lesson indicator

errrm... thats about it, unless you want a fast index too:

- pointer to first control block
- pointer to second control block
- pointer to third control block
....

Isn't it nice of python to hide all this stuff?

- Hendrik