CS21 Lab 12: Doubly-Linked Lists

OPTIONAL - NO DUE DATE (but good practice for the final...hint, hint)
This lab is completely optional. You will not receive a grade on this assignment. However, you may want to try these problems as practice for the final exam.

Doubly-Linked Lists
For the exercise in this section, you should begin with the in-class code for the Node and LinkedList classes.

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.
  2. Modify LinkedList so that it properly maintains the prev links. You will need to update or write 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). This method should return None if the key is not in 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 the previous part 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 for the LinkedList class).
  2. prompts the user to enter a value to search for in the list, calls your find method function, and prints out it's return value.
  3. prompts the user to enter a value to remove from the list, calls your remove method, and then prints out the resulting list
Please enter 10 values!
 1: 21
 2: 45
 3: 79
 4: 99
 5: 3
 6: -70
 7: 51
 8: 632
 9: 787
10: 89

Here is your list:
head--><--21--><--45--><--79--><--99--><--3--><---70--><--51--><--632--><--787--><--89-->tail

search for: 51
<--(51)-->

    remove: 632
head--><--21--><--45--><--79--><--99--><--3--><---70--><--51--><--787--><--89-->tail