[Tutor] lists [Linked lists]

[Danny Yoo]

On Tue, 23 Apr 2002, Victor R. Cardona wrote:

> Linked lists are created using pointers in lanquages like C and C++.
> Nodes are accessed in a linear fashion. However, the design makes the
> removal or insertion of nodes very efficient.
>
> You do not need linked lists in Python. In fact it would be very
> difficult to create (if not impossible), because Python does not have
> pointers. A standard list in Python should give you the functionality of
> a linked list, and is much easier to create :-)

Actually, it's not so hard.


###
class Cons:
    def __init__(self, head, tail):
        self.head, self.tail = head, tail

NULL_LIST = None
###

Done.  *grin*



Here's how we can work with them:

###
>>> mylist = Cons(1, Cons(2, Cons(3, NULL_LIST)))
>>> mylist
<__main__.Cons instance at 0x81156ec>
###

'mylist' is now a list of three elements.  We can get at the value of the
head of our list by doing a elements when we yank on the "head" of our
list.

###
>>> mylist.head
1
###

And to get to the other elements in a linked list, we just start dragging
it by its tail!

###
>>> mylist.tail
<__main__.Cons instance at 0x8112b2c>
>>> mylist.tail.head
2
>>> mylist.tail.tail.head
3
###

We stop pulling at the tail when there's no more tail to yank.

###
>>> mylist.tail.tail.tail
>>> mylist.tail.tail.tail.head
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
AttributeError: 'None' object has no attribute 'head'
###

Linked lists are nice because they're conceptually simple once you see a
picture of them.  Think LEGO, and how the pieces fit together, and that's
a good idea of how linked lists work.  *grin*



Please feel free to ask more questions about this.  Hope this helps!