Create and Initialize Doubly Linked List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Doubly Linked List after Insertions

What is the printed state of the doubly linked list after inserting nodes with values 10, 20, and 30 at the end?

DSA C++

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

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void insertEnd(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) std::cout << " <-> ";
            temp = temp->next;
        }
        std::cout << " -> null" << std::endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.insertEnd(10);
    dll.insertEnd(20);
    dll.insertEnd(30);
    dll.printList();
    return 0;
}

A null

B 30 <-> 20 <-> 10 -> null

C 10 <-> 20 <-> 30 -> null

D 10 -> 20 -> 30 -> null

💡 Hint

Remember that insertEnd adds nodes at the tail, so the order is the same as insertion.

The insertEnd method adds nodes at the end, so the list prints in the order 10, 20, 30 connected with <-> arrows, ending with -> null.

❓ Predict Output

intermediate

State of Doubly Linked List after Inserting at Front

What is the printed state of the doubly linked list after inserting nodes with values 5, 15, and 25 at the front?

DSA C++

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

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void insertFront(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) std::cout << " <-> ";
            temp = temp->next;
        }
        std::cout << " -> null" << std::endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.insertFront(5);
    dll.insertFront(15);
    dll.insertFront(25);
    dll.printList();
    return 0;
}

A 25 <-> 15 <-> 5 -> null

B 5 <-> 15 <-> 25 -> null

C 25 -> 15 -> 5 -> null

D null

💡 Hint

Inserting at front means new nodes become the new head, pushing older nodes back.

Each insertFront adds a new node before the current head, so the list order is 25, 15, 5 connected with <-> arrows, ending with -> null.

🔧 Debug

advanced

Identify the Bug in Doubly Linked List Initialization

What error will this code produce when trying to insert a node at the end of the doubly linked list?

DSA C++

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

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    void insertEnd(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }
};

int main() {
    DoublyLinkedList dll;
    dll.insertEnd(10);
    return 0;
}

A No error, code runs and inserts node correctly

B Compilation error: tail is not declared

C Runtime error: segmentation fault due to uninitialized tail pointer

D Logical error: list remains empty after insertion

💡 Hint

Check if all pointers are properly initialized before use.

The tail pointer was not initialized in the constructor, which could cause runtime errors. Initializing tail to nullptr fixes this issue.

❓ Predict Output

advanced

Output after Deleting a Node from Doubly Linked List

What is the printed state of the doubly linked list after deleting the node with value 20?

DSA C++

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

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void insertEnd(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    void deleteNode(int val) {
        Node* temp = head;
        while (temp && temp->data != val) {
            temp = temp->next;
        }
        if (!temp) return;
        if (temp->prev) temp->prev->next = temp->next;
        else head = temp->next;
        if (temp->next) temp->next->prev = temp->prev;
        else tail = temp->prev;
        delete temp;
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) std::cout << " <-> ";
            temp = temp->next;
        }
        std::cout << " -> null" << std::endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.insertEnd(10);
    dll.insertEnd(20);
    dll.insertEnd(30);
    dll.deleteNode(20);
    dll.printList();
    return 0;
}

A 10 <-> 20 <-> 30 -> null

B 10 <-> 30 -> null

C 20 <-> 30 -> null

D 10 -> 30 -> null

💡 Hint

Deleting a node removes it and connects its previous and next nodes directly.

Node with value 20 is removed, so the list links 10 directly to 30 with <-> arrows, ending with -> null.

🧠 Conceptual

expert

Memory Management in Doubly Linked List

Which statement best describes the correct way to avoid memory leaks when deleting nodes in a doubly linked list implemented in C++?

A Use delete on the head pointer only after all nodes are unlinked.

B Only unlink the node from the list; the system automatically frees memory later.

C Set the node's data to zero and leave the node linked to avoid dangling pointers.

D Always delete the node pointer after unlinking it from the list to free memory.

💡 Hint

Think about what happens if you remove a node but never free its memory.

In C++, after unlinking a node from the list, you must explicitly delete it to free memory and avoid leaks.

Practice

1. What is the main purpose of a doubly linked list in data structures?

easy

A. To allow traversal in both forward and backward directions

B. To store data in a fixed-size array

C. To sort elements automatically

D. To store data only at the beginning

Solution

1. Step 1: Understand doubly linked list structure

   A doubly linked list has nodes with pointers to both previous and next nodes.

2. Step 2: Identify traversal capability

   This structure allows moving forward and backward through the list easily.

3. Final Answer:

   To allow traversal in both forward and backward directions -> Option A

4. Quick Check:

   Doubly linked list = forward and backward traversal [OK]

Hint: Remember: doubly means two directions [OK]

Common Mistakes:

• Confusing doubly linked list with arrays
• Thinking it sorts data automatically
• Assuming it only allows forward traversal

