[Tutor] Linked Lists

[Sean 'Shaleh' Perry]

On Tuesday 26 August 2003 09:37, Sukrit K Mehra wrote:
>
> 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.
>

ok, obviously (right?) you know about Python's built in list construct.

mylist = list() # or [] for the older than 2.3 releases
mylist.append('123')
mylist.insert(3, 'bar')
print mylist
mylist.sort() # note this is destructive and does NOT return the list
mylist.index('123')

So, that said, it can still be fun to make you own stuff.

> Questions
>
> I am having trouble with the basic structure of the list. I
> understand that you need a node, so I have a node
> class Node:
>     def __init__(self, data=NULL, next=NULL):
>         self.next = next
>         self.data = data
>
> I don't know how to make a list class
>

In languages like C you do this by using pointers.

NodeType* head;
NodeType* next = NULL;

head = &mynode;
/* fill up the list */

for(next = head->next; next; next = head->next) { /* or use a do .. while */
    printNode(next);
}

We can be sneaky and use Python's shallow copy semantics though .....

class Node:
  def __init__(self, data=None, next=None):
    self.next = next
    self.data = data

  def __repr__(self):
    return self.data

class MyList:
  def __init__(self):
    self.head = None
    self.tail = self.head

  def append(self, node):
    if self.tail is None:
      self.tail = node
      self.head = self.tail
    else:
      self.tail.next = node
      self.tail = node
    node.next = None

  def walk(self, func):
    item = self.head
    while item is not None:
      print item
      item = item.next

def printer(item):
  print item

mylist = MyList()

print 'add foo'
node = Node('foo')
mylist.append(node)
mylist.walk(printer)

print 'add bar'
node = Node('bar')
mylist.append(node)
mylist.walk(printer)

print 'add baz'
node = Node('baz')
mylist.append(node)
mylist.walk(printer)

Note, you probably do not want to use this in real code, but for learning 
exercises it can be fun.

You get to implement the other functions (and try to figure out how append() 
works).