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.

  • Initialize curr pointing to the head node of the linked list.
  • While curr does not reach the end of the list i.e. curr!=NULL, do the following:
    • print the data stored inside the current node.
    • curr=curr->next;
    • If the last node, store as the tail to facilitate backward traversal.

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.

  • Initialize curr pointing to the tail node of the linked list.
  • While curr does not reach the start of the list i.e. curr!=NULL, do the following:
    • print the data stored inside the current node.
    • curr=curr->prev

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()

  • Create a new node temp with data x and prev as NULL.
  • Set temp->next to head and head->prev to temp to insert temp before the head.
  • Set temp as the head of the linked list.

Insert Node at the End of the DLL append()

  • Create a new node temp with data x and its prev as NULL.
  • Initialize tail pointing towards the head.
  • If the linked list is empty, set temp as head of the linked list and return.
  • Else iterate towards the end of the linked list, such that tail->next!= NULL, so that you land at the last element
  • Set tail->next as the temp and temp->prev as the tail.

Insert Node Before a Given Node insertBefore()

  • if next == NULL, return;
  • Create a new node curr with data x.
  • Set curr->next as next and finally check if curr->prev is NULL.
  • If it is not NULL, set curr->prev->next as curr to complete the insertion else curr is the first node of the linked list. Set head as curr.

Insert Node After a Given Node insertAfter()

  • if prev == NULL, return;
  • Create a new node curr with data x.
  • Set curr->prev as prev and finally check if curr->next is NULL. If it is not NULL ,set curr->next->prev as curr to complete the insertion.

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.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Data Structure

  • Binary Search Tree Check
  • Circular Doubly Linked List
  • Related Article - Doubly Linked List

  • Binary Search Tree Inorder Succesor
  • Linked List Reversal