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]

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

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]

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

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]

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

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" <gherron@island training.comwro te in message
news:mailman.27 91.1168975031.3 2031.python-list@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@lycos.com]

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

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@gmail.com]

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


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]

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

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]

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

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]

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

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]

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


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.

[Marc 'BlackJack' Rintsch]

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

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.

Ciao,
Marc 'BlackJack' Rintsch

[bearophileHUGS@lycos.com]

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

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]

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

sturlamolden a écrit :

Bruno Desthuilliers wrote:
>
>

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

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

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


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.

[Paul Rubin]

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

"sturlamold en" <sturlamolden@y ahoo.nowrites:

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.