How can I create a linked list in Python?

[Dongsheng Ruan]

with a cell class like this:

#!/usr/bin/python

import sys

class Cell:

def __init__( self, data, next=None ):
self.data = data
self.next = next

def __str__( self ):
return str( self.data )

def echo( self ):
print self.__str__()

 

[Gary Herron]

with a cell class like this:

#!/usr/bin/python

import sys

class Cell:

def __init__( self, data, next=None ):
self.data = data
self.next = next

def __str__( self ):
return str( self.data )

def echo( self ):
print self.__str__()

If you really want a list (as Python defines a list - with all the methods) then you should use Python's lists. They are quite efficient and convenient:

l = [Cell(1), Cell(2), Cell(3)]

However, if what you want is each cell to refer to a next cell (which after all is what a linked list does), then you already have it with the next attribute. (In other languages you might implement 'next' as a pointer, while in Python we call it a reference -- but it amounts to the same thing.) Create it this way:

c = Cell(3)
b = Cell(2, c)
a = Cell(1, b)

or

a = Cell(1, Cell(2, Cell(3)))

However, I'll repeat this: The concept of a linked list if a figment of languages with pointer data types. Python abstracts that by allowing attributes to contain references to other objects. However, you're much better off if you can use Python's list data structure rather than try to emulate an outdated concept in a modern language.

Gary Herron

 

[azrael]

How can I implement a linked list like the implementations in c with
struct-s and arrays (or pointers).
to simbolize the working principe



Gary Herron je napisao/la:

with a cell class like this:

#!/usr/bin/python

import sys

class Cell:

def __init__( self, data, next=None ):
self.data = data
self.next = next

def __str__( self ):
return str( self.data )

def echo( self ):
print self.__str__()

If you really want a list (as Python defines a list - with all the methods) then you should use Python's lists. They are quite efficient and convenient:

l = [Cell(1), Cell(2), Cell(3)]

However, if what you want is each cell to refer to a next cell (which after all is what a linked list does), then you already have it with the next attribute. (In other languages you might implement 'next' as a pointer, while in Python we call it a reference -- but it amounts to the same thing.) Create it this way:

c = Cell(3)
b = Cell(2, c)
a = Cell(1, b)

or

a = Cell(1, Cell(2, Cell(3)))

However, I'll repeat this: The concept of a linked list if a figment of languages with pointer data types. Python abstracts that by allowing attributes to contain references to other objects. However, you're much better off if you can use Python's list data structure rather than try to emulate an outdated concept in a modern language.

Gary Herron

 

[Dongsheng Ruan]

Thanks for your kindly help.
I am new CS student taking datat structure and algorithms with AHO's book
with the same title.

The book is done in Pascal, which might be an outdated language.

However, my instructor probably wants us to understand the list ADT better
by not using the built in list in Python.

with a cell class like this:

#!/usr/bin/python

import sys

class Cell:

def __init__( self, data, next=None ):
self.data = data
self.next = next

def __str__( self ):
return str( self.data )

def echo( self ):
print self.__str__()

If you really want a list (as Python defines a list - with all the
methods) then you should use Python's lists. They are quite efficient and
convenient:

l = [Cell(1), Cell(2), Cell(3)]

However, if what you want is each cell to refer to a next cell (which
after all is what a linked list does), then you already have it with the
next attribute. (In other languages you might implement 'next' as a
pointer, while in Python we call it a reference -- but it amounts to the
same thing.) Create it this way:

c = Cell(3)
b = Cell(2, c) a = Cell(1, b)

or

a = Cell(1, Cell(2, Cell(3)))

However, I'll repeat this: The concept of a linked list if a figment of
languages with pointer data types. Python abstracts that by allowing
attributes to contain references to other objects. However, you're much
better off if you can use Python's list data structure rather than try to
emulate an outdated concept in a modern language.

Gary Herron

 

[bearophileHUGS]

Gary Herron:

