Instructions
Objective
Write a program to implement nodes in java.
Requirements and Specifications
Objective
In this project, you will create a Doubly Linked List using you problems solving skills and what you know about Linked Lists.
Instructions
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.
So, once you're done, you should have the following three classes:
- Main.java
- Node.java
- DoublyLinkedList.java
Sample Runs
For this assignment, you simply need to add a bundle of numbers to the LinkedList, and then print them backwards. You can choose the numbers you add and the order as well. You can use the ones you added to the main() method (if you followed along with the lecture), mimic the ones I added, or make a brand new set.
Assume for the sample run below that the following numbers were added in order to the linked list:
1, 2, 3, 4, 5
(1 was added first, up to being 5 added last.)
Source Code
NODES
/**
* A node that is used to build a linked list.
*
* @author Hp Envy
*/
public class Node {
/**
* Node value
*/
int value;
/**
* Reference to the next node
*/
Node next;
/**
* Reference to the previous node
*/
Node previous;
/**
* Create a node.
*
* @param newValue Value to be stored in the node.
*/
public Node(int newValue) {
value = newValue;
next = null;
}
}
DOUBLY LINKED LIST
/**
* A doubly linked list. A linked list whose nodes have a next and previous
* node.
*
* @author Hp Envy
*/
public class DoublyLinkedList {
/**
* Reference to the head node
*/
private Node head;
/**
* Reference to the tail node
*/
private Node tail;
/**
* Add a new node at the end of the list
*
* @param newValue
*/
public void insert(int newValue) {
Node newNode = new Node(newValue);
if (isEmpty()) {
// Case if empty
head = newNode;
tail = newNode;
} else {
// Add next to tail
tail.next = newNode;
newNode.previous = tail;
tail = newNode;
}
}
/**
* Delete the element that holds the key.
*
* @param key Target element to deletes
*/
public void delete(int key) {
Node currentNode = head;
while (currentNode != null) {
if (currentNode.value == key) {
// Found it.. do delete
if (currentNode == head) {
// Case deleting the head
head = currentNode.next;
if (head != null) {
head.previous = null;
} else {
tail = null;
}
} else if (currentNode == tail) {
// Case deleting the tail
tail = tail.previous;
if (tail != null) {
tail.next = null;
} else {
head = null;
} else {
// Case deleting in-between
currentNode.previous.next = currentNode.next;
currentNode.next.previous = currentNode.previous;
}
return;
}
currentNode = currentNode.next;
}
}
/**
* Return the value of a node.
*
* @param index Target node
* @return Node value
*/
public int get(int index) {
if (index < 0) {
throw new RuntimeException("Index out of bounds.");
}
Node currentNode = head;
for (int i = 0; i < index && currentNode != null; i++) {
currentNode = currentNode.next;
}
if (currentNode == null) {
throw new RuntimeException("Index out of bounds.");
}
return currentNode.value;
}
/**
* Update the value of a node.
*
* @param index Target node
* @param value Updated value
*/
public void set(int index, int value) {
if (index < 0) {
throw new RuntimeException("Index out of bounds.");
}
Node currentNode = head;
for (int i = 0; i < index && currentNode != null; i++) {
currentNode = currentNode.next;
}
if (currentNode == null) {
throw new RuntimeException("Index out of bounds.");
}
currentNode.value = value;
}
/**
* Check if list is empty.
*
* @return True if empty, otherwise false.
*/
public boolean isEmpty() {
return head == null;
}
/**
* Return the content of the list
*
* @return Content of list
*/
@Override
public String toString() {
String result = "";
Node currentNode = head;
while (currentNode != null) {
result += currentNode.value;
if (currentNode.next != null) {
result += ", ";
}
currentNode = currentNode.next;
}
return result;
}
/**
* Return the content of the list in reverse
*
* @return Content of list in revere
*/
public String toStringReverse() {
String result = "";
Node currentNode = tail;
while (currentNode != null) {
result += currentNode.value;
if (currentNode.previous != null) {
result += ", ";
}
currentNode = currentNode.previous;
}
return result;
}
}// end class