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

Concept Flow - Create and Initialize Doubly Linked List

Define Node Structure

↓

Create Head Node with data

↓

Set head.prev = NULL

↓

Set head.next = NULL

↓

Initialize list with single node

↓

Done: List ready with one node

Start by defining the node structure, then create the first node (head) with data, set its previous and next pointers to NULL, and finish with a list containing one node.

Execution Sample

DSA C

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

struct Node* head = malloc(sizeof(struct Node));
head->data = 10;
head->prev = NULL;
head->next = NULL;

This code creates a doubly linked list with one node containing data 10, and both pointers set to NULL.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Define struct Node	None	None	List is empty
2	Allocate memory for head node	Node(?, prev=garbage, next=garbage)	head points to new node	head -> [ ? | garbage | garbage ]
3	Assign data = 10 to head	Node(10, prev=garbage, next=garbage)	head->data = 10	head -> [ 10 | garbage | garbage ]
4	Set head->prev = NULL	Node(10, prev=NULL, next=garbage)	head->prev = NULL	head -> [ 10 | NULL | garbage ]
5	Set head->next = NULL	Node(10, prev=NULL, next=NULL)	head->next = NULL	head -> [ 10 | NULL | NULL ]
6	Initialization complete	Node(10, prev=NULL, next=NULL)	No change	head -> [ 10 | NULL | NULL ]

💡 List initialized with one node; both prev and next pointers are NULL.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
head	NULL	Points to allocated node	Points to node with data=10	Points to node with data=10, prev=NULL	Points to node with data=10, prev=NULL, next=NULL	Points to node with data=10, prev=NULL, next=NULL
head->data	Undefined	Undefined	10	10	10	10
head->prev	Undefined	garbage	garbage	NULL	NULL	NULL
head->next	Undefined	garbage	garbage	garbage	NULL	NULL

Key Moments - 3 Insights

Why do we set both head->prev and head->next to NULL?

Because this is the first and only node, it has no previous or next nodes. Setting these pointers to NULL clearly marks the ends of the list, as shown in execution_table steps 4 and 5.

What happens if we forget to allocate memory for the head node?

Without allocating memory (step 2), head would point to NULL or garbage, causing errors when accessing or assigning data. The list would not be properly created.

Why is the data assigned after allocating memory but before setting pointers?

We must first have a valid node (step 2) to store data. Assigning data before allocation would cause errors. Setting pointers after data assignment (steps 4 and 5) ensures the node is fully initialized.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of head->data?

A NULL

B Undefined

C 10

D 0

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3 in execution_table.

At which step does head->prev get set to NULL?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Operation' column in execution_table to find when head->prev is assigned.

If we skip setting head->next to NULL, what would the Visual State show after step 5?

A head -> [ 10 | NULL | garbage ]

B head -> [ 10 | garbage | NULL ]

C head -> [ 10 | NULL | NULL ]

D head -> [ 10 | garbage | garbage ]

💡 Hint

Consider what happens if head->next is not initialized; check pointer defaults in variable_tracker.

Concept Snapshot

Create a struct Node with data, prev, next pointers.
Allocate memory for head node.
Assign data to head->data.
Set head->prev = NULL and head->next = NULL.
This creates a doubly linked list with one node.
Pointers NULL mark list ends.

Full Transcript

To create and initialize a doubly linked list, first define the node structure with data and two pointers: prev and next. Then allocate memory for the head node. Assign the desired data value to head->data. Set both head->prev and head->next to NULL because this is the only node, so it has no neighbors. This process results in a doubly linked list with a single node, where both ends are clearly marked by NULL pointers.

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 data automatically

D. To store data only in one direction

Solution

1. Step 1: Understand doubly linked list structure

   A doubly linked list has nodes with pointers to both next and previous 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 = bidirectional traversal [OK]

Hint: Remember: doubly means two directions [OK]

Common Mistakes:

• Confusing doubly linked list with singly linked list
• Thinking it sorts data automatically
• Assuming it uses arrays internally

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

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

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

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

Solution

1. Step 1: Check node structure for doubly linked list

   Each node must have data, a pointer to next node, and a pointer to previous node.

2. Step 2: Identify correct syntax

   struct Node { int data; struct Node* prev; struct Node* next; }; correctly declares pointers to next and prev nodes using struct Node*.

3. Final Answer:

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

4. Quick Check:

   Node has data + prev pointer + next pointer [OK]

Hint: Pointers to prev and next must be struct Node* [OK]

Common Mistakes:

