The node of a doubly-linked list will contain the information field and two reference fields. One reference will refer to a previous node while the other reference will refer to the next node in the list.

The following class definitions will be used:

public class DListNode{
  private Object value;
  private DListNode next;
  private DListNode previous;

  // Constructor:
  public DListNode(Object initValue,
                   DListNode initNext,
                   DListNode initPrevious){

    value = initValue;
    next = initNext;
    previous = initPrevious;
  }

  public Object getValue(){
    return value;
  }

  public DListNode getNext(){
    return next;
  }

  public DListNode getPrevious(){
    return previous;
  }

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

  public void setNext(DListNode theNewNext){
    next = theNewNext;
  }

  public void setPrevioust(DListNode 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.