In addition to linked lists that have a next field referencing the next node in the list, we can have a doubly linked list. In a doubly linked list, the node contains a value, a reference to the next node in the list, and a reference to the previous node in the list.

Suppose our ListNode class were modified to be a DLListNode class. The class definitions below represent the modifications to the ListNode class to create a DLListNode class. A doubly linked list node is a linked list node with another instance field.

public class DLListNode<E>
{
  private E value;
  private DListNode<E> next;
  private DListNode<E> previous;

  // Constructor:
  public DLListNode( E initValue, DListNode<E> initNext, DListNode<E> initPrevious )
  {
    value = initValue;
    next = initNext;
    previous = initPrevious;
  }

  public E getValue()
  {
    return value;
  }

  public DLListNode<E> getNext()
  {
    return next;
  }

  public DLListNode<E> getPrevious()
  {
    return previous;
  }

  public void setValue( E theNewValue )
  {
    value = theNewValue;
  }

  public void setNext( DLListNode<E> theNewNext )
  {
    next = theNewNext;
  }

  public void setPrevious( DLListNode<E> theNewPrevious )
  {
    previous = theNewPrevious;
  }
}

Figure 29-3

A null value must be placed at each end of the list to signify the end of the data structure. In the diagram, a null is indicated with the diagonal line.

A doubly-linked list should have two external references to access the data structure. In the case above, first and last are the two entry points.

A doubly-linked list can be traversed in either direction.

Inserting values into an ordered doubly-linked list is a similar process to the algorithm used with a singly-linked list. However, the number of reference manipulations will double. The addition of a new node to a position between two existing nodes will require four reference hookups.

The example below and Figure 29-4 show the adjustments necessary to add A DLListNode to the middle of a doubly linked list.

/*
  Adding a node to middle or end of an ordered doubly linked list.
*/
Comparable newValue = (Comparable)newNode.getValue();
DLListNode temp = first;
while ( temp.getNext() != null &&
            newValue.compareTo( (Comparable)temp.getValue() ) > 0 )
{
  temp = temp.getNext();
}

if (  newValue.compareTo( (Comparable)temp.getValue() ) <= 0 )
{
  // Adding to middle.
  // Four references must be set.
  DLListNode hold = temp.getPrevious();
  hold.setNext( newNode );
  newNode.setNext( temp );
  newNode.setPrevious( temp.getPrevious() );
  temp.setPrevious( newNode );
}
else
{
  // Adding to end.
  // Two references must be set.
  temp.setNext( newNode );
  newNode.setPrevious( temp );
}
        

Figure 29-4