Exercise 3 Doubly Linked Lists

1. Open DoubleLinkedNode.java and BuildDLL.java in Eclipse and examine the code in both classes.

2. The DoubleLinkedNode class is complete and does not have to be modified.

3. The BuildDLL class has some provided methods for creating a doubly linked list with a sequence of letters (note that we are using the Character class for this, which is a wrapper for the primitive char type) and printing out the list from front to rear. Run the program to see the default output.

4. Notice that the original list is printing correctly, but the remove() method is not provided so subsequent list outputs are incorrect.

5. You must fill in the code for removing an element from the linked list using the following rules and hints: Loop through the list until you find the correct node (how can you tell if the node is the one for which we are searching?) We will assume that the input parameter 'elem' will always be a valid element that is contained in the list. Normally we would have to account for elements that are not found in the list, but you may ignore this possibility for this lab. What are the 3 possible cases of the node's location in the list? How must each of these cases be handled? Make the appropriate connections with the previous and/or next node based on its position in the list. (Hint: remember front's previous is null and rear's next is null).

6. Run the program and check that the output is correct. The list after each step should be:

K T E N P A L (original)

K T E P A L (after removing 'N')

T E P A L (after removing 'K')

T E P A (after removing 'L')

public class BuildDLL { DoubleLinkedNode front, rear; private static char[] letters = new char[] {'K', 'T', 'E', 'N', 'P', 'A', 'L'}; public BuildDLL () { build(); } public void remove (Character elem) { // Add code in here to remove the node with the given value. } private void build () { DoubleLinkedNode pnode, node; node = new DoubleLinkedNode(letters[0]); pnode = front = node; for (int i = 1; i < 7; i++) { node = new DoubleLinkedNode(letters[i]); pnode.setNext(node); node.setPrevious(pnode); pnode = node; } rear = node; } public DoubleLinkedNode getFront () { return front; } public DoubleLinkedNode getRear () { return rear; } public void printF (DoubleLinkedNode node) { DoubleLinkedNode curr = front; while (curr != null) { System.out.print(curr.getElement() + " "); curr = curr.getNext(); } System.out.print(" "); } public static void main (String[] args) { BuildDLL dll = new BuildDLL(); System.out.println("Original List:"); dll.printF(dll.getFront()); System.out.println("***"); System.out.println("Removing an internal node:"); dll.remove('N'); dll.printF(dll.getFront()); System.out.println("***"); System.out.println("Removing the front node:"); dll.remove('K'); dll.printF(dll.getFront()); System.out.println("***"); System.out.println("Removing the rear node:"); dll.remove('L'); dll.printF(dll.getFront()); System.out.println("***"); } }

public class DoubleLinkedNode { private DoubleLinkedNode next; private DoubleLinkedNode previous; private E element; public DoubleLinkedNode(){ next = null; previous = null; element = null; } public DoubleLinkedNode (E elem){ next = null; previous = null; element = elem; } public DoubleLinkedNode getNext(){ return next; } public DoubleLinkedNode getPrevious(){ return previous; } public void setNext (DoubleLinkedNode node){ next = node; } public void setPrevious (DoubleLinkedNode node){ previous = node; } public E getElement(){ return element; } public void setElement (E elem){ element = elem; } }