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

Concept Flow - Create and Initialize Doubly Linked List

Create new node with data

↓

Set new node's prev to null

↓

Set new node's next to null

↓

Set head pointer to new node

↓

If list empty, head points to new node

↓

Initialization complete

Start by making a new node with data. Set its previous and next links to null. Then point the list's head to this new node. The list is now ready with one element.

Execution Sample

DSA C#

class Node {
  public int data;
  public Node prev, next;
  public Node(int d) { data = d; prev = null; next = null; }
}

Node head = new Node(10);

This code creates a doubly linked list with one node containing the value 10.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	None	None	List is empty
2	Set new node.prev = null	Node(10)	newNode.prev -> null	Node(10) with prev=null
3	Set new node.next = null	Node(10)	newNode.next -> null	Node(10) with next=null
4	Set head = new node	Node(10)	head -> Node(10)	head points to Node(10)
5	Initialization complete	Node(10)	head -> Node(10)	head <-> Node(10) <-> null

💡 List initialized with one node; head points to it; prev and next are null

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
head	null	null	null	null	Node(10)	Node(10)
newNode.data	N/A	10	10	10	10	10
newNode.prev	N/A	undefined	null	null	null	null
newNode.next	N/A	undefined	undefined	null	null	null

Key Moments - 2 Insights

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

Because the first node has no neighbors, its prev and next must be null to show it is alone. See execution_table rows 2 and 3 where these pointers are set.

What does the head pointer represent after initialization?

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

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what does the head pointer point to?

A The previous node

B The new node with data 10

C Null

D The next node

💡 Hint

Check the 'Pointer Changes' column at step 4 in execution_table

At which step is the new node's next pointer set to null?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Operation' column in execution_table for setting next pointer

If we did not set newNode.prev to null, what would be the risk?

A The list might point to a random previous node

B The list would be empty

C The head pointer would be null

D The new node would have no data

💡 Hint

Refer to variable_tracker for newNode.prev values after step 2

Concept Snapshot

Create a new node with data.
Set its prev and next pointers to null.
Assign head pointer to this new node.
This initializes a doubly linked list with one element.
Prev and next null means no neighbors.

Full Transcript

To create and initialize a doubly linked list, first create a new node with the given data. Then set the new node's previous and next pointers to null because it has no neighbors yet. Finally, set the list's head pointer to this new node. This means the list now has one node, and the head points to it. The prev and next pointers being null show that this node is alone in the list.

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 at the beginning

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 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 class for a doubly linked list in C#?

easy

A. class Node { public int data; public Node next; }

B. public class Node { int data; int next; int prev; }

C. public class Node { public int data; public Node next; public Node prev; }

D. public class Node { public int data; public Node next; private Node previous; }

Solution

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

   Node must have data, next pointer, and previous pointer of type Node.

2. Step 2: Verify correct syntax and access modifiers

   public class Node { public int data; public Node next; public Node prev; } declares public int data, and public Node next and prev correctly.

3. Final Answer:

   public class Node { public int data; public Node next; public Node prev; } -> Option C

4. Quick Check:

   Node class with data, next, prev = public class Node { public int data; public Node next; public Node prev; } [OK]

Hint: Node needs next and prev as Node types [OK]

Common Mistakes:

• Using int for next and prev instead of Node
• Missing prev pointer for doubly linked list
• Incorrect access modifiers

3. What will be the output of the following C# code that creates a doubly linked list with nodes 10, 20, 30 and prints forward traversal?

public class Node {
    public int data;
    public Node next;
    public Node prev;
    public Node(int d) { data = d; next = null; prev = null; }
}

public class DoublyLinkedList {
    public Node head;
    public void AddLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) temp = temp.next;
        temp.next = newNode;
        newNode.prev = temp;
    }
    public void PrintForward() {
        Node temp = head;
        while (temp != null) {
            Console.Write(temp.data + " -> ");
            temp = temp.next;
        }
        Console.WriteLine("null");
    }
}

class Program {
    static void Main() {
        DoublyLinkedList list = new DoublyLinkedList();
        list.AddLast(10);
        list.AddLast(20);
        list.AddLast(30);
        list.PrintForward();
    }
}

