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.

Analogy: Imagine a train where each carriage is connected to the one before and after it, 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 values 1, 2, 3 in order

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

Step 1: Create first node with value 1; head and tail point to it

null ← [head/tail] 1 -> null

Why: Start the list with the first node; it has no neighbors yet

Step 2: Create second node with value 2; link it after first node

null ← 1 ↔ [tail] 2 -> null

Why: Add second node and update pointers so 1 points to 2 and 2 points back to 1

Step 3: Create third node with value 3; link it after second node

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

Why: Add third node and update pointers so 2 points to 3 and 3 points back to 2

Result:

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

Annotated Code

DSA C#

using System;

public class DoublyLinkedListNode
{
    public int Value;
    public DoublyLinkedListNode Prev;
    public DoublyLinkedListNode Next;

    public DoublyLinkedListNode(int value)
    {
        Value = value;
        Prev = null;
        Next = null;
    }
}

public class DoublyLinkedList
{
    public DoublyLinkedListNode Head;
    public DoublyLinkedListNode Tail;

    public DoublyLinkedList()
    {
        Head = null;
        Tail = null;
    }

    public void Append(int value)
    {
        var newNode = new DoublyLinkedListNode(value);
        if (Head == null)
        {
            Head = newNode; // first node becomes head
            Tail = newNode; // first node also tail
        }
        else
        {
            Tail.Next = newNode; // link current tail to new node
            newNode.Prev = Tail; // link new node back to tail
            Tail = newNode; // update tail to new node
        }
    }

    public void PrintList()
    {
        var current = Head;
        while (current != null)
        {
            Console.Write(current.Value);
            if (current.Next != null)
                Console.Write(" ↔ ");
            current = current.Next;
        }
        Console.WriteLine();
    }
}

public class Program
{
    public static void Main()
    {
        var list = new DoublyLinkedList();
        list.Append(1);
        list.Append(2);
        list.Append(3);
        list.PrintList();
    }
}

if (Head == null)

check if list is empty to set first node as head and tail

Head = newNode; // first node becomes head Tail = newNode; // first node also tail

initialize head and tail to the new node when list is empty

Tail.Next = newNode; // link current tail to new node newNode.Prev = Tail; // link new node back to tail Tail = newNode; // update tail to new node

append new node at the end and update pointers accordingly

while (current != null)

traverse from head to tail to print all node values

Output

1 ↔ 2 ↔ 3

Complexity Analysis

Time: O(n) because appending n nodes requires visiting each once

Space: O(n) because we store n nodes in memory

vs Alternative: Compared to arrays, doubly linked lists allow easy insertion without shifting elements but use extra space for pointers

Edge Cases

Empty list when appending first node

Head and Tail are set to the new node correctly

DSA C#

if (Head == null)

When to Use This Pattern

When you need to add or remove items from both ends and move forward or backward easily, use a doubly linked list.

Common Mistakes

Mistake: Not updating the Prev pointer of the new node when appending
Fix: Set newNode.Prev = Tail before updating Tail to newNode

Mistake: Not updating Tail to the new node after appending
Fix: Assign Tail = newNode after linking nodes

Summary

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

Use when you want to traverse or modify a list in both directions efficiently.

Remember to update both next and previous pointers when adding nodes.

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