Insertion at the beginning is very similar to that of a singly linked list, except that we must now update the next node's reference for its previous node. The node being inserted does not have a previous node in this case, so nothing needs to be done:

    public Node<E> appendFirst(E value) { 
        Node<E> node = super.appendFirst(value); 
        if (first.next != null) 
            ((DoublyLinkedNode<E>) first.next).prev = (DoublyLinkedNode<E>) first; 
        return node; 
    }

Pictorially, it can be visualized as shown in the following figure:

Figure 10: Insertion at the beginning of a doubly linked list

Appending at the end is very similar and is given as follows:

    public Node<E> appendLast(E value) { 
        DoublyLinkedNode<E> origLast = (DoublyLinkedNode<E>) this.last; 
        Node<E> node = super.appendLast(value); 

If the original list were empty, the original last reference would be null:

        if (origLast == null) { 
            origLast = (DoublyLinkedNode<E>) first; 
        } 
        ((DoublyLinkedNode<E>) this.last).prev = origLast; 
        return node; 
    }

The complexity of the insertion is the same as that of a singly linked list. In fact, all the operations on a doubly linked list have the same running time complexity as that of a singly linked list, except the process of removing the last element. We will thus refrain from stating it again until we discuss the removal of the last element. You should verify that the complexity stays the same as with a singly linked list in all other cases.

As with everything else, this operation is very similar to the process of making an insertion at an arbitrary location of a singly linked list, except that you need to update the references for the previous node.

Figure 11: Insertion at an arbitrary location of a doubly linked list

The following code does this for us:

    public Node<E> insert(int index, E value) { 
        DoublyLinkedNode<E> inserted = (DoublyLinkedNode<E>) super.insert(index, value); 

In the case of the first and last element, our overridden methods are invoked anyway. Therefore, there is no need to consider them again:

        if(index!=0 && index!=length) { 
            if (inserted.next != null) { 

This part needs a little bit of explaining. In Figure 11, the node being inserted is 13. Its previous node should be 4, which was originally the previous node of the next node 3:

                inserted.prev = ((DoublyLinkedNode<E>) inserted.next).prev; 

The prev reference of the next node 3 must now hold the newly inserted node 13:

                ((DoublyLinkedNode<E>) inserted.next).prev = inserted; 
            } 
        } 
        return inserted; 
    }

Removing the first element is almost the same as that for a singly linked list. The only additional step is to set the prev reference of the next node to null. The following code does this:

    public Node<E> removeFirst() { 
        super.removeFirst(); 
        if (first != null) { 
            ((DoublyLinkedNode<E>) first).prev = null; 
        } 
        return first; 
    }

The following figure shows what happens. Also, note that finding an element does not really need an update:

Figure 12: Removal of the first element from a doubly linked list

There can be an optimization to traverse backward from the last element to the first in case the index we are looking for is closer toward the end; however, it does not change the asymptotic complexity of the find operation. So we leave it at this stage. If interested, you would be able to easily figure out how to do this optimization.

Just like other operations, removal is very similar to removal of elements in the case of a singly linked list, except that we need to update the prev reference:

Figure 13: Removal of an arbitrary element from a doubly linked list

The following code will help us achieve this:

    public Node<E> removeAtIndex(int index) { 
        if(index<0||index>=length){ 
            throw new NoSuchElementException(); 
        }

This is a special case that needs extra attention. A doubly linked list really shines while removing the last element. We will discuss the removeLast() method in the next section:

        if(index==length-1){ 
            return removeLast(); 
        } 

The rest of the code is fairly easy to figure out:

        DoublyLinkedNode<E> nodeRemoved 
               = (DoublyLinkedNode<E>) super.removeAtIndex(index); 
        if ((DoublyLinkedNode<E>) nodeRemoved.next != null) 
            ((DoublyLinkedNode<E>) nodeRemoved.next).prev 
                 = nodeRemoved.prev; 
        return nodeRemoved; 
    } 

This is where a doubly linked list really shines. This is the reason we got started with a doubly linked list. And it's not even a lot of code. Check this out:

    public Node<E> removeLast() { 
        Node<E> origLast = last; 
        if(last==null){ 
            throw new IllegalStateException
                          ("Removing element from an empty list"); 
        } 

Just use the fact that we have access to the previous node's reference and we can update the last reference very easily:

        last = ((DoublyLinkedNode<E>)last).prev; 

If the list is not empty after removal, set the next reference of the new last element to null. If the new list is empty instead, update the first element as well:

        if(last!=null){ 
            last.next = null; 
        } else{ 
            first = null; 
        } 

Don't forget to update the length:

        length--; 
        return origLast;
    }

We don't need a new figure to understand the update of the references as they are really similar to the removal process of the first element. The only difference from the singly linked list is that in the case of a singly linked list, we need to walk all the way to the end of the list to find the previous element of the list. However, in the case of a doubly linked list, we can update it in one step because we always have access to the previous node's reference. This drastically reduces the running time from O(n) in the case of a singly linked list to O(1) in the case of a doubly linked list.