2. Which of the following is the correct way to declare a node structure for a doubly linked list in C++?

easy

A. struct Node { int data; Node prev; Node next; };

B. struct Node { int data; Node next; Node prev; };

C. struct Node { int data; Node* next; };

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

Solution

1. Step 1: Check pointer usage in node structure

   Each node must have pointers to next and previous nodes, so use Node* for both.

2. Step 2: Verify syntax correctness

   struct Node { int data; Node* next; Node* prev; }; correctly uses pointers (Node*) for next and prev, while others use incorrect types.

3. Final Answer:

   struct Node { int data; Node* next; Node* prev; }; -> Option D

4. Quick Check:

   Node pointers use * for next and prev [OK]

Hint: Use pointers (*) for next and prev nodes [OK]

Common Mistakes:

• Using Node instead of Node* for pointers
• Missing prev pointer in node
• Incorrect order of members

3. What will be the output of the following code snippet that creates a doubly linked list with two nodes and prints their data?

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

int main() {
  Node* head = new Node{10, nullptr, nullptr};
  Node* second = new Node{20, nullptr, head};
  head->next = second;
  std::cout << head->data << " -> " << second->data << " -> null";
  return 0;
}

medium

A. 20 -> 10 -> null

B. 10 -> 20 -> null

C. 10 -> null

D. Compilation error

Solution

1. Step 1: Analyze node creation and linking

   First node has data 10, second node has data 20 and points back to first node. Head's next points to second.

2. Step 2: Trace output statement

   Prints head data (10), then second data (20), then "-> null" string.

3. Final Answer:

   10 -> 20 -> null -> Option B

4. Quick Check:

   Print order matches linked list nodes [OK]

Hint: Follow pointers to print nodes in order [OK]

Common Mistakes:

• Confusing prev and next pointers
• Printing second node first
• Forgetting to set head->next

4. Identify the error in the following code that attempts to create a doubly linked list with one node:

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

int main() {
  Node* head = new Node;
  head->data = 5;
  head->next = head->prev = nullptr;
  head->prev = head;
  return 0;
}

medium

A. head->prev should not point to head itself

B. Missing initialization of head->data

C. head->next should point to head

D. Node structure is incomplete

Solution

1. Step 1: Review pointer assignments

   head->next and head->prev are set to nullptr, then head->prev is set to head itself.

2. Step 2: Identify logical error

   head->prev pointing to head creates a circular reference which is incorrect for a single node list.

3. Final Answer:

   head->prev should not point to head itself -> Option A

4. Quick Check:

   Single node prev = nullptr, not self [OK]

Hint: Single node prev and next must be nullptr [OK]

Common Mistakes:

• Setting prev or next to self causing loops
• Forgetting to initialize data
• Confusing next and prev pointers

5. You want to create a doubly linked list with three nodes containing values 1, 2, and 3 respectively. Which of the following code snippets correctly initializes the list and links all nodes properly?

hard

A. Node* first = new Node{1, nullptr, nullptr};
Node* second = new Node{2, nullptr, first};
first->prev = second;
Node* third = new Node{3, nullptr, second};
second->prev = third;

B. Node* first = new Node{1, nullptr, nullptr};
Node* second = new Node{2, first, nullptr};
first->next = second;
Node* third = new Node{3, second, nullptr};
second->next = third;

C. Node* first = new Node{1, nullptr, nullptr};
Node* second = new Node{2, nullptr, first};
first->next = second;
Node* third = new Node{3, nullptr, second};
second->next = third;

D. Node* first = new Node{1, nullptr, nullptr};
Node* second = new Node{2, first, nullptr};
first->prev = second;
Node* third = new Node{3, second, nullptr};
second->prev = third;

Solution

1. Step 1: Check node creation and pointer assignments

   Node* first = new Node{1, nullptr, nullptr}; Node* second = new Node{2, nullptr, first}; first->next = second; Node* third = new Node{3, nullptr, second}; second->next = third; creates nodes with correct data and sets next and prev pointers properly: second's prev points to first, first's next points to second, third's prev points to second, second's next points to third.

2. Step 2: Verify linkage correctness

   All nodes are linked forward and backward correctly, forming a proper doubly linked list.

3. Final Answer:

   Node* first = new Node{1, nullptr, nullptr}; Node* second = new Node{2, nullptr, first}; first->next = second; Node* third = new Node{3, nullptr, second}; second->next = third; -> Option C

4. Quick Check:

   Next and prev pointers set correctly in Node* first = new Node{1, nullptr, nullptr}; Node* second = new Node{2, nullptr, first}; first->next = second; Node* third = new Node{3, nullptr, second}; second->next = third; [OK]

Hint: Prev points backward, next points forward in order [OK]

Common Mistakes:

• Swapping next and prev pointers
• Not linking nodes both ways
• Setting prev or next to nullptr incorrectly