knerr cs21 notes...

back to schedule

WEEK13: linked lists
---------------------------------------------------------------
 W: LinkedList class (again...)

LAST TIME:

 - 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


 -here's an example of the linkedlist.py class:

from node import *

class LinkedList(object):
  """
  A class to represent a singly-linked list.
  A linked list has references to it's head and tail nodes.
  """

  def __init__(self):
    """ Create an empty linked list """
    self.head = None  # points to first node in list
    self.tail = None  # points to last node in the list
    self.size = 0     # number of elements in the list

  def __str__(self):
    """
    Create a string consisting of the contents of the
    linked list from head to tail.
    """
    result = "head--" 
    current = self.head
    while current != None:
      result = result + ">(" + str(current.getData()) + ")--"
      current = current.getNext()
    result = result + "|"
    return result 

  def getSize(self):
    return self.size

  def isEmpty(self):
    """Returns True if linked list is empty"""
    return (self.head == None)

  def insertAtHead(self, data):
    """
    This method creates a new Node and adds it to 
    the front of the linked list.
    """
    n = Node(data, None)
    if self.size == 0:
      self.head = n
      self.tail = n
    else:
      n.setNext(self.head)
      self.head = n
    self.size = self.size + 1


 - NOTE how the __str__ method does a *traversal* of the entire list

 - also NOTE how insertAtHead needs to deal with the special case of
   adding a node when the list is empty (must set self.tail, too)

 - what happens when you try to use len on a linked list, like this:

LL = LinkedList()
LL.insertAtHead(201)
LL.insertAtHead("pony")
print len(LL)

 - what happens when you rename the getSize method to __len__, then
   try the above code (print len(LL))??!

YOUR TURN:

 - add an insertAtTail method to the above class, and write some test
   code to make sure it works (make sure it works on an empty list, as
   well as a list with 1 or more nodes in it)


ANOTHER underscore-underscore method...

 - this currently doesn't work: print LL[0]

 - but we could write a getData method so this would work: print LL.getData(0)

 - think about what getData needs to do and come up with an algorithm
   (ex: what should LL.getData(0) return? what should it return if the
   list is empty? what should LL.getData(-1) return? what should LL.getData(n)
   return if n is greater than the size of the list?)

YOUR TURN:

 - write the getData method, and some test code to make sure it works

 - once you're sure it works, rename it __getitem__ and try
   print LL[0] or print LL[-1] or print LL[20], and so on...