CS21: Lab 12

This lab is completely optional. You will not receive a grade on this assignment. However, you may want to write these methods as practice for the final exam.

Finish the LinkedList class

For this lab, run update21 to get a clean copy of the code we wrote in class for the Node and LinkedList classes. In your cs21/labs/12 directory should be the node.py and linkedlist.py files. Read through them and make sure you understand how they work. You can also start with your own files from class, if you want.

So far we have written the following methods:

__init__()
__str__()
append(data)

Here are some other useful methods you should add to the linkedlist.py file:

prepend(data) -- add new node with data in it to head of the list
deleteHead() -- delete the head node, return data stored in deleted node
deleteTail() -- delete the tail node, return data stored in deleted node
isSorted() -- return True if all nodes are in sorted order
count(data) -- count and return number of nodes with data stored in node

For all of these, watch out for special cases, such as deleting a node when there's only one node left in the list.

Here is some test code:

if __name__ == "__main__":
  # test code here
  LL = LinkedList()
  print LL
  for ch in "abcdefg":
    LL.append(ch)
  print LL
  print "sorted??", LL.isSorted()
  LL.deleteHead()
  print "deleted head: ", LL
  LL.deleteTail()
  print "deleted tail: ", LL
  LL.prepend("z")
  LL.prepend("z")
  print LL
  print "sorted??", LL.isSorted()
  print "# of z's", LL.count("z")
  print "# of x's", LL.count("x")

And here is the test code output:

HEAD--><--TAIL
HEAD-->(a)(b)(c)(d)(e)(f)(g)<--TAIL
sorted?? True
deleted head:  HEAD-->(b)(c)(d)(e)(f)(g)<--TAIL
deleted tail:  HEAD-->(b)(c)(d)(e)(f)<--TAIL
HEAD-->(z)(z)(b)(c)(d)(e)(f)<--TAIL
sorted?? False
# of z's 2
# of x's 0

CS21 Lab 12: Finish LinkedList class