Delete from End of Doubly Linked List in DSA C++ - Build from Scratch

Delete from End of Doubly Linked List

📖 Scenario: You are managing a playlist of songs using a doubly linked list. Each song is a node with a title. You want to remove the last song from the playlist.

🎯 Goal: Build a doubly linked list with three songs, then delete the last song from the list, and finally print the updated playlist.

📋 What You'll Learn

Create a doubly linked list with nodes containing song titles: "Song1", "Song2", "Song3"

Add a pointer variable tail to track the last node

Write a function deleteFromEnd to remove the last node from the list

Print the playlist from head to tail after deletion

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers, and other apps to move forward and backward through items efficiently.

💼 Career

Understanding linked list operations is fundamental for software developers working on data structures, memory management, and system programming.

1

Create the doubly linked list with three songs

Create a struct called Node with string title, Node* prev, and Node* next. Then create three nodes with titles "Song1", "Song2", and "Song3". Link them to form a doubly linked list with head pointing to the first node.

DSA C++

// Define Node struct and create doubly linked list with three songs
// Your code here

Hint

Remember to set prev and next pointers correctly to link nodes both ways.

2

Add a tail pointer to track the last node

Add a pointer variable called tail and set it to point to the last node in the list, which is the node with title "Song3".

DSA C++

#include 
#include 
using namespace std;

struct Node {
    string title;
    Node* prev;
    Node* next;
};

int main() {
    Node* head = new Node{"Song1", nullptr, nullptr};
    Node* second = new Node{"Song2", head, nullptr};
    Node* third = new Node{"Song3", second, nullptr};
    head->next = second;
    second->next = third;

    Node* tail = nullptr; // Your code here

    return 0;
}

Hint

Set tail to the last node created, which is third.

3

Write a function to delete the last node

Write a function called deleteFromEnd that takes Node*& head and Node*& tail as parameters. Inside the function, remove the last node from the list by updating pointers and deleting the node. Handle the case when the list becomes empty by setting head and tail to nullptr. Call this function from main.

DSA C++

#include 
#include 
using namespace std;

struct Node {
    string title;
    Node* prev;
    Node* next;
};

// Your code here

int main() {
    Node* head = new Node{"Song1", nullptr, nullptr};
    Node* second = new Node{"Song2", head, nullptr};
    Node* third = new Node{"Song3", second, nullptr};
    head->next = second;
    second->next = third;

    Node* tail = third;

    // Call deleteFromEnd here

    return 0;
}

Hint

Remember to update tail to the previous node and set its next to nullptr. If the list has only one node, set both head and tail to nullptr.

4

Print the playlist after deleting the last song

Use a for loop with a variable current starting at head to traverse the list. Print each node's title followed by " -> ". After the loop, print "null" to show the end of the list.

DSA C++

#include 
#include 
using namespace std;

struct Node {
    string title;
    Node* prev;
    Node* next;
};

void deleteFromEnd(Node*& head, Node*& tail) {
    if (tail == nullptr) {
        return; // List empty
    }
    Node* toDelete = tail;
    if (head == tail) {
        head = nullptr;
        tail = nullptr;
    } else {
        tail = tail->prev;
        tail->next = nullptr;
    }
    delete toDelete;
}

int main() {
    Node* head = new Node{"Song1", nullptr, nullptr};
    Node* second = new Node{"Song2", head, nullptr};
    Node* third = new Node{"Song3", second, nullptr};
    head->next = second;
    second->next = third;

    Node* tail = third;

    deleteFromEnd(head, tail);

    // Your code here
}

Hint

Use a loop starting from head and print each title followed by " -> ". After the loop, print "null".

Practice

1. What happens to the tail pointer when you delete the last node from a doubly linked list?

easy

A. It moves to the previous node of the deleted node

B. It becomes null immediately

C. It points to the head node

D. It remains unchanged

Solution

1. Step 1: Understand the tail pointer role

   The tail pointer always points to the last node in the list.

2. Step 2: Effect of deleting the last node

   When the last node is deleted, the tail must move to the previous node to remain the last node.

3. Final Answer:

   It moves to the previous node of the deleted node -> Option A

4. Quick Check:

   Tail updates to previous node after deletion [OK]

