[Tutor] lists [Twisted Linked Lists]

[Danny Yoo]

> You can also use the trick C programmers have used for years where they
> want very fast linked lists - create a large array then use the array
> index of the next item as the pointer. This also works in Python using a
> big list.


Hmmm... it might be good to see what linked lists would look like if we
DIDN't have pointers... *grin*


###
"""PrimitiveLinkedLists.py

Danny Yoo (dyoo@hkn.eecs.berkeley.edu)

This is a sample implementation of a linked list using an index as a way
of reference to another object.

This representation is twisted.  No sane person should use this in a
production system.  *grin*
"""


MAX_NODES = 1000
NODES = [0] * MAX_NODES
NEXTS = [0] * MAX_NODES
EMPTY_LIST = MAX_NODES


class LinkedListError(Exception): pass

def head(i):
    if i == EMPTY_LIST:
        raise LinkedListError, "Can't take the head of the empty list!"
    return NODES[i]

def tail(i):
    if i == EMPTY_LIST:
        raise LinkedListError, "Can't take the tail of the empty list!"
    return NEXTS[i]

def cons(obj, j):
    i = 0
    while i < MAX_NODES:
        if NEXTS[i] == 0: break
        i = i + 1
    if i == MAX_NODES:
        raise LinkedListError, "No more memory!"
    NEXTS[i] = j
    NODES[i] = obj
    return i

## Let's "waste" the first cell of memory so that the user doesn't fiddle
## with it.
assert (cons("sentinel", EMPTY_LIST) == 0)
###




The key is to understand that a linked list only requires a way of
"referring" to another element.  As long as we can conceptually refer to
an element, we have enough machinery to build linked lists, and being able
to refer to an list item by index is just enough to get things rolling:

###
>>> mylist = cons("This", cons("is", cons("a", cons("test", EMPTY_LIST))))
>>> head(mylist)
'This'
>>> head(tail(mylist))
'is'
>>> head(tail(tail(mylist)))
'a'
>>> head(tail(tail(tail(mylist))))
'test'
>>> head(tail(tail(tail(tail(mylist)))))
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "/usr/tmp/python-22546FBD", line 11, in head
__main__.LinkedListError: Can't take the head of the empty list!
>>> def empty(L): return L == EMPTY_LIST
...
>>> def length(L):
...     if empty(L): return 0
...     return 1 + length(tail(L))
...
>>> length(mylist)
4
###


So it's possible to do linked lists even without pointers.  The code above
doesn't use the trick that Alan mentioned, but it shouldn't be hard to
change it to optimize finding a new node to cons()truct.



Hope this helps!