Delete Operation - Doubly Linked List

If we want to delete an existing node cur from the doubly linked list, we can simply link its previous node prev with its next node next.

Unlike the singly linked list, it is easy to get the previous node in constant time with the "prev" field.

Since we no longer need to traverse the linked list to get the previous node, both the time and space complexity are O(1).

An Example

Our goal is to delete the node 6 from the doubly linked list.

So we link its previous node 23 and its next node 15:

Node 6 is not in our doubly linked list now.