Insert at End of Doubly Linked List in DSA C#

Mental Model

Add a new item at the very end of a list where each item knows both its previous and next neighbor.

Analogy: Imagine a train where each carriage is linked to the one before and after it. Adding a new carriage means connecting it to the last carriage and updating the last carriage to point to the new one.

null ← 1 ↔ 2 ↔ 3 -> null

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at end

Goal: Add a new node with value 4 at the end of the doubly linked list

Step 1: Create new node with value 4

null ← 1 ↔ 2 ↔ 3 -> null   newNode(4)

Why: We need a new node to add to the list

Step 2: Start at head (node 1) to find last node

null ← 1 ↑ ↔ 2 ↔ 3 -> null   newNode(4)

Why: We must find the last node to attach the new node

Step 3: Move to node 2

null ← 1 ↔ 2 ↑ ↔ 3 -> null   newNode(4)

Why: Keep moving forward to reach the last node

Step 4: Move to node 3 (last node)

null ← 1 ↔ 2 ↔ 3 ↑ -> null   newNode(4)

Why: We found the last node where new node will be attached

Step 5: Set last node's next to new node and new node's prev to last node

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null

Why: Link new node at the end maintaining both directions

Result:

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null

Annotated Code

DSA C#

using System;

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

    public DoublyLinkedListNode(int data)
    {
        Data = data;
        Prev = null;
        Next = null;
    }
}

public class DoublyLinkedList
{
    public DoublyLinkedListNode Head;

    public DoublyLinkedList()
    {
        Head = null;
    }

    public void InsertAtEnd(int data)
    {
        DoublyLinkedListNode newNode = new DoublyLinkedListNode(data); // create new node

        if (Head == null) // if list empty
        {
            Head = newNode; // new node is head
            return;
        }

        DoublyLinkedListNode curr = Head; // start at head
        while (curr.Next != null) // move to last node
        {
            curr = curr.Next; // advance curr to next node
        }

        curr.Next = newNode; // link last node's next to new node
        newNode.Prev = curr; // link new node's prev to last node
    }

    public void PrintList()
    {
        DoublyLinkedListNode curr = Head;
        while (curr != null)
        {
            Console.Write(curr.Data);
            if (curr.Next != null)
                Console.Write(" ↔ ");
            curr = curr.Next;
        }
        Console.WriteLine();
    }
}

class Program
{
    static void Main()
    {
        DoublyLinkedList list = new DoublyLinkedList();
        list.InsertAtEnd(1);
        list.InsertAtEnd(2);
        list.InsertAtEnd(3);
        list.InsertAtEnd(4); // insert value 4 at end
        list.PrintList();
    }
}

DoublyLinkedListNode newNode = new DoublyLinkedListNode(data); // create new node

create new node to add at end

if (Head == null) // if list empty

handle empty list by making new node the head

DoublyLinkedListNode curr = Head; // start at head

start traversal from head to find last node

while (curr.Next != null) // move to last node

advance curr until last node (where next is null)

curr.Next = newNode; // link last node's next to new node

attach new node after last node

newNode.Prev = curr; // link new node's prev to last node

set new node's prev pointer back to last node

Output

1 ↔ 2 ↔ 3 ↔ 4

Complexity Analysis

Time: O(n) because we traverse the list from head to last node once

Space: O(1) because we only create one new node and use constant extra space

vs Alternative: Compared to inserting at head which is O(1), inserting at end requires traversal making it O(n)

Edge Cases

empty list

new node becomes the head of the list

DSA C#

if (Head == null) // if list empty

single element list

new node is linked after the single node correctly

DSA C#

while (curr.Next != null) // move to last node

When to Use This Pattern

When you need to add an item at the end of a list that links both forward and backward, use this pattern to maintain both directions.

Common Mistakes

Mistake: Forgetting to set the new node's Prev pointer to the last node
Fix: Always set newNode.Prev = curr after linking curr.Next = newNode

Mistake: Not handling empty list case, causing null reference errors
Fix: Check if Head is null and assign new node as Head before traversal

Summary

Adds a new node at the end of a doubly linked list maintaining both next and prev links.

Use when you want to append data to the tail of a doubly linked list.

The key is to find the last node and link the new node both ways to keep the list connected.

Practice

1. What is the main purpose of inserting a node at the end of a doubly linked list?

easy

A. To remove the first node

B. To find the middle node

C. To reverse the list

D. To add a new element after the last node

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes connected forward and backward, allowing traversal in both directions.