• Using int instead of pointer for next/prev
• Missing prev pointer in node
• Declaring next/prev as struct Node instead of pointer

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

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

int main() {
  Node* head = (Node*)malloc(sizeof(Node));
  Node* second = (Node*)malloc(sizeof(Node));

  head->data = 10;
  head->prev = NULL;
  head->next = second;

  second->data = 20;
  second->prev = head;
  second->next = NULL;

  printf("%d -> %d -> NULL", head->data, second->data);
  return 0;
}

medium

A. Compilation error

B. 20 -> 10 -> NULL

C. 10 -> 20 -> NULL

D. 10 -> NULL

Solution

1. Step 1: Analyze node creation and linking

   Two nodes are created: head with data 10, second with data 20. head->next points to second, second->prev points to head.

2. Step 2: Understand print statement

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

3. Final Answer:

   10 -> 20 -> NULL -> Option C

4. Quick Check:

   Prints data in order: 10 then 20 [OK]

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

Common Mistakes:

• Confusing order of nodes
• Forgetting to set next or prev pointers
• Assuming print shows backward traversal

4. Identify the error in the following code snippet that attempts to initialize a doubly linked list node:

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

int main() {
  struct Node* node = malloc(sizeof(struct Node));
  node->data = 5;
  node->prev = NULL;
  node->next = NULL;
  free(node);
  printf("%d", node->data);
  return 0;
}

medium

A. Accessing freed memory after free(node)

B. Missing #include

C. Incorrect struct declaration

D. No error, code runs fine

Solution

1. Step 1: Review memory allocation and freeing

   Memory is allocated for node, initialized, then freed with free(node).

2. Step 2: Identify invalid access

   After freeing, code tries to print node->data, which accesses freed memory causing undefined behavior.

3. Final Answer:

   Accessing freed memory after free(node) -> Option A

4. Quick Check:

   Using pointer after free = error [OK]

Hint: Never use pointer after free() [OK]

Common Mistakes:

• Ignoring use-after-free errors
• Forgetting to include stdlib.h (but not main error here)
• Assuming free deletes pointer variable

5. You want to create a doubly linked list with nodes containing values 1, 2, and 3 in that order. Which code snippet correctly initializes this list with proper prev and next pointers?

hard

A. Node* n1 = malloc(sizeof(Node)); n1->data=1; n1->prev=NULL; n1->next=NULL;
Node* n2 = malloc(sizeof(Node)); n2->data=2; n2->prev=NULL; n2->next=NULL;
n1->next=n2;
Node* n3 = malloc(sizeof(Node)); n3->data=3; n3->prev=NULL; n3->next=NULL;
n2->next=n3;

B. Node* n1 = malloc(sizeof(Node)); n1->data=1; n1->prev=NULL; n1->next=NULL;
Node* n2 = malloc(sizeof(Node)); n2->data=2; n2->prev=n1; n2->next=NULL;
n1->next=n2;
Node* n3 = malloc(sizeof(Node)); n3->data=3; n3->prev=n2; n3->next=n1;
n2->next=n3;

C. Node* n1 = malloc(sizeof(Node)); n1->data=1; n1->prev=NULL; n1->next=NULL;
Node* n2 = malloc(sizeof(Node)); n2->data=2; n2->prev=n1; n2->next=NULL;
n1->next=n2;
Node* n3 = malloc(sizeof(Node)); n3->data=3; n3->prev=NULL; n3->next=NULL;
n2->next=n3;

D. Node* n1 = malloc(sizeof(Node)); n1->data=1; n1->prev=NULL; n1->next=NULL;
Node* n2 = malloc(sizeof(Node)); n2->data=2; n2->prev=n1; n2->next=NULL;
n1->next=n2;
Node* n3 = malloc(sizeof(Node)); n3->data=3; n3->prev=n2; n3->next=NULL;
n2->next=n3;

Solution

1. Step 1: Check initialization of first node

   n1 has data=1, prev=NULL, next=NULL initially.

2. Step 2: Link second node correctly

   n2 has data=2, prev=n1, next=NULL; n1->next points to n2.

3. Step 3: Link third node correctly

   n3 has data=3, prev=n2, next=NULL; n2->next points to n3.

4. Final Answer:

   Code snippet B correctly sets prev and next pointers for all nodes -> Option D

5. Quick Check:

   Each node's prev and next link neighbors properly [OK]

Hint: Prev of first is NULL; next of last is NULL [OK]

Common Mistakes:

• Not setting prev pointers for nodes after first
• Setting next pointers incorrectly
• Making circular links unintentionally