Insert at End of Doubly Linked List in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions.

beginner

What steps are needed to insert a new node at the end of a doubly linked list?

1. Create a new node with the given data.
2. If the list is empty, make the new node the head.
3. Otherwise, traverse to the last node.
4. Set the last node's next pointer to the new node.
5. Set the new node's previous pointer to the last node.
6. Set the new node's next pointer to nullptr.

intermediate

Why do we need to update both next and previous pointers when inserting at the end?

Because each node points forward and backward, we must update the last node's next pointer to the new node and the new node's previous pointer back to the last node. This keeps the list connected in both directions.

intermediate

What happens if you forget to set the new node's previous pointer when inserting at the end?

The new node will not link back to the list properly. This breaks backward traversal and can cause errors when moving backward through the list.

beginner

Show the C++ code snippet to create a new node for a doubly linked list.

struct Node {
int data;
Node* next;
Node* prev;
Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

What pointer of the last node should be updated when inserting at the end?

A tail

B next

C head

D prev

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

If the doubly linked list is empty, what should the new node become?

A The previous node

B The tail only

C A disconnected node

D The head of the list

When the list is empty, the new node becomes the head (and tail) of the list.

Which pointer of the new node must be set to the last node?

A prev

B next

C head

D tail

The new node's prev pointer must point to the last node to maintain backward links.

What is the next pointer of the new node after insertion at the end?

A Points to the head

B Points to the previous node

C Null (nullptr)

D Points to itself

The new node is the last node, so its next pointer should be null.

Which of these is NOT a part of a doubly linked list node?

A Random pointer

B Data

C Previous pointer

D Next pointer

A standard doubly linked list node does not have a random pointer.

Explain how to insert a new node at the end of a doubly linked list.

Think about how the pointers connect nodes forward and backward.

Describe what happens to the pointers when inserting at the end of a doubly linked list.

Focus on how the new node links with the existing list.

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 structure of a doubly linked list

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

2. Step 2: Purpose of insertion at the end

   Inserting at the end means adding a new node after the current last node, updating pointers accordingly.

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 at end reverses the list
• Assuming insertion happens at the start

2. Which of the following is the correct way to update the tail pointer when inserting a new node at the end of a doubly linked list in C++?

easy

A. tail = NULL;

B. tail = tail->prev;

C. tail = head;

D. tail = newNode;

Solution

1. Step 1: Identify the new tail after insertion

   When a new node is added at the end, it becomes the new tail of the list.

2. Step 2: Update the tail pointer

   Assign the tail pointer to point to the new node to reflect the updated end of the list.

3. Final Answer:

   tail = newNode; -> Option D

4. Quick Check:

   New tail points to newNode [OK]

Hint: Tail always points to the last inserted node [OK]

Common Mistakes:

• Setting tail to previous node instead of new node
• Resetting tail to head incorrectly
• Assigning tail to NULL after insertion

3. What will be the output of the following code snippet after inserting 30 at the end of the doubly linked list?

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

Node* head = new Node{10, NULL, NULL};
Node* tail = head;

Node* newNode = new Node{30, tail, NULL};
tail->next = newNode;
tail = newNode;

// Print list from head
Node* temp = head;
while(temp != NULL) {
  std::cout << temp->data << " ";
  temp = temp->next;
}

medium

A. 10 30

B. 30 10

C. 10

D. 30

Solution

1. Step 1: Initial list and insertion

   Initially, list has one node with data 10. New node with 30 is added at end, linked properly.

2. Step 2: Traversing and printing

   Starting from head (10), print data then move to next node (30), print data, then NULL ends loop.

3. Final Answer:

   10 30 -> Option A

4. Quick Check:

   List after insertion = 10 30 [OK]

Hint: Traverse from head to see all nodes in order [OK]

Common Mistakes:

• Printing nodes in reverse order
• Not updating tail->next pointer
• Forgetting to update tail pointer

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

void insertEnd(Node*& head, Node*& tail, int val) {
  Node* newNode = new Node{val, NULL, NULL};
  if (head == NULL) {
    head = newNode;
    tail = newNode;
  } else {
    tail->next = newNode;
    newNode->prev = tail;
    head = newNode;  // Error here
  }
}

medium

A. head should be updated to newNode

B. newNode->prev should be NULL

C. tail should be updated to newNode

D. tail->next should be NULL

Solution

1. Step 1: Analyze pointer updates in else block

   tail->next points to newNode and newNode->prev points to tail correctly.

2. Step 2: Identify incorrect pointer assignment

   head is wrongly updated to newNode; it should remain unchanged. Instead, tail should be updated to newNode.

3. Final Answer:

   tail should be updated to newNode -> Option C

4. Quick Check:

   Tail points to last node after insertion [OK]

Hint: Update tail, not head, when inserting at end [OK]

Common Mistakes:

• Updating head instead of tail
• Not linking newNode's prev pointer
• Forgetting to set tail->next

5. Given a doubly linked list with nodes 5 <-> 10 <-> 15, write the sequence of node values after inserting 20 at the end and then 2 at the end. What is the final list?

hard

A. 2 <-> 5 <-> 10 <-> 15 <-> 20

B. 5 <-> 10 <-> 15 <-> 20 <-> 2

C. 5 <-> 10 <-> 15 <-> 2 <-> 20

D. 20 <-> 2 <-> 5 <-> 10 <-> 15

Solution

1. Step 1: Insert 20 at the end

   Starting list: 5 <-> 10 <-> 15. After inserting 20 at end: 5 <-> 10 <-> 15 <-> 20.

2. Step 2: Insert 2 at the end

   Now add 2 at end: 5 <-> 10 <-> 15 <-> 20 <-> 2.

3. Final Answer:

   5 <-> 10 <-> 15 <-> 20 <-> 2 -> Option B

4. Quick Check:

   Insertions add nodes at list end in order [OK]

Hint: Insertions add nodes at the end, order preserved [OK]

Common Mistakes:

• Inserting new nodes at the start instead of end
• Mixing order of inserted nodes
• Confusing next and prev pointers