2. Step 2: Purpose of insertion at the end

   Inserting at the end means adding a new node after the current last node, updating pointers accordingly.

3. Final Answer:

   To add a new element after the last node -> Option D

4. Quick Check:

   Insert at end = add after last node [OK]

Hint: Insert at end means add after last node [OK]

Common Mistakes:

• Confusing insertion at end with deletion
• Thinking insertion reverses the list
• Assuming insertion happens at the start

2. Which of the following is the correct syntax to create a new node in C# for a doubly linked list?

easy

A. Node newNode = new Node(data);

B. Node newNode = Node(data);

C. newNode = Node.new(data);

D. Node newNode = new Node[];

Solution

1. Step 1: Understand object creation in C#

   In C#, objects are created using the 'new' keyword followed by the constructor call.

2. Step 2: Apply to Node creation

   Creating a new node requires calling the Node constructor with data inside parentheses after 'new'.

3. Final Answer:

   Node newNode = new Node(data); -> Option A

4. Quick Check:

   Use 'new' keyword with constructor call [OK]

Hint: Use 'new' keyword with constructor parentheses [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using array syntax incorrectly
• Calling constructor without 'new'

3. Given the following code snippet, what will be the printed output after inserting 30 at the end of the doubly linked list?

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

class DoublyLinkedList {
  public Node head;
  public void InsertAtEnd(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 PrintList() {
    Node temp = head;
    while (temp != null) {
      Console.Write(temp.data + " -> ");
      temp = temp.next;
    }
    Console.WriteLine("null");
  }
}

DoublyLinkedList dll = new DoublyLinkedList();
dll.InsertAtEnd(10);
dll.InsertAtEnd(20);
dll.InsertAtEnd(30);
dll.PrintList();

medium

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

B. 30 -> 20 -> 10 -> null

C. 10 -> 20 -> null

D. null

Solution

1. Step 1: Trace InsertAtEnd calls

   First insert 10: list is 10 -> null. Then insert 20: list is 10 -> 20 -> null. Then insert 30: list is 10 -> 20 -> 30 -> null.

2. Step 2: PrintList outputs nodes in order

   PrintList prints each node's data followed by '->', ending with 'null'. So output is '10 -> 20 -> 30 -> null'.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Insertion at end appends nodes in order [OK]

Hint: Insert at end appends nodes; print shows order [OK]

Common Mistakes:

• Confusing insertion order
• Printing in reverse order
• Missing 'null' at end

4. Identify the error in the following InsertAtEnd method for a doubly linked list:

public void InsertAtEnd(int data) {
  Node newNode = new Node(data);
  if (head == null) {
    head = newNode;
  }
  Node temp = head;
  while (temp.next != null) {
    temp = temp.next;
  }
  temp.next = newNode;
  newNode.prev = temp;
}

medium

A. Loop condition should be temp != null

B. Missing return after setting head when list is empty

C. Incorrect assignment of newNode.prev

D. Node constructor is called incorrectly

Solution

1. Step 1: Analyze empty list case

   If head is null, head is set to newNode but code continues to loop and assign pointers again, causing newNode to link to itself.

2. Step 2: Fix by adding return after setting head

   Adding 'return;' after 'head = newNode;' stops further code execution, preventing incorrect pointer assignments.

3. Final Answer:

   Missing return after setting head when list is empty -> Option B

4. Quick Check:

   Return after empty list insert prevents errors [OK]

Hint: Add return after empty list insertion [OK]

Common Mistakes:

• Not returning after setting head
• Wrong loop condition
• Misassigning prev pointer

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25. You want to insert 35 at the end. After insertion, which of the following correctly describes the pointers of the new node and the previous last node?

hard

A. newNode.prev points to null; node with 25.next points to newNode

B. newNode.next points to node with 25; node with 25.prev points to newNode

C. newNode.prev points to node with 25; node with 25.next points to newNode

D. newNode.prev and newNode.next both point to null; node with 25.next points to null

Solution

1. Step 1: Understand pointer updates when inserting at end

   The new node's prev pointer should point to the current last node (25), and the current last node's next pointer should point to the new node.

2. Step 2: Confirm new node's next pointer

   The new node's next pointer should be null because it is now the last node.

3. Final Answer:

   newNode.prev points to node with 25; node with 25.next points to newNode -> Option C

4. Quick Check:

   Prev points backward; next points forward [OK]

Hint: New node prev = old last; old last next = new node [OK]

Common Mistakes:

• Swapping prev and next pointers
• Setting newNode.prev to null
• Not updating old last node's next pointer