Hint: Tail always points to last node, update to previous on delete [OK]

Common Mistakes:

• Setting tail to null without checking if list is empty
• Not updating tail pointer after deletion
• Pointing tail to head incorrectly

2. Which of the following is the correct syntax to delete the last node in a doubly linked list in C++?

easy

A. tail->prev = tail; delete tail; tail = nullptr;

B. delete tail; tail = tail->prev; tail->next = nullptr;

C. tail = tail->prev; delete tail->next; tail->next = nullptr;

D. tail->next = nullptr; delete tail; tail = tail->prev;

Solution

1. Step 1: Identify correct order of operations

   First, move tail pointer to previous node, then delete the old last node, and finally set new tail's next to nullptr.

2. Step 2: Match with options

   tail = tail->prev; delete tail->next; tail->next = nullptr; correctly moves tail, deletes old node, and updates next pointer.

3. Final Answer:

   tail = tail->prev; delete tail->next; tail->next = nullptr; -> Option C

4. Quick Check:

   Move tail first, then delete old node [OK]

Hint: Move tail before deleting old node to avoid dangling pointer [OK]

Common Mistakes:

• Deleting tail before moving pointer causes invalid access
• Not setting tail->next to nullptr after deletion
• Incorrect pointer assignments causing memory leaks

3. What will be the output of the following code snippet after deleting the last node?

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

Node* head = new Node{1, nullptr, nullptr};
Node* second = new Node{2, head, nullptr};
head->next = second;
Node* tail = second;

// Delete last node
Node* temp = tail;
tail = tail->prev;
tail->next = nullptr;
delete temp;

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

medium

A. 1 2

B. No output (empty list)

C. 2

D. 1

Solution

1. Step 1: Understand list before deletion

   List has two nodes: 1 (head) -> 2 (tail).

2. Step 2: Delete last node and update pointers

   Last node (2) is deleted, tail moves to node 1, and tail->next is set to nullptr.

3. Step 3: Print remaining list

   Only node 1 remains, so output is "1".

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Last node deleted, only head remains [OK]

Hint: After deleting tail, print from head to see remaining nodes [OK]

Common Mistakes:

• Printing deleted node due to not updating tail->next
• Assuming list is empty after deletion
• Confusing head and tail pointers

4. Identify the error in the following code that deletes the last node of a doubly linked list:

void deleteEnd(Node*& tail) {
  delete tail;
  tail = tail->prev;
  tail->next = nullptr;
}

medium

A. Not updating head pointer causes memory leak

B. Accessing tail->prev after deleting tail causes undefined behavior

C. tail->next should be set to tail->prev

D. No error, code is correct

Solution

1. Step 1: Analyze order of operations

   The code deletes tail first, then tries to access tail->prev which is invalid after deletion.

2. Step 2: Correct approach

   First move tail pointer to previous node, then delete the old tail node, and update pointers.

3. Final Answer:

   Accessing tail->prev after deleting tail causes undefined behavior -> Option B

4. Quick Check:

   Delete after pointer update to avoid invalid access [OK]

Hint: Move pointer before delete to avoid invalid memory access [OK]

Common Mistakes:

• Deleting node before updating pointers
• Not checking if tail is nullptr before access
• Confusing order of pointer updates and deletion

5. Given a doubly linked list with nodes containing values [10, 20, 30, 40], write the steps to delete the last node and update the list correctly. What will be the final list after deletion?

hard

A. [10, 20, 30]

B. [10, 20, 30, 40]

C. [20, 30, 40]

D. [10, 20, 40]

Solution

1. Step 1: Identify the last node and tail pointer

   The last node has value 40, tail points to it.

2. Step 2: Move tail pointer to previous node and delete last node

   Tail moves to node with value 30, delete node 40, set tail->next to nullptr.

3. Step 3: Final list after deletion

   List nodes are now 10 -> 20 -> 30 with tail at 30.

4. Final Answer:

   [10, 20, 30] -> Option A

5. Quick Check:

   Last node removed, tail updated, list shortened [OK]

Hint: Delete last node, move tail back, set tail->next null [OK]

Common Mistakes:

• Not updating tail->next to nullptr
• Deleting wrong node or skipping pointer updates
• Assuming list shrinks from head instead of tail