medium

A. 30 -> 20 -> 10 -> null

B. null

C. 10 -> 20 -> null

D. 10 -> 20 -> 30 -> null

Solution

1. Step 1: Understand AddLast method behavior

   AddLast adds nodes at the end, so nodes are 10, then 20, then 30 in order.

2. Step 2: Trace PrintForward output

   PrintForward prints from head to last node: 10 -> 20 -> 30 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option D

4. Quick Check:

   Forward print = 10 -> 20 -> 30 -> null [OK]

Hint: AddLast appends; PrintForward prints from head [OK]

Common Mistakes:

• Confusing forward and backward traversal
• Missing last node in output
• Printing in reverse order

4. Identify the error in the following code snippet that tries to add a node at the end of a doubly linked list:

public void AddLast(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node temp = head;
    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = newNode;
    // Missing line here
}

medium

A. Missing setting newNode.prev = temp

B. Missing setting head = newNode

C. Missing while loop to find last node

D. Missing creating newNode instance

Solution

1. Step 1: Review AddLast logic

   After finding last node, newNode is linked as next of temp.

2. Step 2: Check doubly linked list pointer updates

   For doubly linked list, newNode.prev must point back to temp to maintain backward link.

3. Final Answer:

   Missing setting newNode.prev = temp -> Option A

4. Quick Check:

   Set newNode.prev to temp for backward link [OK]

Hint: Always set newNode.prev when adding at end [OK]

Common Mistakes:

• Forgetting to set newNode.prev
• Reassigning head incorrectly
• Skipping loop to find last node

5. You want to create a doubly linked list from an array of integers {1, 2, 3, 4} such that the list is 1 -> 2 -> 3 -> 4 (head points to 1), and then reverse print the list (4 -> 3 -> 2 -> 1 -> null) using backward traversal. Which approach correctly initializes the list and prints it backward?

int[] arr = {1, 2, 3, 4};
DoublyLinkedList list = new DoublyLinkedList();
// Step 1: Add all elements from arr to list
// Step 2: Print list backward

// Which code snippet correctly does this?

hard

A. for (int i = arr.Length - 1; i >= 0; i--) list.AddLast(arr[i]);
Node temp = list.head;
while (temp != null) { Console.Write(temp.data + " -> "); temp = temp.next; }
Console.WriteLine("null");

B. foreach (int val in arr) list.AddLast(val);
Node temp = list.head;
while (temp.next != null) temp = temp.next;
while (temp != null) { Console.Write(temp.data + " -> "); temp = temp.prev; }
Console.WriteLine("null");

C. foreach (int val in arr) list.AddFirst(val);
Node temp = list.head;
while (temp != null) { Console.Write(temp.data + " -> "); temp = temp.next; }
Console.WriteLine("null");

D. for (int i = 0; i < arr.Length; i++) list.AddLast(arr[i]);
Node temp = list.head;
while (temp != null) { Console.Write(temp.data + " -> "); temp = temp.next; }
Console.WriteLine("null");

Solution

1. Step 1: Add elements in order using AddLast

   Use foreach (int val in arr) list.AddLast(val); to build the list as 1 -> 2 -> 3 -> 4, preserving array order.

2. Step 2: Traverse to last node and print backward

   Node temp = list.head; while (temp.next != null) temp = temp.next; then while (temp != null) { Console.Write(temp.data + " -> "); temp = temp.prev; } Console.WriteLine("null"); to print 4 -> 3 -> 2 -> 1 -> null.

3. Final Answer:

   foreach (int val in arr) list.AddLast(val); Node temp = list.head; while (temp.next != null) temp = temp.next; while (temp != null) { Console.Write(temp.data + " -> "); temp = temp.prev; } Console.WriteLine("null"); -> Option B

4. Quick Check:

   Build forward list + backward traversal from tail [OK]

Hint: Add in order, then move to tail to print backward [OK]

Common Mistakes:

• Adding elements in reverse order
• Printing forward instead of backward
• Using AddFirst which reverses order