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]

Dongsheng Ruan wrote:

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:

Dongsheng Ruan wrote:

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.

"Gary Herron" <gh*****@island training.comwro te in message
news:ma******** *************** *************** *@python.org...

Dongsheng Ruan wrote:

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

Dongsheng Ruan wrote:

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]

At Tuesday 16/1/2007 17:07, Dongsheng Ruan wrote:

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

On 1月17日, 上�9时55分 , Gabriel Genellina
<gagsl...@yahoo .com.arwrote:

At Tuesday 16/1/2007 17:07, Dongsheng Ruan wrote:

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

[sturlamolden]

Bruno Desthuilliers wrote:

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.