Insert at End of Doubly Linked List in DSA C

Mental Model

A doubly linked list has nodes connected both forward and backward. To add a new node at the end, we link it after the last node and update pointers.

Analogy: Imagine a train where each carriage is connected to the one before and after. Adding a new carriage at the end means hooking it to the last carriage and making sure both know about each other.

head -> [1] ↔ [2] ↔ [3] ↔ null
null ← [1] ↔ [2] ↔ [3] ← tail

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at end

Goal: Add a new node with value 4 at the end of the doubly linked list

Step 1: Create new node with value 4

head -> [1] ↔ [2] ↔ [3] ↔ null    [4] (new node, prev=null, next=null)
null ← [1] ↔ [2] ↔ [3] ← tail

Why: We need a new node ready to be linked at the end

Step 2: Traverse from head to last node (3)

head -> [1] ↔ [2] ↔ [3] (current) ↔ null    [4] (new node)
null ← [1] ↔ [2] ↔ [3] ← tail

Why: We must find the last node to attach the new node after it

Step 3: Set last node's next pointer to new node

head -> [1] ↔ [2] ↔ [3] -> [4] (new node)
null ← [1] ↔ [2] ↔ [3] ←-> [4]

Why: Link last node forward to new node

Step 4: Set new node's prev pointer to last node

head -> [1] ↔ [2] ↔ [3] ↔ [4]
null ← [1] ↔ [2] ↔ [3] ←-> [4]

Why: Link new node backward to last node

Step 5: Set new node's next pointer to null (end)

head -> [1] ↔ [2] ↔ [3] ↔ [4] -> null
null ← [1] ↔ [2] ↔ [3] ←-> [4] ← tail

Why: Mark new node as the last node

Result:

head -> [1] ↔ [2] ↔ [3] ↔ [4] -> null
null ← [1] ↔ [2] ↔ [3] ←-> [4] ← tail

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for doubly linked list
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// Function to create a new node with given data
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the end of the doubly linked list
void insertAtEnd(Node** head_ref, int data) {
    Node* newNode = createNode(data); // create new node

    if (*head_ref == NULL) {
        *head_ref = newNode; // list empty, new node is head
        return;
    }

    Node* temp = *head_ref;
    while (temp->next != NULL) {
        temp = temp->next; // advance to last node
    }

    temp->next = newNode; // link last node forward
    newNode->prev = temp; // link new node backward
}

// Function to print the doubly linked list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d", temp->data);
        if (temp->next != NULL) {
            printf(" ↔ ");
        }
        temp = temp->next;
    }
    printf(" -> null\n");
}

int main() {
    Node* head = NULL;

    // Create initial list 1 ↔ 2 ↔ 3
    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);

    // Insert 4 at end
    insertAtEnd(&head, 4);

    // Print final list
    printList(head);

    return 0;
}

Node* newNode = createNode(data); // create new node

create new node with given data

