knerr cs21 notes...

back to schedule

WEEK12: linked lists
---------------------------------------------------------------
 M: nodes in linked list and Node class


LISTS...

 - how does python's list work? how is it implemented?

 - what things do we normally do with python lists?

      L = []             # construct
      L.append("cat")    # add to
      print L
      L.pop(0)           # remove from

 - can we write/create lists from scratch?


LINKED LISTS:

 - a linked list is a collection of objects/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)

 - linked lists are often used to create other useful data structures,
   such as stacks and queues

NODE Class:

 - let's write a Node class, where each node has two instance
   variables: one to hold the node data (call it "data"), and 
   one to hold a pointer to another node (call it "next")

   later on we will use these node objects to build a linked-list!

 - add two mutators and two accessors for the data and next
   variables, then test it out


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()