[Tutor] Re: Linked Lists

[Daniel Yoo]

On Tue, 20 Mar 2001, VanL wrote:

> One person said:
> > Given that lists are built into Python, and much more powerfull
> than this besides,  it is of cource a pointless class.
> 
> Another said:
> > I find I never use linked lists in Python by the way, always just
> Python
> > lists. And so many other standard hard algorithms and data
> structures become
> > trivial when you have dictionaries available :).
> 
> Yeah, the native Python lists support a log more operations.  But I
> was under the impression that linked lists
> and lists were completely different data structures.

They are different data structures, because certain operations will take
less time, like insertion.  Insertion in a linked list takes "constant"
time, so it's very easy to support insertions anywhere in your structure.

Python lists, too, support arbitrary insertion.  I haven't taken a look at
the data structure, but I'm assuming that they've implemented it as a
dynamic array that grows if it needs to.  If this is true, then inserting
at the end of a list is easy, but inserting anywhere else is costly: we'd
need to migrate all the elements to the right by one index.  So that's one
place where linked lists win.

There are always tradeoffs --- if you're doing to do arbitrary insertion,
you'll find the linked list useful.  However, remember that linked lists
don't support arbitrary indexing --- in order to get the fifth element of
a linked list, we have "next().next().next().next()".  Whew!

Practically speaking, I think that dynamic arrays are more useful than
linked lists, but that's just an opinion.


> In a similar vein, how would you use Python's native data types to
> represent a linked list?

What you had, with the class structure, is a good way to represent linked
lists.  Another way to do it is to use a paired structure, a la Scheme:

###
>>> def cons(a, b):
...     return [a, b]
...
>>> def first(pair):
...     return pair[0]
...
>>> def rest(pair):
...     return pair[1]
...
>>> cons(1, cons(2, cons(3, cons(4, None))))
[1, [2, [3, [4, None]]]]
>>> myLinkedList = cons('a', cons('b', cons('c', None)))
>>> first(rest(rest(myLinkedList)))
'c'
###

This is an alternative way to develop linked lists.  It might look funny
to have all those nested lists, but it's very similar to the previous
class definition.

Hope this helps!