[Tutor] Linked Lists

[Scott Widney]

> This time I am here with a more concrete problem. I want to 
> learn about linked lists in python such that I can say -
> 
> mylist = linked() 
> #initialize list, that is have a class named linked
> 
> and have following methods (or functions if you will) 
> 
> addbeginning(x) #to add an element at beginning
> addposition(x, pos) #to add an elemnt at specified position
> addend(x) #to add at end
> print() #to print 
> sort() #to sort
> search() #to search
> 
> ... and so forth.

If all you need simple singly-linked-list functionality for a project you're
working on, let me say -- "Don't reinvent the wheel!". Python's built-in
[list] already provides you with the functionality you mentioned. Try this
is the interpreter:

Python 2.2.2 (#37, Oct 14 2002, 17:02:34) [MSC 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> dir(list)
['__add__', '__class__', '__contains__', '__delattr__', '__delitem__',
'__delslice__', '__doc__', '__eq__', '__ge__', '__getattribute__',
'__getitem__', '__getslice__', '__gt__', '__hash__', '__iadd__', '__imul__',
'__init__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__',
'__reduce__', '__repr__', '__rmul__', '__setattr__', '__setitem__',
'__setslice__', '__str__', 'append', 'count', 'extend', 'index', 'insert',
'pop', 'remove', 'reverse', 'sort']
>>>

Look at the last few words in that list. They're the methods that every list
inherits. Let's look at the functions you mention and show how they are done
with Python lists. We'll start with a simple list...

>>> L = [1, 2, 3, 4]

# addbeginning(x) add an element at beginning
>>> L.insert(0, 'a')
>>> L
['a', 1, 2, 3, 4]

# addposition(x, pos) add an elemnt at specified position
>>> L.insert(2, 'b')
>>> L
['a', 1, 'b', 2, 3, 4]

# addend(x) add at end
>>> L.append('foo')
>>> L
['a', 1, 'b', 2, 3, 4, 'foo']

# print() to print
>>> print L
['a', 1, 'b', 2, 3, 4, 'foo']

# sort() #to sort
>>> L.sort()
>>> L
[1, 2, 3, 4, 'a', 'b', 'foo']

# search() #to search
>>> L.index('foo')
6
>>> L[6]
'foo'
>>> L.index('bar')
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
ValueError: list.index(x): x not in list

There's also slicing, concatenating, popping, etc.

>>> L.insert(3, 'r')
>>> L[1:4]
['b', 'a', 'r']
>>> L
['foo', 'b', 'a', 'r', 4, 3, 2, 1]
>>> L[4:] + L[:4]
[4, 3, 2, 1, 'foo', 'b', 'a', 'r']
>>> L.insert(0, L.pop())
>>> L.insert(0, L.pop())
>>> L.insert(0, L.pop())
>>> L.insert(0, L.pop())
>>> L
[4, 3, 2, 1, 'foo', 'b', 'a', 'r']
>>> L.append(L.pop(0))
>>> L.append(L.pop(0))
>>> L.append(L.pop(0))
>>> L.append(L.pop(0))
>>> L
['foo', 'b', 'a', 'r', 4, 3, 2, 1]
>>> L.insert(0, L.pop())
>>> L.insert(1, L.pop())
>>> L.insert(2, L.pop())
>>> L.insert(3, L.pop())
>>> L
[1, 2, 3, 4, 'foo', 'b', 'a', 'r']

Try typing: help(list) at the >>> prompt for more information.

Now if it were a doubly-linked list, I think that would be another
matter....


Hope this helps!
Scott