Double Linked List Structure

If you wish to traverse a list both forwards and backwards efficiently, or if you wish, given a list element, to determine the preceding and following elements quickly, then the doubly-linked list comes in handy. A list element contains the data plus pointers to the next and previous list items as shown in the picture below.

Of course we need a pointer to some link in the doubly-linked list to access list elements. It is convenient for doubly-linked lists to use a list header, or head, that has the same structure as any other list item and is actually part of the list data structure. The picture below shows an empty and nonempty doubly-linked list. By following arrows it is easy to go from the list header to the first and last list element, respectively.

Insertion and removal of an element in a doubly-linked list is in this implementation rather easy. In the picture below we illustrate the pointer changes for a removal of a list item (old pointers have been drawn solid and new pointers are dashed arrows). We first locate the previous list item using the previous field. We make the next field of this list item point to the item following the one in cursor position pos. Then we make the previous field of this following item point to the item preceding the one in the cursor position pos. The list item pointed to by the cursor becomes useless and should be automatically garbage collected.

Implementing the double list items

Double List Node

package com.vaani.ds.doublelist;

final class DoubleListNode {
    Object obj;
    DoubleListNode previous, next;

    public DoubleListNode(Object obj) {
        this(null, obj, null);
    }

    public DoubleListNode(DoubleListNode previous, 

                                   Object obj, DoubleListNode next) {
        this.previous = previous;
        this.obj = obj;
        this.next = next;
    }
}

A class definition with only two constructor methods. The keyword final ensures that this class has no subclasses nor that a user can derive a class from this one.

DoubleLinkedList.java

public class DoubleLinkedList <E>{   
    DoubleListNode<E> head;
    private DoubleListNode<E> tail;
    private int length=0;
    /*
     * creates an empty list
     */
    public DoubleLinkedList() {
        //        head = new DoubleListNode<E>(null);
        //        head.next = head.prev = head;
        head.setPrev(null);
        head.setNext(tail);
        tail.setPrev(head);
        tail.setNext(null);
    }

    public DoubleListNode<E> get(int index) 
                                throws IndexOutOfBoundsException {
        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException();
        } else {
            DoubleListNode<E> cursor = head;
            for (int i = 0; i < index; i++) {
                cursor = cursor.getNext();
            }
            return cursor;
        }
    }

    public E remove(int index) throws IndexOutOfBoundsException {
        if (index == 0) {
            throw new IndexOutOfBoundsException();
        } else {
            DoubleListNode<E> result = get(index);
            result.getNext().setPrev(result.getPrev());
            result.getPrev().setNext(result.getNext());
            length--;
            return result.getValue();
        }
    }
    /*
     * remove all elements in the list
     */
    public final  void clear() {
        head.next = head.prev = head;
    }

    /*
     * returns true if this container is empty.
     */
    public final boolean isEmpty() {
        return head.next == head;
    }

    public int size() {
        return length;
    }


    public String toString() {
        StringBuffer result = new StringBuffer();
        result.append("(head) - ");
        DoubleListNode<E> temp = head;
        while (temp.getNext() != tail) {
            temp = temp.getNext();
            result.append(temp.getValue() + " - ");
        }
        result.append("(tail)");
        return result.toString();
    }

    public void add(int index, E value) 
                                throws IndexOutOfBoundsException {
        DoubleListNode<E> cursor = get(index);
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }

    public void addHead(E value) {
        DoubleListNode<E> cursor = head;
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }

    public void addTail(E value) {
        DoubleListNode<E> cursor = tail.getPrev();
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }


    /*
     * Return an iterator positioned at the head.
     */
    public final DoubleListIterator head() {
        return new DoubleListIterator(this, head);
    }


}