Delete from End of Doubly Linked List in DSA Go - Execution Trace

Concept Flow - Delete from End of Doubly Linked List

Start at head

↓

Traverse to last node

↓

Check if list empty?

↓

Done

↓

Set new tail.next = null

↓

Delete old tail node

↓

Done

Start at head, move to last node, if list empty stop. Otherwise, update tail to previous node, remove last node, finish.

Execution Sample

DSA Go

func deleteFromEnd(head *Node) *Node {
  if head == nil {
    return nil
  }
  current := head
  for current.next != nil {
    current = current.next
  }
  if current.prev != nil {
    current.prev.next = nil
  } else {
    head = nil
  }
  return head
}

Deletes the last node from a doubly linked list and returns the updated head.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list 10 <-> 20 <-> 30 <-> 40	10 <-> 20 <-> 30 <-> 40	head points to 10	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │←── │ prev:10│←── │ prev:20│←── │ prev:30│ │ next:20│──→ │ next:30│──→ │ next:40│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
2	Traverse to last node (40)	10 <-> 20 <-> 30 <-> 40	current moves from 10 → 20 → 30 → 40	Same as step 1, pointer current at node 40
3	Delete last node (40)	10 <-> 20 <-> 30	Node 30.next set to nil, node 40 removed	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head new tail
4	Return updated head	10 <-> 20 <-> 30	head unchanged	Same as step 3
5	Delete from empty list	empty	head is nil, no change	List is empty (null)

💡 Stop when last node is deleted or list is empty

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
head	points to 10	points to 10	points to 10	points to 10
current	points to 10	points to 40	points to 40 (deleted)	nil
last node	none	40	deleted	none
list size	4 nodes	4 nodes	3 nodes	3 nodes

Key Moments - 3 Insights

Why do we need to check if current.prev is nil before deleting?

Because if current.prev is nil, it means the list has only one node. Deleting it means the list becomes empty, so head must be set to nil (see step 3 in execution_table).

Why do we stop traversal at current.next == nil and not current == nil?

Because current.next == nil means current is the last node. We want to delete the last node, so we stop at it (see step 2 in execution_table).

What happens to the removed node's memory?

In Go, garbage collection automatically frees memory of nodes no longer referenced after pointer changes (step 3).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what pointer change happens?

A Node 30.next is set to nil

B Node 40.prev is set to nil

C Head is set to nil

D Current moves to node 20

💡 Hint

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

At which step does the list size reduce from 4 to 3?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at 'list size' row in variable_tracker after each step

If the list had only one node, what would happen to head after deletion?

A Head points to the same node

B Head points to nil

C Head points to next node

D Head points to previous node

💡 Hint

Refer to key_moments about deleting the only node and step 3 in execution_table

Concept Snapshot

Delete from End of Doubly Linked List:
- Traverse from head to last node (where next is nil)
- If list empty, do nothing
- If only one node, set head to nil
- Else set prev node's next to nil
- Removed node is unlinked and garbage collected

Full Transcript

To delete the last node from a doubly linked list, start at the head and move forward until you reach the last node where next is nil. If the list is empty, no deletion happens. If the list has only one node, deleting it means the list becomes empty, so head is set to nil. Otherwise, update the previous node's next pointer to nil to unlink the last node. The removed node is then freed by garbage collection. This process ensures the list remains connected and valid after deletion.

Practice

1. What happens to the tail pointer when you delete the last node from a doubly linked list?

easy

A. The tail pointer becomes null immediately.

B. The tail pointer moves to the next node.

C. The tail pointer does not change.

D. The tail pointer moves to the previous node.

Solution

1. Step 1: Understand the tail pointer role

   The tail pointer points to the last node in the doubly linked list.

2. Step 2: Effect of deleting the last node

   When the last node is deleted, the tail pointer must move to the previous node to remain valid.

3. Final Answer:

   The tail pointer moves to the previous node. -> Option D

4. Quick Check:

   Tail moves backward after deletion [OK]

Hint: Tail always points to last node; update to previous on delete [OK]

Common Mistakes:

• Not updating tail pointer after deletion
• Setting tail to next node which is null
• Leaving tail pointer unchanged

2. Which of the following Go code snippets correctly deletes the last node from a doubly linked list named dll?

easy

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

B. dll.tail = dll.tail.prev; dll.tail.next = nil

C. dll.head = dll.head.next; dll.head.prev = nil