if (*head_ref == NULL) { *head_ref = newNode; // list empty, new node is head return; }

handle empty list by making new node the head

while (temp->next != NULL) { temp = temp->next; // advance to last node }

traverse to last node in list

temp->next = newNode; // link last node forward

link last node's next to new node

newNode->prev = temp; // link new node backward

link new node's prev to last node

Output

1 ↔ 2 ↔ 3 ↔ 4 -> null

Complexity Analysis

Time: O(n) because we traverse the list from head to last node once

Space: O(1) because we only create one new node and use constant extra space

vs Alternative: Compared to inserting at the beginning which is O(1), inserting at end requires traversal making it O(n)

Edge Cases

empty list

new node becomes the head and only node

DSA C

if (*head_ref == NULL) {
        *head_ref = newNode; // list empty, new node is head
        return;
    }

single element list

new node is linked after the single node correctly

DSA C

while (temp->next != NULL) {
        temp = temp->next; // advance to last node
    }

When to Use This Pattern

When you need to add an element at the end of a doubly linked list, use traversal to find the last node and update pointers to insert.

Common Mistakes

Mistake: Not updating the new node's prev pointer to point back to the last node
Fix: Set newNode->prev = temp after linking last node's next to new node

Mistake: Not handling empty list case, causing null pointer errors
Fix: Check if head is NULL and assign new node as head before traversal

Summary

Adds a new node at the end of a doubly linked list by updating next and prev pointers.

Use when you want to append data to the tail of a doubly linked list.

The key is to find the last node and link the new node both forward and backward.

Practice

1. What is the main purpose of inserting a node at the end of a doubly linked list?

easy

A. To add a new element after the last node

B. To remove the first node

C. To reverse the list

D. To find the middle node

Solution

1. Step 1: Understand the list structure

   A doubly linked list has nodes connected forward and backward, allowing traversal in both directions.

2. Step 2: Purpose of insertion at end

   Inserting at the end means adding a new node after the last node, extending the list.

3. Final Answer:

   To add a new element after the last node -> Option A

4. Quick Check:

   Insert at end = add after last node [OK]

Hint: Insert at end means add after last node [OK]

Common Mistakes:

• Confusing insertion at end with deletion
• Thinking insertion happens at the start
• Mixing up singly and doubly linked list operations

2. Which of the following is the correct way to update the 'next' pointer of the last node when inserting a new node at the end in C?

easy

A. last->next = newNode;

B. newNode->next = last;

C. last->prev = newNode;

D. newNode->prev = NULL;

Solution

1. Step 1: Identify the last node's next pointer

   The last node's 'next' pointer should point to the new node to link it at the end.

2. Step 2: Correct pointer assignment

   Assigning 'last->next = newNode;' correctly links the new node after the last node.

3. Final Answer:

   last->next = newNode; -> Option A

4. Quick Check:

   Last node's next points to new node [OK]

Hint: Last node's next points to new node [OK]

Common Mistakes:

• Assigning newNode->next to last (wrong direction)
• Changing last->prev instead of last->next
• Setting newNode->prev to NULL instead of last

3. What will be the output of the following code snippet after inserting a node with value 5 at the end of the doubly linked list 1 <-> 3 <-> 4?

struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

void insertEnd(struct Node** head, int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = NULL;
  if (*head == NULL) {
    newNode->prev = NULL;
    *head = newNode;
    return;
  }
  struct Node* temp = *head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = newNode;
  newNode->prev = temp;
}

void printList(struct Node* head) {
  while (head != NULL) {
    printf("%d ", head->data);
    head = head->next;
  }
}

int main() {
  struct Node* head = malloc(sizeof(struct Node));
  head->data = 1; head->prev = NULL;
  struct Node* second = malloc(sizeof(struct Node));
  second->data = 3; second->prev = head; head->next = second;
  struct Node* third = malloc(sizeof(struct Node));
  third->data = 4; third->prev = second; second->next = third; third->next = NULL;
  insertEnd(&head, 5);
  printList(head);
  return 0;
}

medium

A. 1 3 4 0

B. 1 3 4 5

C. 1 3 4

D. 5 1 3 4

Solution

1. Step 1: Understand initial list and insertion

   The list is 1 <-> 3 <-> 4. The function inserts 5 at the end by traversing to last node (4) and linking new node after it.

2. Step 2: Trace printList output

   After insertion, list is 1 <-> 3 <-> 4 <-> 5. Printing nodes in order outputs "1 3 4 5 "

3. Final Answer:

   1 3 4 5 -> Option B

4. Quick Check:

   List after insertEnd = 1 3 4 5 [OK]

Hint: Traverse to last, link new node, print all nodes [OK]

Common Mistakes:

• Not setting newNode->prev correctly
• Forgetting to set last node's next to newNode
• Printing before insertion

4. Identify the error in the following code snippet for inserting a node at the end of a doubly linked list:

void insertEnd(struct Node** head, int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = NULL;
  if (*head == NULL) {
    *head = newNode;
    return;
  }
  struct Node* temp = *head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = newNode;
}

medium

A. Wrong condition in while loop

B. Incorrect malloc size

C. Missing setting newNode->prev pointer

D. Not updating head pointer

Solution

1. Step 1: Check pointer assignments for doubly linked list

   In doubly linked list, newNode->prev must point to the last node (temp) after insertion.

2. Step 2: Identify missing pointer update

   The code sets temp->next = newNode but does not set newNode->prev = temp, breaking backward link.

3. Final Answer:

   Missing setting newNode->prev pointer -> Option C

4. Quick Check:

   newNode->prev must be set [OK]

Hint: Always set newNode->prev to last node [OK]

Common Mistakes:

• Forgetting newNode->prev assignment
• Assuming singly linked list logic applies
• Not handling empty list case

5. Given a doubly linked list with nodes 10 <-> 20 <-> 30, write the sequence of pointer changes when inserting a new node with value 40 at the end. Which of the following correctly describes the final connections?

hard

A. newNode->prev = NULL; newNode->next = NULL; last->next = NULL

B. newNode->next = last; last->prev = newNode; newNode->prev = NULL

C. last->prev = newNode; newNode->next = last; newNode->prev = NULL

D. last->next = newNode; newNode->prev = last; newNode->next = NULL

Solution

1. Step 1: Identify last node and new node pointers

   Last node is 30. New node 40 should be linked after 30 with next NULL.

2. Step 2: Correct pointer assignments

   Set last->next = newNode to link forward, newNode->prev = last for backward link, and newNode->next = NULL as it is new end.

3. Final Answer:

   last->next = newNode; newNode->prev = last; newNode->next = NULL -> Option D

4. Quick Check:

   New node linked after last with proper prev and next [OK]

Hint: New node's prev = last; last's next = new node; new node's next = NULL [OK]

Common Mistakes:

• Reversing prev and next pointers
• Setting newNode->prev to NULL incorrectly
• Not setting last->next to newNode