Sometimes it is convenient to maintain references to both the next node and the previous node in a linked list. This is called a doubly linked list and is illustrated in Figure 13.4 of the text. File DoubleLinked contains definitions for a doubly linked list of integers. This class contains an inner class IntNode that holds information for a single node in the list (its value and references to the next and previous nodes). The DoubleLinked class also contains the following methods:

public DoubleLinked()constructor; creates an empty list of integers public void addToFront(int val)takes an integer and puts it on the front of the list public void print()prints the elements in the list from first to last

File DoubleLinkedTest contains a driver that allows you to experiment with these methods. Save both of these files to your directory, compile and run DoubleLinkedTest, and play around with it to see how it works. Then add the following methods to the DoubleLinked class. For each, add an option to the driver to test it. 1. public void addToEnd(int val)takes an integer and puts it on the end of the list 2. public void removeFirst()removes the first value from the list. If the list is empty, does nothing. 3. public void removeLast()removes the last element of the list. If the list is empty, does nothing. 4. public void remove(int oldVal)removes the first occurrence of oldVal in the list.

DoubleLinked.java

// ***************************************************************

// DoubleLinked.java

//

// A class using a doubly linked list to represent a list of integers.

//

// ***************************************************************

public class DoubleLinked

{

private IntNode list;

// ----------------------------------------------

// Constructor -- initializes list

// ----------------------------------------------

public DoubleLinked()

{

list = null;

}

// ----------------------------------------------

// Prints the list elements

// ----------------------------------------------

public void print()

{

for (IntNode temp = list; temp != null; temp = temp.next)

System.out.println(temp.val);

}

// ----------------------------------------------

// Adds new element to front of list

// ----------------------------------------------

public void addToFront(int val)

{

IntNode newNode = new IntNode(val);

newNode.next = list;

if (list != null)

list.prev = newNode;

list = newNode;

}

//***************************************************************

// An inner class that represents a list element.

//***************************************************************

private class IntNode

{

public int val;

public IntNode next;

public IntNode prev;

public IntNode(int val)

{

this.val = val;

this.next = null;

this.prev = null;

}

}

}

DoubleLinkedTest.java

// ***********************************************************

// DoubleLinkedTest.java

//

// Driver to test DoubleLinked methods.

// ***********************************************************

import java.util.Scanner;

public class DoubleLinkedTest

{

private static Scanner scan;

private static DoubleLinked list = new DoubleLinked();

//----------------------------------------------------------------

// Creates a list, then repeatedly prints the menu and does what

// the user asks until they quit.

//----------------------------------------------------------------

public static void main(String[] args)

{

scan = new Scanner(System.in);

printMenu();

int choice = scan.nextInt();

while (choice != 0)

{

dispatch(choice);

printMenu();

choice = scan.nextInt();

}

}

//---------------------------------------

// Does what the menu item calls for.

//---------------------------------------

public static void dispatch(int choice)

{

int newVal;

switch(choice)

{

case 0:

System.out.println("Bye!");

break;

case 1: //print

System.out.println("** List elements **");

list.print();

break;

case 2: //add to front

System.out.println("Enter integer to add to front");

newVal = scan.nextInt();

list.addToFront(newVal);

break;

default:

System.out.println("Sorry, invalid choice");

}

}

//-----------------------------------------

// Prints the user's choices

//-----------------------------------------

public static void printMenu()

{

System.out.println(" Menu ");

System.out.println(" ====");

System.out.println("0: Quit");

System.out.println("1: Print list");

System.out.println("2: Add an integer to the front of the list");

System.out.print(" Enter your choice: ");

}

}