DoublyLinkedList.java:

public class DoublyLinkedList {

// ---------------- nested Node class ----------------

/**

* Node of a doubly linked list, which stores a reference to its element and

* to both the previous and next node in the list.

*/

private static class Node {

/** The element stored at this node */

private E element; // reference to the element stored at this node

/** A reference to the preceding node in the list */

private Node prev; // reference to the previous node in the list

/** A reference to the subsequent node in the list */

private Node next; // reference to the subsequent node in the list

/**

* Creates a node with the given element and next node.

*

* @param e

* the element to be stored

* @param p

* reference to a node that should precede the new node

* @param n

* reference to a node that should follow the new node

*/

public Node(E e, Node p, Node n) {

element = e;

prev = p;

next = n;

}

// public accessor methods

/**

* Returns the element stored at the node.

*

* @return the element stored at the node

*/

public E getElement() {

return element;

}

/**

* Returns the node that precedes this one (or null if no such node).

*

* @return the preceding node

*/

public Node getPrev() {

return prev;

}

/**

* Returns the node that follows this one (or null if no such node).

*

* @return the following node

*/

public Node getNext() {

return next;

}

// Update methods

/**

* Sets the node's previous reference to point to Node n.

*

* @param p

* the node that should precede this one

*/

public void setPrev(Node p) {

prev = p;

}

/**

* Sets the node's next reference to point to Node n.

*

* @param n

* the node that should follow this one

*/

public void setNext(Node n) {

next = n;

}

} // ----------- end of nested Node class -----------

// instance variables of the DoublyLinkedList

/** Sentinel node at the beginning of the list */

private Node header; // header sentinel

/** Sentinel node at the end of the list */

private Node trailer; // trailer sentinel

/** Number of elements in the list (not including sentinels) */

private int size = 0; // number of elements in the list

/** Constructs a new empty list. */

public DoublyLinkedList() {

header = new Node(null, null, null); // create header

trailer = new Node(null, header, null); // trailer is preceded by

// header

header.setNext(trailer); // header is followed by trailer

}

// public accessor methods

/**

* Returns the number of elements in the linked list.

*

* @return number of elements in the linked list

*/

public int size() {

return size;

}

/**

* Tests whether the linked list is empty.

*

* @return true if the linked list is empty, false otherwise

*/

public boolean isEmpty() {

return size == 0;

}

/**

* Returns (but does not remove) the first element of the list.

*

* @return element at the front of the list (or null if empty)

*/

public E first() {

if (isEmpty())

return null;

return header.getNext().getElement(); // first element is beyond header

}

/**

* Returns (but does not remove) the last element of the list.

*

* @return element at the end of the list (or null if empty)

*/

public E last() {

if (isEmpty())

return null;

return trailer.getPrev().getElement(); // last element is before trailer

}

// public update methods

/**

* Adds an element to the front of the list.

*

* @param e

* the new element to add

*/

public void addFirst(E e) {

addBetween(e, header, header.getNext()); // place just after the header

}

/**

* Adds an element to the end of the list.

*

* @param e

* the new element to add

*/

public void addLast(E e) {

addBetween(e, trailer.getPrev(), trailer); // place just before the

// trailer

}

/**

* Removes and returns the first element of the list.

*

* @return the removed element (or null if empty)

*/

public E removeFirst() {

if (isEmpty())

return null; // nothing to remove

return remove(header.getNext()); // first element is beyond header

}

/**

* Removes and returns the last element of the list.

*

* @return the removed element (or null if empty)

*/

public E removeLast() {

if (isEmpty())

return null; // nothing to remove

return remove(trailer.getPrev()); // last element is before trailer

}

// private update methods

/**

* Adds an element to the linked list in between the given nodes. The given

* predecessor and successor should be neighboring each other prior to the

* call.

*

* @param predecessor

* node just before the location where the new element is

* inserted

* @param successor

* node just after the location where the new element is inserted

*/

private void addBetween(E e, Node predecessor, Node successor) {

// create and link a new node

Node newest = new Node(e, predecessor, successor);

predecessor.setNext(newest);

successor.setPrev(newest);

size++;

}

/**

* Removes the given node from the list and returns its element.

*

* @param node

* the node to be removed (must not be a sentinel)

*/

private E remove(Node node) {

Node predecessor = node.getPrev();

Node successor = node.getNext();

predecessor.setNext(successor);

successor.setPrev(predecessor);

size--;

return node.getElement();

}

/**

* Produces a string representation of the contents of the list. This exists

* for debugging purposes only.

*/

public String toString() {

StringBuilder sb = new StringBuilder("(");

Node walk = header.getNext();

while (walk != trailer) {

sb.append(walk.getElement());

walk = walk.getNext();

if (walk != trailer)

sb.append(", ");

}

sb.append(")");

return sb.toString();

}

/**

* required method to find the middle value

*

* @return the value at middle (or left of middle in case of even size), or

* null if list is empty

*/

public E findMiddle() {

Node middleNode = header.next;

Node currentNode = header.next;

// if current node equals trailer, returning null

if (currentNode == trailer) {

return null; // empty list

}

/**

* the algorithm is pretty simple, we loop until currentNode reach the

* end, in each iteration, currentNode is advanced twice and middleNode

* is advanced once. so when currentNode reaches the end, middleNode

* will only be halfway, so we can return it's value, which will be the

* middle value.

*/

// looping as long as currentNode is not null and next of currentNode is

// not trailer

while (currentNode != null && currentNode.next != trailer) {

// advancing middleNode once

middleNode = middleNode.next;

// advancing currentNode once

currentNode = currentNode.next;

// if currentNode is not null and next of currentNode is not

// trailer, advancing currentNode once again

if (currentNode != null && currentNode.next != trailer) {

currentNode = currentNode.next;

} else {

// otherwise moving back middleNode once (in case of even size)

middleNode = middleNode.prev;

}

}

return middleNode.element;

}

} // ----------- end of DoublyLinkedList class -----------

Create a java program to test findMiddle() from the DoublyLinkedList.java class provided below, with the following three tests cases. Program output should be this: Finding the middle of the 7ist: (1,2,3,4,5,6,7) The middle value is: 4 Finding the middle of this list: (1,2,3,4) The middle value is: 2 Finding the middle of this list: (First, Second, Third, Fourth, Fifth) The middle value is: Third Your code must work for any doubly-linked list, not just the examples