Overview of Doubly Linked Lists

22/October/2014 by Valkryst, Updated 29/June/2017

The following post is derived from notes taken while reading through this textbook.

Although the visualization above may not make sense right away, just think of each node as holding a reference to the next node in the list. The red node holds a reference to the green node. Because the red node is the first node, it doesn't hold a reference to a node before it. The green node holds a reference to the red node, because it comes before the green node, and a reference to the blue node, because it comes after the green node. The blue node holds a reference to the green node, because it comes before the blue node, and it holds no reference to the next node because there is no next node.

The red node is the head (beginning) of the list and the blue node is the tail (end) of the list.

    
        public class DoublyLinkedList {
            /** The head node. */
            private Node head;
            /** The tail node. */
            private Node tail;
            /** The total number of nodes in the list. */
            private long size;

            /** Constructs an empty DoublyLinkedList. */
            public DoublyLinkedList() {
                tail = new Node<>(null, null, null);
                head = new Node<>(null, null, null);
                size = 0;
            }

            @Override
            public String toString() {
                final StringBuilder sb = new StringBuilder();
                Node current = head.getNextNode();

                while(current != getTail()) {
                    sb.append(current.getStoredValue().toString()).append("\n");
                    current = current.getNextNode();
                }

                return sb.toString();
            }

            /**
            * Inserts a node at the head of the list.
            *
            * @param node
            *         The node to insert.
            */
            public void addFirst(final Node node) {
                head.getNextNode().setPreviousNode(node);
                head.setNextNode(node);
                size++;
            }

            /**
            * Inserts a node at the tail of the list.
            *
            * @param node
            *         The node to insert.
            */
            public void addLast(final Node node) {
                tail.getPreviousNode().setNextNode(node);
                tail.setPreviousNode(node);
                size++;
            }

            /**
            * Inserts a node before another node.
            *
            * @param node
            *         The node to add the new node before.
            *
            * @param newNode
            *         The node to insert.
            */
            public void addBefore(final Node node, final Node newNode) {
                final Node temp = node.getPreviousNode();
                node.setPreviousNode(newNode);
                newNode.setNextNode(node);
                newNode.setPreviousNode(temp);
                size++;
            }

            /**
            * Inserts anode after another node.
            *
            * @param node
            *         The node to add the new node after.
            *
            * @param newNode
            *         The node to insert.
            */
            public void addAfter(final Node node, final Node newNode) {
                final Node temp = node.getNextNode();
                node.setNextNode(newNode);
                newNode.setPreviousNode(node);
                newNode.setNextNode(temp);
                size++;
            }

            /**
            * Removes the head node.
            *
            * @return
            *         The previous head node of the list, without any references
            *         to the rest of the list.
            */
            public Node removeHead() {
                final Node temp = new Node<>(head.getNextNode().getStoredValue(), null, null);
                head.setNextNode(head.getNextNode().getNextNode());
                head.getNextNode().setPreviousNode(head);

                size--;
                return temp;
            }

            /**
            * Removes the tail node.
            *
            * @return
            *         The previous tail node of the list, without any references
            *         to the rest of the list.
            */
            public Node removeTail() {
                final Node temp = new Node<>(tail.getPreviousNode().getStoredValue(), null, null);
                tail.setPreviousNode(tail.getPreviousNode().getPreviousNode());
                tail.getPreviousNode().setNextNode(tail);

                size--;
                return temp;
            }

            /**
            * Removes a node from the list.
            *
            * @param node
            *         The node to remove.
            *
            * @return
            *         The removed node, without any references to the rest of the list.
            */
            public Node remove(final Node node) {
                if(node == getHead()) {
                    return removeHead();
                } else if(node == getTail()) {
                    return removeTail();
                } else {
                    final Node temp = new Node<>(node.getStoredValue(), null, null);
                    final Node previousNode = node.getPreviousNode();
                    final Node nextNode = node.getNextNode();

                    previousNode.setNextNode(nextNode);
                    nextNode.setPreviousNode(previousNode);

                    return temp;
                }
            }

            public Node getHead() {
                return head.getNextNode();
            }

            public Node getTail() throws IllegalStateException {
                return tail.getPreviousNode();
            }

            public Node getNext(final Node node) throws IllegalStateException {
                return node.getNextNode();
            }

            public Node getPrevious(final Node node) throws IllegalStateException {
                return node.getPreviousNode();
            }
        }
    
    
        public class Node {
            /** The value. */
            private E value;
            /** A reference to the next node. */
            private Node nextNode;
            /** A reference to the next node. */
            private Node previousNode;

            /**
            * Constructs a Node.
            *
            * @param value
            *         The value.
            */
            public Node(final E value) {
                this.value = value;
            }

            /**
            * Constructs a Node.
            *
            * @param value
            *         The value to be held by the Node.
            *
            * @param nextNode
            *         A reference to the next node.
            *
            * @param previousNode
            *         A reference to the previous node.
            */
            public Node(final E value, final Node nextNode, final Node previousNode) {
                this.value = value;
                this.nextNode = nextNode;
                this.previousNode = previousNode;
            }

            public E getStoredValue() {
                return value;
            }

            public Node getNextNode() {
                return nextNode;
            }

            public Node getPreviousNode() {
                return previousNode;
            }

            public void setStoredValue(final E value) {
                this.value = value;
            }

            public void setNextNode(final Node nextNode) {
                this.nextNode = nextNode;
            }

            public void setPreviousNode(final Node previousNode) {
                this.previousNode = previousNode;
            }
        }