CS21 Lab 13: Optional Assignment

Due 11:59pm Wed night, Dec. 10

You must work alone on this assignment.

This assignment is completely optional. Your grade on this assignment will supplant your lowest grade for any quiz or homework (I will automatically drop the one that helps you the most). Even if you do not submit it, you may want to try these problems as practice for the final exam.

Run update21, if you haven't already, to create the cs21/labs/13 directory. Then cd into your cs21/labs/13 directory and create the python programs for lab 13 in this directory. 

$ update21
$ cd cs21/labs/13
Linked Lists
For the exercise in this section, you should begin with the in-class code for the Node and LinkedList classes (I put the node.py and linkedlist.py files we used in class in the labs/13 directory, but you should have more complete solutions from your in-class work).

We have dealt exclusively with what are called singly-linked lists. They are called singly-linked because there is only one link that connects each node to another node in the list. We have called this link next because it points to the next item in the list.

In this exercise, you will write an implementation of a doubly-linked list. A doubly-linked list maintains two links to other nodes in the list: a link called next which points to the next node in the list (same as we've already seen), and a link called prev which points to the previous node in the list. The prev link allows you to walk back and forth through the list. For example, to find the second-to-last item in a doubly-linked list, you can start at the tail and follow one prev to get to the second-to-last node.

Here is what a doubly linked list might look like in memory ( just the head and tail fields of the LinkedList object are shown): 

                Node obj         Node obj         Node obj         Node obj
                --------         --------         --------         --------
                | data-|--> 6    | data-|--> 12   | data-|--> 3    | data-|--> 8
  head -------->| next-|-------->| next-|-------->| next-|-------->| next-|----|
           |--- |-prev |<--------|-prev |<--------|-prev |<--------|-prev |
                --------         --------         --------         --------
                                                                      ^
                                                                      | 
                                     tail -----------------------------

You will need to do the following:

  1. Modify Node so that it has a prev link, add getPrev and setPrev methods, and update the __str__ method.
  2. Modify LinkedList so that it properly maintains the prev links. You will need to update insertAtHead, insertAtTail, removeFromHead, and removeFromTail.
  3. Add functionality to support a method called find(self, key) which returns the Node containing the first instance of the key in the LinkedList (starting from the head of the list).
  4. Add functionality to support a method called remove(self, key) which removes the Node containing the first instance of the key in the LinkedList (starting from the head of the list). You will probably want to use the find method you wrote in part iii as part of this solution.

You should have a main function that:

  1. creates a doubly linked list from 10 values entered by the user and prints out the resulting list (make sure you have an implementation of the __str__ method in the LinkedList and Node classes).
  2. prompts the user to enter a value to search for in the list, and calls your find method function and prints out its return value.
  3. prompts the user to enter a value to remove from the list, calls your remove function, and then prints out the resulting list.
Recursion

Implement an iterative function, raiseToThePower(n, p), that computes n raised to the p power by using only multiplication (you may not use the ** operator nor any functions in the math library). For example: 

n^6 = n * n * n * n * n * n
Implement a recursive function, raiseToThePowerRec(n, p), that computes n raised to the p power (same as above, using only multiplication).

Write a main function that prompts the user to enter two values, one for n and one for p, and then makes calls to your functions and prints out the results.

Submit

Once you are satisfied with your programs, hand them in by typing handin21 in a terminal window.