Create and Initialize Doubly Linked List in DSA C++ - Execution Trace

Concept Flow - Create and Initialize Doubly Linked List

Create new node

↓

Set node data

↓

Set node prev = nullptr

↓

Set node next = nullptr

↓

Set head pointer = new node

↓

Done: List with one node

Start by creating a new node, set its data and pointers to null, then assign it as the head of the list.

Execution Sample

DSA C++

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

Node* node = new Node();
node->data = 10;
node->prev = nullptr;
node->next = nullptr;
Node* head = node;

This code creates a doubly linked list with one node containing data 10 and null pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node	None	None	null
2	Set node data = 10	Node(10)	None	10 <-> null
3	Set node prev = nullptr	Node(10)	node.prev = nullptr	null <- 10
4	Set node next = nullptr	Node(10)	node.next = nullptr	10 -> null
5	Set head = node	Node(10)	head -> node	head -> 10 <-> null
6	Done	Node(10)	head points to node	head -> 10 <-> null

💡 List initialized with one node; head points to node with data 10 and null prev/next pointers.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
head	nullptr	nullptr	nullptr	nullptr	nullptr	node	node
node->data	undefined	undefined	10	10	10	10	10
node->prev	undefined	undefined	undefined	nullptr	nullptr	nullptr	nullptr
node->next	undefined	undefined	undefined	undefined	nullptr	nullptr	nullptr

Key Moments - 3 Insights

Why do we set both prev and next pointers to nullptr when creating the first node?

Because the first node has no neighbors, so both pointers must be null to show it is alone. See steps 3 and 4 in execution_table.

What does the head pointer represent after initialization?

The head points to the first node in the list. After step 5, head points to the new node, making it the start of the list.

Why is the visual state shown as 'head -> 10 <-> null'?

It shows the head points to the node with data 10, which has no previous node (null) and no next node (null), so arrows show connections accordingly.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of node->prev?

A head

B undefined

C nullptr

D 10

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table.

At which step does the head pointer start pointing to the new node?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Pointer Changes' column for when head is assigned in execution_table.

If we skip setting node->next to nullptr, what would the visual state show after step 4?

A head -> 10 <-> garbage

B head -> null

C head -> 10 <-> null

D null

💡 Hint

Without setting node->next to nullptr, the pointer may hold garbage value, affecting visual state.

Concept Snapshot

Create a node struct with data, prev, next pointers.
Allocate new node with new.
Set data value.
Set prev and next to nullptr.
Assign head pointer to new node.
List now has one node with no neighbors.

Full Transcript

To create and initialize a doubly linked list, first create a new node. Set its data to the desired value. Then set both prev and next pointers to nullptr because the node has no neighbors yet. Finally, assign the head pointer to this new node. This makes the list start with one node. The visual state shows the head pointing to the node with data 10, which has no previous or next nodes. This process ensures the list is correctly initialized and ready for further operations.

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