If you really want a list (as Python defines a list - with all the methods) then you should use Python's lists. They are quite efficient and convenient:

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.

The concept of a linked list if a figment of languages with pointer data types.

You may manage a list with a language without pointers, like *basic*
(for students) Scheme. Creating a List data type for Python is possible
too, without true pointer like ones found in Pascal.

However, you're much better off if you can use Python's list data structure rather
than try to emulate an outdated concept in a modern language.

Simple lists today aren't much efficient because their pointers break
cache locality, they may cause cache trashing, so they may be slower
than smarter and more localized structures, like short double linked
arrays, etc.
But I think lists aren't outdated, they are a mathematical concept too,
and they are quite used still.
If you want to learn some Computer Science, it's positive to know what
linked lists are.
If you want to implement algorithms that must process LOT of things,
you may find pointers and lists quite necessary today too, see for
example:
http://citeseer.ist.psu.edu/knuth00dancing.html
http://en.wikipedia.org/wiki/Dancing_Links
Python and its data structures aren't the right solutions for all
purposes.

Bye,
bearophile

 

[ray223]

with a cell class like this:

#!/usr/bin/python

import sys

class Cell:

def __init__( self, data, next=None ):
self.data = data
self.next = next

def __str__( self ):
return str( self.data )

def echo( self ):
print self.__str__()

Hi,

The "How to Think Like a Computer Scientist" free book has a chapter
just for this topic:

http://greenteapress.com/thinkpython/html/chap17.html

Regards,

Ray Smith
http://RaymondSmith.com

 

[Bruno Desthuilliers]

Dongsheng Ruan a écrit :

Thanks for your kindly help.
I am new CS student taking datat structure and algorithms with AHO's book
with the same title.

The book is done in Pascal, which might be an outdated language.

Yes, somehow - but note, that linked lists are the central data
structure of Lisp, which is probably the older programming language
still in use...

Implementing linked lists in Python is not a great deal - it just
doesn't make much sens. It's IMHO much more interesting to learn this
kind of stuff with a low-level language like C or Pascal.

However, my instructor probably wants us to understand the list ADT better
by not using the built in list in Python.

Indeed !-)

 

[Gabriel Genellina]

Thanks for your kindly help.
I am new CS student taking datat structure and algorithms with AHO's book
with the same title.

The book is done in Pascal, which might be an outdated language.

However, my instructor probably wants us to understand the list ADT better
by not using the built in list in Python.

Just use the same structure as the book. Instead of nil, use None;
instead of new(P) where P:^Foo, use P=Foo(); records become classes
without methods...

Anyway, implementing linked lists, dictionaries, and other basic
structures in a language like Pascal, or C -which doesn't have them
natively- may be a good learning exercise. But doing that in Python
is not a good idea. Of course, using Python in a second or third
algorithms course *is* a good idea, because you can forget about
these implementation details and concentrate on the algorithms.


--
Gabriel Genellina
Softlab SRL






__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya!
http://www.yahoo.com.ar/respuestas

 

[kernel1983]

Every language has its own way to do the business!
Python has a more abstract data type as the common tools.
Just do things in pythonic way!

 

[sturlamolden]

Implementing linked lists in Python is not a great deal - it just
doesn't make much sens.

It does make sence, as there are memory constraints related to it.
Python lists are arrays under the hood. This is deliberately. Dynamic
arrays grows faster than lists for the common "short list" case, and
because indexing an array is O(1) instead of O(N) as it is for linked
lists. You can easily break the performance of Python lists by adding
objects in the middle of a list or appending objects to the end of long
lists. At some point the list can not grow larger by a simple realloc,
as it would crash with other objects on the heap, and the whole list
must be replaced by a brand new memory segment.

Also linked lists are an interesting theoretical concept in computer
science. Understanding how dynamic datastructures work and their
limitations are a key to understanding algorithms and how computers
work in general.

