A DoublyLinkedList is very similar to a SinglyLinkedList with the exception that each node, u, in a DoublyLinkedList has references to both the node, u.next, and the node that precedes it, u.prev.

When implementing a SinglyLinkedList, we saw that there were, consitently, several edge cases to be concerned about. As an example, removing the last element from a SinglyLinkedList or adding an element to an empty SinglyLinkedList requires attention to ensure that head and tail are correctly updated. Conceivably, the cleanest method of catching these edge cases in a DoublyLinkedList is to introduce a dummy node. This being a node that does not contain any data, but is instead a placeholder so that there are no special nodes; every node has both a next and prev, with dummy acting as the node that follows the last node in the list and precedes the first node in the list. In this fashion, the nodes of the list are (doubly-)linked into a cycle, as illustrated in Fig.1.

Finding the node at a particular index in a DoublyLinkedList is straightforward; we can either start at the head of the list (dummy.next) and iterate forward, or start at the tail (dummy.prev) and iterate backward. This permits us to reach the ith node in O(1+min{i,n-i}) time.

The get(i) and set(i,x) operations are also straightforward. Firstly, we find the ith node and then simply get or set its x value. As the running times of these operations is dictated by the time it takes to find the ith node, and is therefore O(1+min{i,n-i}).

If we have a reference to a node, w, in a DoublyLinkedList and we want to insert a node, u, before w, it is simply a matter of setting u.next=w, u.prev=w.prev, and then altering u.prev.next and u.next.prev (see Fig.2). Due to the dummy node, there is no need to worry about w.prev or w.next not existing.

Now, implementing the list operation add(i,x) is inconsequential. We find the ith node in the list and insert a new node, u, that contains x just before it. The only non-constant part of the running time of add(i,x) is the time it takes to find the ith node. Therefore, add(i,x) also runs in O(1+min{i,n-i}) time.

Removing a node, w, from the DoublyLinkedList is also straightforward. It is simply a case of adjusting the pointers at w.next and w.prev so that they skip over w. Once again, the use of the dummy node removes the need to consider any edge cases. Now the remove(i) operation is tivial. Just find the node with index i and remove it. Again, the only expensive bit of the operation is finding the ith node using the getNode(i) operation, so remove(i) also runs in O(1+min{i,n-1}) time.

The following theorem summarizes the performance of the DoublyLinkedList:

A DoublyLinkedList implements the List interface. In this implementation, the get(i), set(i,x), add(i,x), and remove(i) operations run in O(1+min{i,n-i}) time per operation.

Significantly, if we ignore the cost of the getNode(i) operation, then all operations on a DoublyLinkedList take constant time. Therefore, the only expensive part of operations on a DoublyLinkedList is finding the relevant node. Once we have the relevant node, adding, removing or accessing the data at the node only takes constant time.

This is incredibly incongruous to the array-based List implementations. In those implementations, the relevant array item can be found in constant time. Nevertheless, addition or removal requires shifting elements in the array and, generally, takes non-constant time.

Due to this, linked list structures are advantageous in applications where references to list nodes can be obtained through external means. As an example, the LinkedHashSet data structure found in the Java Collections Framework, wherein a set of items is stored in a doubly-linked list and the nodes of the doubly-linked list are stored in a hash table. Whenever elements are removed from a LinkedHashSet, the hash table is used to find the relevant list node in constant time and then the list node is deleted (also in constant time).