Delete from End of Doubly Linked List in DSA C# - Time & Space Complexity

Time Complexity: Delete from End of Doubly Linked List

O(1)

Understanding Time Complexity

We want to understand how long it takes to remove the last item from a doubly linked list.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void DeleteFromEnd()
{
    if (tail == null) return; // empty list
    if (tail.Prev == null) // only one node
    {
        head = null;
        tail = null;
        return;
    }
    tail = tail.Prev;
    tail.Next = null;
}

This code removes the last node from a doubly linked list by updating pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Updating the tail pointer and its previous node's next pointer.
• How many times: This happens once per call, no loops or recursion involved.

How Execution Grows With Input

Removing the last node always takes the same steps, no matter how big the list is.

Input Size (n)	Approx. Operations
10	4 steps
100	4 steps
1000	4 steps

Pattern observation: The number of steps stays the same as the list grows.

Final Time Complexity

Time Complexity: O(1)

This means deleting from the end takes a constant amount of time regardless of list size.

Common Mistake

[X] Wrong: "Deleting from the end takes longer as the list grows because we must traverse the list."

[OK] Correct: Because the list keeps a direct pointer to the last node (tail), no traversal is needed.

Interview Connect

Knowing that deleting from the end of a doubly linked list is quick shows you understand how pointers help speed up operations.

Self-Check

"What if we did not keep a tail pointer? How would the time complexity change?"

Practice

1. What happens when you delete the last node from a doubly linked list that has multiple nodes?

easy

A. The first node is deleted instead.

B. The head pointer is set to null.

C. The list becomes empty immediately.

D. The second last node becomes the new tail and its next pointer is set to null.

Solution

1. Step 1: Identify the last node and its previous node

   In a doubly linked list, the last node's previous node is the second last node.

2. Step 2: Update the second last node's next pointer

   Set the second last node's next pointer to null to remove the last node from the list.

3. Final Answer:

   The second last node becomes the new tail and its next pointer is set to null. -> Option D

4. Quick Check:

   Deleting last node updates tail's next to null [OK]

Hint: Last node's previous next pointer must be null after deletion [OK]

Common Mistakes:

• Setting head to null instead of updating tail
• Not updating the previous node's next pointer
• Deleting the first node by mistake

2. Which of the following is the correct C# syntax to delete the last node from a doubly linked list named dll?

easy

A. dll.Head = dll.Head.Next; dll.Head.Previous = null;

B. dll.Tail = dll.Tail.Previous; dll.Tail.Next = null;

C. dll.Tail = null; dll.Head = null;

D. dll.Head.Previous = dll.Tail; dll.Tail.Next = dll.Head;

Solution

1. Step 1: Move tail pointer to previous node

   Set dll.Tail to dll.Tail.Previous to remove the last node.

2. Step 2: Set new tail's next pointer to null

   Update dll.Tail.Next to null to mark the end of the list.

3. Final Answer:

   dll.Tail = dll.Tail.Previous; dll.Tail.Next = null; -> Option B

4. Quick Check:

   Correct tail update syntax = dll.Tail = dll.Tail.Previous; dll.Tail.Next = null; [OK]

Hint: Tail moves back, next pointer cleared [OK]

Common Mistakes:

• Updating head instead of tail
• Not setting tail's next to null
• Setting both head and tail to null unnecessarily

3. Consider the following C# code that deletes the last node from a doubly linked list. What will be the printed list after deletion?

dll.AddLast(1); dll.AddLast(2); dll.AddLast(3); dll.DeleteFromEnd(); dll.PrintList();

medium

A. 2 -> 3 -> null

B. 1 -> 2 -> 3 -> null

C. 1 -> 2 -> null

D. null

Solution

1. Step 1: Add nodes 1, 2, 3 to the list

   The list becomes 1 -> 2 -> 3 -> null.

2. Step 2: Delete the last node (3)

   After deletion, the list becomes 1 -> 2 -> null.

3. Final Answer:

   1 -> 2 -> null -> Option C

4. Quick Check:

   Last node removed, list ends at 2 [OK]

Hint: Deleting last removes tail node only [OK]

Common Mistakes:

• Assuming list remains unchanged
• Deleting head instead of tail
• Printing list before deletion

4. The following code attempts to delete the last node from a doubly linked list but causes a runtime error. What is the error?

if (dll.Tail != null) { dll.Tail = dll.Tail.Previous; dll.Tail.Next = null; }

medium

A. NullReferenceException when list has only one node

B. Syntax error due to missing braces

C. The head pointer is not updated

D. The list becomes circular

Solution

1. Step 1: Check deletion when only one node exists

   If only one node exists, dll.Tail.Previous is null, so dll.Tail becomes null.

2. Step 2: Accessing dll.Tail.Next causes error

   After setting dll.Tail to null, accessing dll.Tail.Next throws NullReferenceException.

3. Final Answer:

   NullReferenceException when list has only one node -> Option A

4. Quick Check:

   Accessing property on null tail causes error [OK]

Hint: Check for null tail before accessing Next [OK]

Common Mistakes:

• Not handling single-node list case
• Ignoring null checks before pointer access
• Assuming head updates automatically

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30 <-> 40. After deleting the last node twice, what will be the list and the tail node's value?

hard

A. 10 <-> 20 -> null, Tail = 20

B. 10 <-> 20 <-> 30 -> null, Tail = 30

C. 10 -> null, Tail = 10

D. Empty list, Tail = null

Solution

1. Step 1: Initial list and first deletion

   List is 10 <-> 20 <-> 30 <-> 40. Deleting last node removes 40, list becomes 10 <-> 20 <-> 30.

2. Step 2: Second deletion removes 30

   After second deletion, list becomes 10 <-> 20, and tail points to node with value 20.

3. Final Answer:

   10 <-> 20 -> null, Tail = 20 -> Option A

4. Quick Check:

   Two deletions remove last two nodes [OK]

Hint: Each deletion removes tail, tail moves back [OK]

Common Mistakes:

• Deleting only one node instead of two
• Not updating tail after deletions
• Confusing head and tail pointers