The simplest way of implementing a linked list in Python is nesting
Python lists. One may e.g. type something like:

#create
mylist = []

# push
mylist = [someobject, mylist]

# pop
mylist = mylist[1]

#iterate
cur = mylist
while cur:
cur = cur[1]

This is actually single linked list that behaves like a stack, i.e. the
last added element sits on top and one needs to iterate the list to get
to the first.

Those who know Lisp should be familiar with the concept of creating
dynamic data structures form nesting lists; it may be more unfamiliar
to C and Pascal programmers, as these languages do not support such
constructs. In Python one may also use a more explicit solution
involving classes for expressing linked lists, which would be more
familiar to C and Pascal programmers. In any case, making linked lists
are trivial in Python.

 

[Marc 'BlackJack' Rintsch]

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.

Ciao,
Marc 'BlackJack' Rintsch

 

[bearophileHUGS]

Marc 'BlackJack' Rintsch:

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.

Right, I was mostly talking about (single/double) linked lists

Bye,
bearophile

 

[Bruno Desthuilliers]

sturlamolden a écrit :

Bruno Desthuilliers wrote:




It does make sence,

Oh Yec ?-)

sorry...

as there are memory constraints related to it.
Python lists are arrays under the hood. This is deliberately. Dynamic
arrays grows faster than lists for the common "short list" case, and
because indexing an array is O(1) instead of O(N) as it is for linked
lists. You can easily break the performance of Python lists by adding
objects in the middle of a list or appending objects to the end of long
lists. At some point the list can not grow larger by a simple realloc,
as it would crash with other objects on the heap, and the whole list
must be replaced by a brand new memory segment.

That's certainly true - from a technical POV -, but I never had such a
problem in now 7 years of Python programming.

Also linked lists are an interesting theoretical concept in computer
science. Understanding how dynamic datastructures work and their
limitations are a key to understanding algorithms and how computers
work in general.

Indeed. Did I say otherwise ?

The simplest way of implementing a linked list in Python is nesting
Python lists.

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

(snip)

Those who know Lisp should be familiar with the concept of creating
dynamic data structures form nesting lists; it may be more unfamiliar
to C and Pascal programmers, as these languages do not support such
constructs.

But how are Lisp lists implemented then ?-)

I do totally agree that Lispish lists are something one should learn,
but starting with a low-level procedural language with 'manual' memory
management is certainly a Good Thing(tm). Well, IMHO at least (FWIW,
having first learned to implement linked lists in C and Pascal, I had no
problem understanding Lisp's list).

In Python one may also use a more explicit solution
involving classes for expressing linked lists, which would be more
familiar to C and Pascal programmers. In any case, making linked lists
are trivial in Python.

Yes again. Hence my remark...

 

[sturlamolden]

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.

 

[Paul Rubin]

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.

But that's what Lisp does too. As the poet said:

One thing the average language lacks
Is programmed use of push-down stacks.
But LISP provides this feature free:
A stack - you guessed it - is a tree.
An empty stack is simply NIL.
In order, then, the stack to fill
A CONS will push things on the top;
To empty it, a CDR will
Behave exactly like a pop.
A simple CAR will get you back
The last thing you pushed on the stack;
An empty stack's detectable
By testing with the function NULL.
Thus even should a LISPer lose
With PROGs and GOs, RETURNs and DOs,
He need his mind not overtax
To implement recursive hacks:
He'll utilize this clever ruse
Of using trees as moby stacks.

(http://www.gotlisp.com/lambda/lambda.txt)

All Python needs is a way of displaying the lists as (a b c) instead
of [a, [b, [c, None]]], and that can be done in pure Python.

 

[Bruno Desthuilliers]

sturlamolden a écrit :

Bruno Desthuilliers wrote:




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.





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]

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

 

[sturlamolden]

But that's what Lisp does too.

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

 

[Neil Cerutti]

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.

 

[Hendrik van Rooyen]

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