D. dll.head = dll.tail; dll.tail = nil

Solution

1. Step 1: Identify correct pointer updates for tail deletion

   Deleting last node means tail moves to previous node and new tail's next is nil.

2. Step 2: Check code correctness

   dll.tail = dll.tail.prev; dll.tail.next = nil sets tail to previous node and sets tail.next to nil, which is correct.

3. Final Answer:

   dll.tail = dll.tail.prev; dll.tail.next = nil -> Option B

4. Quick Check:

   Tail moves back, next cleared [OK]

Hint: Tail moves to prev; set tail.next to nil [OK]

Common Mistakes:

• Moving tail forward instead of backward
• Not setting tail.next to nil
• Changing head pointer instead of tail

3. What is the output of the following Go code that deletes the last node from a doubly linked list?

package main
import "fmt"

type Node struct {
    data int
    prev *Node
    next *Node
;
}

type DoublyLinkedList struct {
    head *Node
    tail *Node
;
}

func (dll *DoublyLinkedList) DeleteFromEnd() {
    if dll.tail == nil {
        return
    }
    if dll.tail.prev == nil {
        dll.head = nil
        dll.tail = nil
        return
    }
    dll.tail = dll.tail.prev
    dll.tail.next = nil
}

func (dll *DoublyLinkedList) Print() {
    current := dll.head
    for current != nil {
        fmt.Print(current.data, " -> ")
        current = current.next
    }
    fmt.Println("null")
}

func main() {
    n1 := &Node{data: 1}
    n2 := &Node{data: 2}
    n3 := &Node{data: 3}
    n1.next = n2
    n2.prev = n1
    n2.next = n3
    n3.prev = n2
    dll := DoublyLinkedList{head: n1, tail: n3}
    dll.DeleteFromEnd()
    dll.Print()
}

medium

A. 1 -> 2 -> null

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

C. 2 -> 3 -> null

D. null

Solution

1. Step 1: Initial list and deletion

   List is 1 -> 2 -> 3 -> null. DeleteFromEnd removes last node (3).

2. Step 2: After deletion

   Tail moves to node with data 2, tail.next set to nil. List becomes 1 -> 2 -> null.

3. Final Answer:

   1 -> 2 -> null -> Option A

4. Quick Check:

   Last node removed, tail updated [OK]

Hint: Deleting end removes last node, tail moves back [OK]

Common Mistakes:

• Not updating tail.next to nil causing dangling pointer
• Printing old list without deletion
• Confusing head and tail pointers

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

func (dll *DoublyLinkedList) DeleteFromEnd() {
    if dll.tail == nil {
        return
    }
    dll.tail = dll.tail.prev
    dll.tail.next = nil
}

medium

A. It should delete from the head, not the tail.

B. It incorrectly sets tail.next to nil before moving tail.

C. It does not handle the case when the list has only one node.

D. It should set head to nil instead of tail.

Solution

1. Step 1: Analyze edge case for single node list

   If list has one node, tail.prev is nil, so after tail = tail.prev, tail is nil.

2. Step 2: Cause of panic

   Next line tries to access tail.next but tail is nil, causing runtime panic.

3. Final Answer:

   It does not handle the case when the list has only one node. -> Option C

4. Quick Check:

   Missing single-node check causes nil pointer panic [OK]

Hint: Check for single-node list before updating tail [OK]

Common Mistakes:

• Not checking if tail.prev is nil before access
• Assuming list always has multiple nodes
• Ignoring head pointer update when list becomes empty

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30 <-> 40. After deleting the last node twice using the correct delete from end method, what will be the printed list?

hard

A. 10 -> 20 -> null

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

C. 20 -> 30 -> null

D. 10 -> 30 -> null

Solution

1. Step 1: Initial list and first deletion

   List is 10 <-> 20 <-> 30 <-> 40. First deletion removes 40, list becomes 10 <-> 20 <-> 30.

2. Step 2: Second deletion

   Second deletion removes 30, list becomes 10 <-> 20.

3. Step 3: Print list

   Printing from head: 10 -> 20 -> null.

4. Final Answer:

   10 -> 20 -> null -> Option A

5. Quick Check:

   Two deletions remove last two nodes [OK]

Hint: Each delete removes last node, tail moves back [OK]

Common Mistakes:

• Deleting only once instead of twice
• Confusing node values after deletion
• Not updating tail pointer correctly