Doubly Linked List Structure and Node Design in DSA C++

Mental Model

A doubly linked list is a chain of nodes where each node knows both its neighbor before and after it.

Analogy: Imagine a train where each carriage has a connector to the carriage in front and the one behind, so you can move forward or backward easily.

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

Dry Run Walkthrough

Input: Create a doubly linked list with nodes 1, 2, 3 linked in order

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

Step 1: Create node 1 with prev=null and next=null

null ← [1] -> null

Why: Start with the first node which has no neighbors yet

Step 2: Create node 2 and link it after node 1

null ← [1] ↔ [2] -> null

Why: Link node 2 after node 1, update pointers both ways

Step 3: Create node 3 and link it after node 2

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

Why: Link node 3 after node 2, completing the chain

Result:

null ← 1 ↔ 2 ↔ 3 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Node {
public:
    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 current tail to new node
        newNode->prev = tail; // link new node back to current tail
        tail = newNode; // update tail to new node
    }

    void printList() {
        Node* curr = head;
        while (curr) {
            cout << curr->data;
            if (curr->next) cout << " ↔ ";
            curr = curr->next;
        }
        cout << "\n";
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(1);
    dll.append(2);
    dll.append(3);
    dll.printList();
    return 0;
}

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

set first node as head and tail when list is empty

tail->next = newNode;

link current tail's next to new node

newNode->prev = tail;

link new node's prev back to current tail

tail = newNode;

update tail pointer to new node

Output

1 ↔ 2 ↔ 3

Complexity Analysis

Time: O(1) for append because we keep track of tail and link new node directly

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

vs Alternative: Compared to singly linked list, doubly linked list uses more space but allows backward traversal and easier node removal

Edge Cases

Empty list when appending first node

Head and tail both point to the new node

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 structure because each node links both ways.

Common Mistakes

Mistake: Not updating the new node's prev pointer when appending
Fix: Always set newNode->prev = tail before updating tail

Mistake: Forgetting to update tail pointer after adding new node
Fix: Set tail = newNode to keep tail at the last node

Summary

A doubly linked list stores nodes where each node points to both previous and next nodes.

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

The key is each node has two pointers, allowing two-way navigation.

Practice

1. What is the main advantage of a doubly linked list over a singly linked list?

easy

A. It can only be traversed forward.

B. It uses less memory than a singly linked list.

C. It requires only one pointer per node.

D. It allows traversal in both forward and backward directions.

Solution

1. Step 1: Understand node pointers in doubly linked list

   Each node has two pointers: one to the next node and one to the previous node.

2. Step 2: Compare traversal capabilities

   This allows moving forward and backward through the list, unlike singly linked lists which only allow forward traversal.

3. Final Answer:

   It allows traversal in both forward and backward directions. -> Option D

4. Quick Check:

   Doubly linked list = two-way traversal [OK]

Hint: Remember: two pointers mean two directions [OK]

Common Mistakes:

• Thinking it uses less memory than singly linked list
• Assuming it has only one pointer per node
• Believing it can only traverse forward

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* next; Node* prev; };

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

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

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

Solution

1. Step 1: Check pointer usage for next and prev

   In a doubly linked list, next and prev must be pointers to Node, so Node* next and Node* prev are correct.

2. Step 2: Identify incorrect declarations

   struct Node { int data; Node next; Node prev; }; uses Node next and Node prev (not pointers), C uses int prev, and D uses int for both next and prev, which is incorrect.

3. Final Answer:

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

4. Quick Check:

   Pointers for next and prev = struct Node { int data; Node* next; Node* prev; }; [OK]

Hint: Pointers to Node must use * symbol [OK]

Common Mistakes:

• Using Node instead of Node* for next and prev
• Using int type for pointers
• Missing pointer symbols

3. Consider the following code snippet for a doubly linked list node insertion at the front:

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

Node* head = nullptr;

Node* newNode = new Node{10, nullptr, nullptr};
newNode->next = head;
if (head != nullptr) {
  head->prev = newNode;
}
head = newNode;

// What is the data in head->next after insertion?

medium

A. nullptr

B. 10

C. Undefined

D. Garbage value

Solution

1. Step 1: Analyze initial head value

   Initially, head is nullptr, meaning the list is empty.

2. Step 2: After insertion, newNode->next points to old head (nullptr)

   Since head was nullptr, newNode->next is set to nullptr, so head->next is nullptr after insertion.

3. Final Answer:

   nullptr -> Option A

4. Quick Check:

   Empty list insertion sets next to nullptr [OK]

Hint: New node next points to old head, which is nullptr here [OK]

Common Mistakes:

• Assuming head->next has data 10
• Thinking head->next is undefined or garbage
• Ignoring initial nullptr head

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

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

void insertEnd(Node*& head, int val) {
  Node* newNode = new Node{val, nullptr, nullptr};
  if (head == nullptr) {
    head = newNode;
    return;
  }
  Node* temp = head;
  while (temp->next != nullptr) {
    temp = temp->next;
  }
  temp->next = newNode;
  newNode->prev = nullptr;
}

medium

A. temp should be initialized to nullptr.

B. head should be passed by value, not reference.

C. newNode->prev should point to temp, not nullptr.

D. newNode->next should point to head.

Solution

1. Step 1: Check newNode's prev pointer assignment

   After finding the last node (temp), newNode is added after temp, so newNode->prev must point to temp.

2. Step 2: Identify incorrect assignment

   Code sets newNode->prev = nullptr, which breaks backward link; it should be newNode->prev = temp.

3. Final Answer:

   newNode->prev should point to temp, not nullptr. -> Option C

4. Quick Check:

   Prev pointer links new node to last node [OK]

Hint: Prev of new node = last node before insertion [OK]

Common Mistakes:

• Setting newNode->prev to nullptr instead of last node
• Passing head by value losing list updates
• Incorrect initialization of temp pointer

5. You want to design a function to delete a node from a doubly linked list given a pointer to that node (not the head). Which pointer updates are necessary to maintain list integrity?

hard

A. No pointer updates needed; just delete the node.

B. Set node's prev->next to node's next and node's next->prev to node's prev.

C. Set node's prev to nullptr and node's next to nullptr only.

D. Set node's next->next to node's prev and node's prev->prev to node's next.

Solution

1. Step 1: Understand node removal in doubly linked list

   To remove a node, the previous node's next pointer must skip the node and point to node's next.

2. Step 2: Update next node's prev pointer

   Similarly, the next node's prev pointer must skip the node and point to node's prev.

3. Final Answer:

   Set node's prev->next to node's next and node's next->prev to node's prev. -> Option B

4. Quick Check:

   Prev and next pointers bypass deleted node [OK]

Hint: Link prev and next nodes directly to remove node [OK]

Common Mistakes:

• Not updating both prev and next pointers
• Setting wrong pointers to nullptr
• Deleting node without fixing links