Doubly Linked List – Insert Operation

Linked Lists

Contents

IntroExamplePseudocodeExamplesTimeSpace

Insert Operation in Doubly Linked List

Insertion in a doubly linked list means adding a new node at a specific position—either at the beginning, in the middle, or at the end of the list.

Unlike singly linked lists, each node in a doubly linked list has two pointers: next and prev. When inserting a node, both pointers must be carefully updated to preserve the two-way connectivity.

Visual Example

Suppose we have a doubly linked list:

We want to insert 30 at index 2, so the final list becomes: 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ null

Step-by-Step Insertion at Index 2

  1. Start with the doubly linked list 10 ⇄ 20 ⇄ 40 ⇄ null.
  2. Traverse to the node at index 1 (value 20).
  3. Create a new node with value 30.
  4. Set newNode.next = current.next (i.e., 30 points forward to 40).
  5. Set newNode.prev = current (i.e., 30 points back to 20).
  6. Set current.next.prev = newNode (i.e., 40’s previous becomes 30).
  7. Set current.next = newNode (i.e., 20’s next becomes 30).

Complete Pseudocode: Insert Node in Doubly Linked List

This pseudocode shows how to insert a node at a specific index in a doubly linked list.

function insertAt(head, index, value):
    newNode = new DoublyListNode(value)

    if index == 0:
        newNode.next = head
        if head != null:
            head.prev = newNode
        return newNode

    curr = head
    for i in range(index - 1):
        curr = curr.next

    newNode.next = curr.next
    newNode.prev = curr
    if curr.next != null:
        curr.next.prev = newNode
    curr.next = newNode

    return head

Let’s walk through each part of the code to understand what it does.

function insertAt(head, index, value):
    newNode = new DoublyListNode(value)

Explanation: We define a function to insert a new node at a given index in a doubly linked list. A new node is created with the specified value.

    if index == 0:
        newNode.next = head
        if head != null:
            head.prev = newNode
        return newNode

Explanation: If the index is 0, the new node becomes the new head. We update the next and prev links appropriately and return the new node as the head.

    curr = head
    for i in range(index - 1):
        curr = curr.next

Explanation: If we're inserting elsewhere, we move curr to the node just before the desired index using a loop.

    newNode.next = curr.next
    newNode.prev = curr
    if curr.next != null:
        curr.next.prev = newNode
    curr.next = newNode

Explanation: After locating the correct position, we update the forward and backward links. We ensure that the previous and next pointers on both sides of the new node are properly adjusted.

    return head

Explanation: Finally, we return the unchanged head of the list so the outer structure remains intact and usable.

Doubly Linked List Insert Operation Examples

The following examples demonstrate how to insert a new node at various positions in a doubly linked list. Each node maintains both prev and next links.

Initial List Insert Index Insert Value Final Linked List Explanation
[10, 20, 30] 0 5 null ← 5 ⇄ 10 ⇄ 20 ⇄ 30 → null Insert at the beginning. New node becomes the new head. Its next points to the old head, and the old head's prev is updated.
[10, 20, 30] 2 25 10 ⇄ 20 ⇄ 25 ⇄ 30 Insert in the middle. New node's prev and next pointers link to neighbors; neighbors update their links accordingly.
[10, 20, 30] 3 35 10 ⇄ 20 ⇄ 30 ⇄ 35 → null Insert at the end. New node's prev points to the old tail, and the old tail’s next points to the new node.
[10, 20, 30] 5 50 Error Invalid index. The index is beyond the list size. The operation should fail gracefully or throw an error.

Time Complexity of Doubly Linked List Insert Operation

Insertion Case Time Complexity Explanation
Insert at Beginning O(1) We update the new node’s next to point to the current head and its prev to null. Then update the head’s prev and move head to the new node.
Insert at Middle O(n) We traverse the list to the desired position. Once there, we adjust both prev and next pointers of surrounding nodes and the new node.
Insert at End (without tail pointer) O(n) We traverse the list to the last node and attach the new node by updating next and prev pointers.
Insert at End (with tail pointer) O(1) With a tail pointer, we can insert the new node directly after the last node and update the tail reference.

Space Complexity of Doubly Linked List Insert Operation

Insertion Case Space Complexity Explanation
Insert at Beginning O(1) Only one new node is created. Although the node has two pointers (prev and next), they are part of the node structure and do not add extra asymptotic space.
Insert at Middle O(1) Space remains constant since only one node is added, regardless of position. The new node’s prev and next pointers are set appropriately.
Insert at End O(1) Inserting at the end involves creating a single node with two pointers, which still requires constant space.

Key Takeaways

  • Doubly linked lists allow traversal in both directions using prev and next pointers.
  • Each insertion involves updating up to four pointers: the prev and next of the new node, and possibly the neighboring nodes.
  • Insert at Beginning: Update the new node’s next to point to the current head, and set the head’s prev to the new node.
  • Insert at End: Traverse to the last node (unless a tail pointer is maintained), and update the new node and last node’s pointers accordingly.
  • Insert in Middle: Requires traversing to the target position, then carefully rewiring the prev and next pointers of the surrounding nodes.
  • Insertion operations take O(1) space, regardless of position.
  • Always handle edge cases like inserting into an empty list or inserting before/after null pointers.

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...