How can I create a linked list in Python?

[Neil Cerutti]

On 2007-01-18, sturlamolden <sturlamolden at yahoo.no> wrote:
>
> 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__(self, 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