For this project, you will take the LinkedList.java we created during our Linked List lecture and turn it into a DoublyLinkedList.

First, rename your file from LinkedList.java to DoublyLinkedList.java.

Change the name of the class to DoublyLinkedList. Do the same for the constructor.

A doubly linked list not only allows traversal from the (head) first element in the Linked list to the (tail) last, but traversal from last to first. In this way, you will need to modify Node.java so not only does it have a Node next, but a Node previous as well. This way, not only will a node know who is next, but it will know who came previous as well.

The head node in LinkedList.java represents the very first node in the list. In your DoublyLinkedList.java, not only will you have a head, but a tail Node as well. Create a tail Node in DoublyLinkedList.java that keeps track of the last most element in the list. You should now have two instance variables: Node head and Node tail.

Whenever you added or removed a node, you would have to house keep and manage the .next variables of each affected node. You will now need to handle setting up the previous nodes for each affected Node as well at the same time. You will need to modify your insert() and delete() functions so that whenever you would modify a .next, you will also set the .previous of a node.

Your goal is to set up the Doubly linked list so that each node knows who their previous neighbor is. Once you have done so, you will create a new function called toStringReverse(). (Note: no need to Override for this function. You only have to Override the regular toString() function, not this one.) This function will act like toString(), only you will print out the list starting from the tail using only each Node’s .previous instead of their .next.

In main, replace your System.out.println(list.toString()) with the new System.out.println(list.toStringReverse()) to print out the list in reverse. Ideally, in this way the list should print out the numbers you programmatically added to it in the reverse order that they were given.

Code:

public class LinkedList
{
private Node head;

public void insert(int newValue)
{
//create a node with the value we want to add
Node newNode = new Node(newValue);

//find a spot in the list to insert the node(end of list)
if(isEmpty())
{
head = newNode;
}//end if
else
{
Node last = head;
while(last.next != null)
{
last = last.next;
}//end while

//at this point, last is equal to the final node in the list
last.next = newNode;//added the new node after the final node
}//end else
}//end method

public void delete(int key)
{
//start our search at the head
Node currentNode = head;
Node previous = null;

//if the head node has the key we want to delete
if(!isEmpty() && head.value == key)
{
head = head.next;
}//end if
//the key is not the head node search through each node
else
{
while(currentNode != null && currentNode.value!= key)
{
previous = currentNode;
currentNode = currentNode.next;
}//end while
if(currentNode == null) //we never found the value
{
System.out.println(“Key not found in Linked list.”);
}//end if
if(currentNode != null)//Found! now want to delete current node
{
previous.next = currentNode.next;

}
}//end else

//we do not find the key in the list
}//end method

public int get(int index)
{
//create node to hold result

//check the head to see if its the node we want
if(index == 0 && head != null)
{
return head.value;
}//end if
//check the rest of the nodes
else if(head.next != null)
{
int currentIndex = 1;
Node temp = head.next;

while(temp != null)
{
if(index == currentIndex)
{
return temp.value;
}//end iff

temp = temp.next;
currentIndex++;
}//end while
}//end else
//handle if the node doesnt exist
return -99999;
}//end method

public void set(int index, int value)
{
//create node to hold result

//check the head to see if its the node we want
if(index == 0 && head != null)
{
head.value = value;
}//end if
//check the rest of the nodes
else if(head.next != null)
{
int currentIndex = 1;
Node temp = head.next;

while(temp != null)
{
if(index == currentIndex)
{
temp.value = value;
}//end if

temp = temp.next;
currentIndex++;
}//end while
}//end else

}//end method

public boolean isEmpty()
{
return head == null;
}//end method

@Override
public String toString()
{
String result = “”;

Node last = head;

while (last != null)
{
result += last.value + (last.next == null ? “” : “, ” ); // “, “;
last = last.next;
}

return result;
}//end method
}//end class