Doubly Linked List

1. Double Linked List vs Linked List
2. Doubly Linked List Traversal Algorithm
3. Doubly Linked List Insertion
4. Doubly Linked List Insertion Illustration
5. Doubly Linked List Traversal & Insertion Implementation
6. Doubly Linked List Traversal & Insertion Algorithm Complexity

A Doubly Linked List is a linear data structure. It is a collection of objects defined as nodes. But unlike the linked list, the node has two pointers, one previous pointer and the other next pointer. Just like linked list nodes are stored in random positions in memory and not stored in contiguous locations.

Double Linked List vs Linked List

1. Double-linked lists allow us to traverse the linked list in both forward and backward directions, but it comes at the cost of extra space required by the prev pointer for every node.
2. It is very easy to insert elements inside a doubly linked list as we do not have to maintain multiple pointers or traverse linked lists to find the previous pointer, but we do have to modify more pointers as compared to the linked list.

Doubly Linked List Traversal Algorithm

Forward Direction

Let the head be the first node of the linked list.

Similarly, we can do the backward traversal by starting from the tail and changing curr to curr->prev.

Reverse Direction

Let the tail be the last node of the linked list.

Doubly Linked List Insertion

There are 4 cases for the doubly linked list for inserting elements just like linked lists.

Insert Node at the Head of the DLL push()

Insert Node at the End of the DLL append()

Insert Node Before a Given Node insertBefore()

Insert Node After a Given Node insertAfter()

Doubly Linked List Insertion Illustration

Insert Node at the Head of the DLL push()

Insert Node at the End of the DLL append()

Insert Node Before a Given Node insertBefore()

Insert Node After a Given Node insertAfter()

Doubly Linked List Traversal & Insertion Implementation

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node* next;
  Node* prev;
};

void push(Node** head, int x) {
  Node* curr = new Node();
  curr->data = x;
  curr->next = (*head);
  curr->prev = NULL;
  if ((*head) != NULL) (*head)->prev = curr;
  (*head) = curr;
}
void insertAfter(Node* prev, int x) {
  if (prev == NULL) {
    cout << "the given previous node cannot be NULL";
    return;
  }

  Node* curr = new Node();
  curr->data = x;
  curr->next = prev->next;
  prev->next = curr;
  curr->prev = prev;
  if (curr->next != NULL) curr->next->prev = curr;
}

void insertBefore(struct Node** head, struct Node* next, int x) {
  if (next == NULL) {
    return;
  }

  Node* curr = new Node();
  curr->data = x;
  curr->prev = next->prev;
  next->prev = curr;
  curr->next = next;
  if (curr->prev != NULL)
    curr->prev->next = curr;
  else
    (*head) = curr;
}

void append(Node** head, int x) {
  Node* curr = new Node();
  Node* tail = *head;
  curr->data = x;
  curr->next = NULL;
  if (*head == NULL) {
    curr->prev = NULL;
    *head = curr;
    return;
  }
  while (tail->next != NULL) tail = tail->next;
  tail->next = curr;
  curr->prev = tail;
  return;
}

void printList(Node* node) {
  Node* tail = NULL;
  cout << "Forward Traversal:";
  while (node != NULL) {
    cout << " " << node->data << " ";
    tail = node;
    node = node->next;
  }

  cout << "\nReverse Traversal:";
  while (tail != NULL) {
    cout << " " << tail->data << " ";
    tail = tail->prev;
  }
  cout << "\n";
}

int main() {
  Node* head = NULL;
  append(&head, 6);
  push(&head, 7);
  push(&head, 1);
  append(&head, 4);
  printList(head);
  insertAfter(head->next, 8);
  insertBefore(&head, head->next->next, 3);
  printList(head);
  return 0;
}

Doubly Linked List Traversal & Insertion Algorithm Complexity

Traversal

Time Complexity

• Average Case

To traverse the complete doubly linked list, we have to visit every node. So, if it has n nodes the average-case time complexity of traversal is of the order of O(n). The time complexity is of the order of O(n).

• Best Case

The best-case time complexity is O(n). It is the same as average-case time complexity.

• Worst Case

The worst-case time complexity is O(n). It is the same as best-case time complexity.

Space Complexity

The traversal algorithm’s space complexity is O(1) as no extra space other than curr pointer is required.

Insertion

Time Complexity

• Average Case

The insertion of an element for all 4 cases requires a maximum of 4 link changes, and hence the time complexity of insertion is O(1).

• Best Case

The best-case time complexity is O(1). It is the same as average-case time complexity.

• Worst Case

The worst-case time complexity is O(1). It is the same as best-case time complexity.

Space Complexity

The insertion algorithm’s space complexity is O(1) for all 4 types of insertion.