Delete from End of Doubly Linked List in DSA Java - 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: Direct pointer updates without loops or recursion.
• How many times: Exactly once per call, no repetition over list size.

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
100	4
1000	4

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 fixed amount of time regardless of list size.

Common Mistake

[X] Wrong: "Deleting from the end takes longer as the list grows because you must find the last node."

[OK] Correct: The doubly linked list keeps a direct reference to the last node (tail), so no searching is needed.

Interview Connect

Knowing that deleting from the end is quick helps you explain efficient list operations clearly and confidently.

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 second last node becomes the new tail and its next pointer is set to null.

B. The head pointer is set to null.

C. The list becomes circular.

D. The first node is deleted instead.

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, making it the new tail.

3. Final Answer:

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

4. Quick Check:

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

Hint: Tail's previous node next pointer becomes 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 Java code snippets correctly deletes the last node from a doubly linked list named dll?

easy

A. dll.tail.next = dll.tail.prev; dll.tail = null;

B. dll.head = dll.head.next; dll.head.prev = null;

C. dll.tail = dll.tail.prev; dll.tail.next = null;

D. dll.head.prev = dll.tail; dll.tail = dll.tail.next;

Solution

1. Step 1: Move tail pointer to previous node

   Set dll.tail to dll.tail.prev to remove last node reference.

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

   Update dll.tail.next to null to mark end of list.

3. Final Answer:

   dll.tail = dll.tail.prev; dll.tail.next = null; -> Option C

4. Quick Check:

   Correct tail update and next pointer null [OK]

Hint: Tail moves back, next pointer set to null [OK]

Common Mistakes:

• Updating head instead of tail
• Setting tail to null without updating pointers
• Confusing next and prev pointers

3. Consider the following Java code for deleting the last node from a doubly linked list:

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

class DoublyLinkedList {
  Node head, tail;

  void deleteFromEnd() {
    if (tail == null) return;
    if (head == tail) {
      head = tail = null;
      return;
    }
    tail = tail.prev;
    tail.next = null;
  }
}

DoublyLinkedList dll = new DoublyLinkedList();
dll.head = new Node(1);
Node second = new Node(2);
dll.head.next = second;
second.prev = dll.head;
dll.tail = second;
dll.deleteFromEnd();
System.out.println(dll.head.data + " -> " + (dll.head.next == null ? "null" : dll.head.next.data));

What is the output?

medium

A. 1 -> 2

B. null -> null

C. 2 -> null

D. 1 -> null

Solution

1. Step 1: Setup list with two nodes 1 and 2

   Head points to node 1, tail points to node 2, linked properly.

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

   Tail moves to node 1, tail.next set to null, removing node 2.

3. Final Answer:

   1 -> null -> Option D

4. Quick Check:

   After deletion, only node 1 remains with next null [OK]

Hint: After deleting tail, tail.prev.next is null [OK]

Common Mistakes:

• Printing old tail node data
• Not updating tail.next to null
• Confusing head and tail pointers

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

void deleteFromEnd() {
  if (tail == null) return;
  tail = tail.prev;
  tail.next = null;
}

What is the error and how to fix it?

medium

A. Compilation error due to missing semicolon; fix by adding semicolon.

B. NullPointerException when list has one node; fix by checking if tail.prev is null.

C. Logical error deleting head instead of tail; fix by updating head pointer.

D. No error; code works fine.

Solution

1. Step 1: Identify cause of NullPointerException

   If list has one node, tail.prev is null, so tail becomes null, then tail.next causes error.

2. Step 2: Fix by checking single node case

   Add condition: if head == tail, set head and tail to null before updating pointers.

3. Final Answer:

   NullPointerException when list has one node; fix by checking if tail.prev is null. -> Option B

4. Quick Check:

   Check single node case before pointer update [OK]

Hint: Check if tail.prev is null before accessing tail.next [OK]

Common Mistakes:

• Not handling single node list
• Assuming tail.prev always exists
• Ignoring null pointer exceptions

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30 <-> 40. After deleting the last node twice using the correct deleteFromEnd method, what is the final list?

hard

A. 10 <-> 20

B. 10 <-> 20 <-> 30

C. 20 <-> 30

D. 30 <-> 40

Solution

1. Step 1: Delete last node once

   Deleting last node 40 removes it; list becomes 10 <-> 20 <-> 30.

2. Step 2: Delete last node second time

   Deleting last node 30 removes it; list becomes 10 <-> 20.

3. Final Answer:

   10 <-> 20 -> Option A

4. Quick Check:

   Two deletions remove last two nodes [OK]

Hint: Each deleteFromEnd removes tail node [OK]

Common Mistakes:

• Deleting from head instead of tail
• Not updating tail pointer after deletion
• Confusing node values after deletion