knerr cs21 notes...

back to schedule

WEEK13: linked lists
---------------------------------------------------------------
 M: 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

 - linked lists typically have a head node and sometimes a tail node:

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

   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(20,None)
  print "n1: ", n1
  n2 = Node(721,None)
  n2.setNext(n1)
  print "n2: ", n2, n2.getNext()



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 head of the list.
   here's one possible algorithm:

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

YOUR TURN:

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

if __name__ == "__main__":
  LL = LinkedList()
  for i in [4,10,"cat",905, 3.14159]:
    LL.insertAtHead(i)
  print LL

 - if you have time, see if you can write insertAtTail