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 (handin21 looks for your lab 13 assignments in your cs21/labs/13 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. The starting point is here: ~newhall/public/cs21/week13/linked.py, but you should have a more complete solution from your in-class work that you can use as a starting point.

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 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 (and functions identically to the next pointer we have seen so far), and a link called prev which points to the previous node in the list. The prev 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 support getPrev and setPrev, 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 print out the resulting list (make sure you have an implementation of the __str__ methods of 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, pow), that computes n raised to the pow 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, pow), that computes n raised to the pow power by using only multiplication (you may not use the ** operator nor any functions from the math library).

Write a main function that prompts the user to enter two values, one for n and one for pow, and makes a call to your raiseToThePower function with n and pow, and prints out the result and makes a call to your raiseToThePowerRec with n and pow, and prints out the result.

Submit

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