Chapter 3, Problem 8R

Explanation of Solution

Method to find the middle node of doubly linked list:

This method moves right from head is assigned to middle node and at the same time moves left from tail is assigned to partner node.

• If the middle and partner node is equal, then return the middle node.
• If middle node is just next node of partner node, then it even number of elements. So, return the previous node of middle node.

Program:

//Define the middle() method

private Node<E> middle()

{

  //Check whether the list is empty

  if (size == 0)

  //Throw an exception

throw new IllegalStateException("List must not be empty");

  //Assign the next node of head to middle Node

  Node<E> middleNode = head−>next;

  //Assign the previous node of tail to partner Node

  Node<E> partnerNode = tail−>prev;

/*Loop executes until the middle node and partner node is not equal and next node of middle node and partner node is not equal. */

while (middleNode != partnerNode && middleNode−>next != partnerNode)

  {

  //Assign next node of middle node to middle node

  middleNode = middleNode.getNext();

/*Assign previous node of partner node to partner node...