Create and Initialize Doubly Linked List in DSA C++

Mental Model

A doubly linked list is a chain of nodes where each node knows both its previous and next neighbor, making it easy to move forward and backward.

Analogy: Imagine a train where each carriage is connected to the one before and after it, so you can walk from the front to the back or back to front easily.

null ← [head] ↔ [node1] ↔ [node2] ↔ [node3] -> null

Dry Run Walkthrough

Input: Create a doubly linked list with values 10, 20, 30 in order

Goal: Build the doubly linked list so each node points to the next and previous nodes correctly

Step 1: Create first node with value 10, set head and tail to it

null ← [10] -> null
↑head, ↑tail

Why: We start the list with one node, so head and tail both point here

Step 2: Create second node with value 20, link it after tail

null ← [10] ↔ [20] -> null
↑head ↑tail

Why: Add new node after tail and update tail pointer

Step 3: Create third node with value 30, link it after tail

null ← [10] ↔ [20] ↔ [30] -> null
↑head ↑tail

Why: Add last node and update tail to point here

Result:

null ← [10] ↔ [20] ↔ [30] -> null
head points to 10, tail points to 30

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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 append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode; // first node becomes head and tail
            return;
        }
        tail->next = newNode; // link new node after tail
        newNode->prev = tail; // link new node back to tail
        tail = newNode;       // update tail to new node
    }

    void printForward() {
        Node* curr = head;
        while (curr) {
            cout << curr->data;
            if (curr->next) cout << " ↔ ";
            curr = curr->next;
        }
        cout << " -> null" << endl;
    }

    void printBackward() {
        Node* curr = tail;
        while (curr) {
            cout << curr->data;
            if (curr->prev) cout << " ↔ ";
            curr = curr->prev;
        }
        cout << " ← null" << endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(10);
    dll.append(20);
    dll.append(30);

    dll.printForward();
    dll.printBackward();

    return 0;
}

if (!head) { head = tail = newNode; return; }

handle empty list by setting head and tail to new node

tail->next = newNode;

link new node after current tail

newNode->prev = tail;

link new node back to current tail

tail = newNode;

update tail pointer to new node

Output

10 ↔ 20 ↔ 30 -> null

30 ↔ 20 ↔ 10 ← null

Complexity Analysis

Time: O(n) to create n nodes because we append each node once

Space: O(n) because each node stores data and two pointers

vs Alternative: Compared to singly linked list, doubly linked list uses extra space for prev pointer but allows backward traversal

Edge Cases

Empty list before any append

First append sets head and tail to new node

DSA C++

if (!head) { head = tail = newNode; return; }

Appending only one node

List has one node with prev and next as null

DSA C++

if (!head) { head = tail = newNode; return; }

When to Use This Pattern

When you need to move forward and backward through a list easily, use a doubly linked list to keep track of both neighbors.

Common Mistakes

Mistake: Not updating the prev pointer of the new node
Fix: Set newNode->prev = tail before updating tail

Mistake: Not updating tail pointer after appending
Fix: Assign tail = newNode after linking

Summary

Creates a doubly linked list where each node points to both previous and next nodes.

Use when you want to traverse a list forwards and backwards efficiently.

Remember to update both next and prev pointers and adjust head and tail correctly.

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