WEEK13: linked lists
---------------------------------------------------------------
 W: LinkedList class


LINKED LISTS:

 - used as building blocks for many advanced data structures (like
   queues, stacks, and skip lists)

 - can be used like Python lists -- many languages (like C) don't
   have a data structure like a Python list

 - we'll use linked lists as another example of a class, and write
   our own


REVIEW of LINKED LISTS:

 - a linked list is a collection of "nodes", where each
   node "points" to the next one in the list

 - each node stores two things: data and where (if anywhere) the next node is
   (see Node __init__ method below)

 - linked lists typically have three instance variables: a head pointer (self.head),
   a tail pointer (self.tail), and the number of nodes in the list (self.size)

              -----    -----    -----    ------    ------
 head node--> | 3 |    | 5 |    | 0 |    | 91 |    | 12 | <--tail node
              -----    -----    -----    ------    ------
              |   |--> |   |--> |   |--> |    |--> |    | 
              -----    -----    -----    ------    ------

   the above linked list has 5 nodes, and each node stores
   one piece of data (a simple integer)


NODE Class from last time:

class Node:
    """
    A class to represent one node in a singly-linked list.
    A node has two fields: data and next. Data stores the data
    value and next refers to the next node in the linked list.
    """

    def __init__(self, data, next):
        """ Create an new linked list node """
        self.data = data
        self.next = next

    def __str__(self):
        """show if next is None or points to something"""
        me =  "(%s)" % (self.data)
        if (self.next != None):
          me += "-->" 
        else :
          me += "--|"
        return me

    def setData(self, data):
        self.data = data

    def setNext(self, next):
       self.next = next

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

#########################################################

if __name__ == "__main__":

  n1 = Node("jeff",None)      # store a string in each node
  n2 = Node("frances",None)
  n1.setNext(n2)
  print "n1: ", n1
  print "n2: ", n2


LINKED LIST CLASS:

 - each linked list should have what kind of data and methods???

data: head, tail, size??
methods: __init__, __str__, add (at head? at tail? in sorted order?),
         remove (at head? tail?), findNode, len?

 - for the constructor, let's make the list empty, with both
   the head and the tail set to None (and a size of zero)

 - let's start with adding a new node at the tail of the list
   (like the python list append method). here's one possible algorithm:

        create a new node with the given data
        set the new node's next field to point to None
        set the current tail node's next to point to the new node
        set the tail of the linked list to point to the new node
        if this is the only node in the list, set the head to point to it, too
        add one to the size of the linked list

APPEND method:

  def append(self, data):
    """append new node to linked list"""

    newnode = Node(data)

    if self.size == 0:
      self.head = newnode  # list is empty case
      self.tail = newnode
    else:
      self.tail.setNext(newnode)
      self.tail = newnode

    self.size += 1

__str__ method:

  - need to traverse the list, visiting every node, adding each
    node's data item to the string we will return

    s = "head -- "
    curr = self.head
    while curr != None:
      s = s + str(curr.getData()) + " -- "
      curr = curr.getNext()
    s = s + "tail"


YOUR TURN:

 - write a LinkedList class that works with the following
   test code:

  LL = LinkedList()
  for i in ["jeff", "frances", "molly", "justin"]:
    LL.append(i)
  print LL