Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Operations on Doubly Linked List
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

A doubly linked list is a data structure where each node contains three parts:

  • Data (the stored value)
  • Next pointer (points to the next node)
  • Prev pointer (points to the previous node)

This bidirectional structure allows traversal in both forward and backward directions and simplifies some operations like deletion.

1. Traversal in a Doubly Linked List

Traversal in a doubly linked list means visiting each node in sequence. We can traverse in two ways:

  • Forward Traversal: Start from the head and follow the next pointers until reaching the end.
  • Reverse Traversal: Start from the tail (last node) and follow the prev pointers until reaching the beginning.

Step-by-Step Algorithm for Forward Traversal

  • Step 1: Initialize a pointer current to the head node.
  • Step 2: While current is not NULL:
    • Print or process the value stored in current.
    • Move current to current.next.
  • Step 3: End when current becomes NULL.

Step-by-Step Algorithm for Reverse Traversal

  • Step 1: Initialize a pointer current to the head and traverse to the last node (where current.next is NULL).
  • Step 2: While current is not NULL:
    • Print or process the value stored in current.
    • Move current to current.prev.
  • Step 3: End when current becomes NULL.

Code

Python3
Python3
. . . .

✅ Time Complexity: O(n) for both forward and reverse traversals (each node is visited once).
✅ Space Complexity: O(1) (Only a pointer is used for traversal).

2. Insertion in a Doubly Linked List

Insertion in a doubly linked list involves adding a new node at a specified position. Due to the bidirectional pointers, updating the list requires adjusting both next and prev pointers. This operation can be done at the beginning, end, or any middle position.

Step-by-Step Algorithm for Insertion at a Specific Position

  1. Create a new node with the given value.

  2. If inserting at position 0 (beginning):

    • Set newNode.next to point to the current head.
    • If the list isn’t empty, update head.prev to point back to newNode.
    • Update head to point to newNode.
    • This makes the new node the first element.

  3. Otherwise:

    • Traverse the list to find the node at position (position - 1).
      • Start from head and move forward until the desired node is reached.
      • Here, we need the node after which the new node will be inserted.
    • If the target position is invalid (beyond the list length), print an error and exit.

  4. Insert the new node:

    • Link the New Node Forward: Make the new node point to the node that comes after the previous node (i.e., set newNode.next to previous.next).
    • Link the Previous Node to the New Node: Change the previous node so that it now points to the new node (i.e., set previous.next to newNode).
    • Link the New Node Backward: If there is a node after the new node, update its prev pointer to point to the new node (i.e., set previous.next.prev to newNode).
    • Set the New Node’s Backward Link: Finally, set the new node’s prev pointer to the previous node.

Code

Python3
Python3
. . . .

✅ Time Complexity: O(n) due to traversal (worst-case for middle or end insertion).
✅ Space Complexity: O(1) as no extra space is used.

3. Deletion in a Doubly Linked List

Deletion in a doubly linked list involves removing a node while ensuring that both next and prev pointers of neighboring nodes are correctly updated. Deletion can occur at the beginning, at the end, or in the middle.

Step-by-Step Algorithm for Deletion

  1. Check if the list is empty:

    • If head is NULL, print an error and exit.

  2. If deleting the first node (position 0):

    • Update head to head.next.
    • If the new head is not NULL, set its prev pointer to NULL.
    • Deletion is complete.

  3. Otherwise, traverse to the node just before the target node (position - 1):

    • Start at head and move forward until reaching the node before the one to delete.
    • If this node or its next pointer is NULL, the position is invalid; print an error and exit.

  4. Delete the target node:

    • Identify the Node to Delete: Let target be the node immediately after the previous node (i.e., target = previous.next).
    • Skip the Target Node: Update previous.next so that it points to the node after the target (i.e., previous.next = target.next). This removes the target from the forward chain.
    • Fix Backward Link: If there is a node after the target (i.e., target.next is not NULL), update its prev pointer to point back to the previous node. This removes the target from the backward chain.

  5. Deletion is complete.

Code

Python3
Python3
. . . .

✅ Time Complexity: O(n) (Traversal required to locate node for deletion).
✅ Space Complexity: O(1) (No extra space used).

Let's start solving problems on Linkedlist.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible