Add Operation - Doubly Linked List

If we want to insert a new node cur after an existing node prev, we can divide this process into two steps:

1. link cur with prev and next, where next is the original next node of prev

re-link the prev and next with cur.

Similar to the singly linked list, both the time and the space complexity of the add operation are O(1).

An Example

Let's add a new node 9 after the existing node 6:

1. link cur (node 9) with prev (node 6) and next (node 15)

re-link prev (node 6) and next (node 15) with cur (node 9)