Skip to main content

Programming Contest Central

Double Linked List Node

It is recommended that you read through tutorials Linked List Node and Linked List Class first.

A double linked list adds another reference to each node, which points to the previous node. For example:

Deleting a node in a single linked list requires the previous node’s reference to be changed. Using a double linked list, finding the previous node is much more efficient, although more memory is required to contain this extra reference. Note that all changes now require two nodes to be modified instead of only one in single linked lists.

The DoubleLinkedListNode here extends LinkedListNode and adds the prev reference. super(); calls the LinkedListNode constructors. getNext() is overriden from LinkedListNode to be casted as a DoubleLinkedListNode.

public class DoubleLinkedListNode extends LinkedListNode {
    private DoubleLinkedListNode prev;

    public DoubleLinkedListNode() {
        super();
        setPrev(null);
    }

    public DoubleLinkedListNode(Object myNodeValue) {
        super(myNodeValue);
        setPrev(null);
    }

    // setNext() is the same and does not need to be modified

    public DoubleLinkedListNode getNext() {
        return (DoubleLinkedListNode) super.getNext();
    }

    public void setPrev(DoubleLinkedListNode prev) {
        this.prev = prev;
    }

    public DoubleLinkedListNode getPrev() {
        return prev;
    }
}

This tutorial on doubly linked lists continues with Double Linked List Class

%%sidebarspace%%