Double Linked List

The advantage of a doubly linked list (also called two – way linked list) is that given a node in the list, we can navigate in both directions.

The primary disadvantages of doubly linked lists are:

• Each node requires an extra pointer, requiring more space.
• The insertion or deletion of a node takes a bit longer (more pointer operations).

Type declaration for a doubly linked list of integers:

Doubly Linked List Insertion 

Insertion into a doubly-linked list has three cases (same as singly linked list): 

• Inserting a new node before the head. 
• Inserting a new node after the tail (at the end of the list). 
• Inserting a new node at the middle of the list.

Inserting a new node at the middle of the list.

curr_node = 15

new_node = data

next_node  = 7 (next_node = curr_node->next;)

1. new_node->next = next_node;
2. new_node->prev = curr_node;
3. next_node->prev = new_node;
4. curr_node->next = new_node;

See Complete ADT

Complexity for both Insertion and Deletion

Time Complexity: O( n), for scanning the complete list of size n. 

Space Complexity: O( 1), for creating one temporary variable.