Delete a Node from Circular Linked List in DSA Python - Build from Scratch

Delete a Node from Circular Linked List

📖 Scenario: Imagine you have a circular chain of friends sitting around a round table. Each friend holds hands with the next friend, and the last friend holds hands with the first, making a circle. Sometimes, a friend leaves the circle, and the chain needs to close the gap so the circle stays unbroken.

🎯 Goal: You will create a circular linked list of friends, then write code to remove a friend by name from the circle, keeping the circle connected.

📋 What You'll Learn

Create a circular linked list with exactly 4 nodes named 'Alice', 'Bob', 'Charlie', and 'Diana' in that order.

Create a variable called name_to_delete and set it to the exact string 'Charlie'.

Write a function called delete_node that takes the head of the circular linked list and name_to_delete, and removes the node with that name from the list.

Print the names of the friends in the circular linked list after deletion, separated by ' -> ', ending with ' -> (back to head)'.

💡 Why This Matters

🌍 Real World

Circular linked lists are used in real-world applications like music playlists that loop, round-robin scheduling, and multiplayer games where players take turns in a circle.

💼 Career

Understanding how to manipulate circular linked lists is important for software engineers working on systems that require continuous looping data structures or efficient resource scheduling.

1

Create the Circular Linked List

Create a class called Node with attributes name and next. Then create four nodes with names 'Alice', 'Bob', 'Charlie', and 'Diana'. Link them in order to form a circular linked list where the last node points back to the first node. Assign the first node to a variable called head.

DSA Python

# Define Node class and create circular linked list with 'Alice', 'Bob', 'Charlie', 'Diana'
# Your code here

Hint

Remember to link the last node's next to the first node to make the list circular.

2

Set the Name to Delete

Create a variable called name_to_delete and set it to the string 'Charlie'.

DSA Python

class Node:
    def __init__(self, name):
        self.name = name
        self.next = None

node1 = Node('Alice')
node2 = Node('Bob')
node3 = Node('Charlie')
node4 = Node('Diana')

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

head = node1

# Create variable name_to_delete with value 'Charlie'
# Your code here

Hint

Use name_to_delete = 'Charlie' exactly.

3

Write the Delete Function

Write a function called delete_node that takes two parameters: head (the start of the circular linked list) and name_to_delete. The function should remove the node with the name matching name_to_delete from the circular linked list and return the new head of the list. Handle cases where the node to delete is the head, a middle node, or the only node in the list.

DSA Python

class Node:
    def __init__(self, name):
        self.name = name
        self.next = None

node1 = Node('Alice')
node2 = Node('Bob')
node3 = Node('Charlie')
node4 = Node('Diana')

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

head = node1

name_to_delete = 'Charlie'

# Define delete_node function below
# Your code here

Hint

Remember to handle deleting the head node by updating the last node's next pointer.

4

Print the Circular Linked List After Deletion

Call the delete_node function with head and name_to_delete. Then print the names of the nodes in the circular linked list starting from the new head, separated by ' -> ', and end with ' -> (back to head)'.

DSA Python

class Node:
    def __init__(self, name):
        self.name = name
        self.next = None

node1 = Node('Alice')
node2 = Node('Bob')
node3 = Node('Charlie')
node4 = Node('Diana')

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

head = node1

name_to_delete = 'Charlie'

def delete_node(head, name_to_delete):
    if head is None:
        return None

    current = head
    prev = None

    # If only one node and it matches
    if current.name == name_to_delete and current.next == current:
        return None

    # If head needs to be deleted
    if current.name == name_to_delete:
        # Find last node to update its next
        while current.next != head:
            current = current.next
        current.next = head.next
        head = head.next
        return head

    prev = head
    current = head.next

    while current != head:
        if current.name == name_to_delete:
            prev.next = current.next
            return head
        prev = current
        current = current.next

    return head

# Call delete_node and print the circular linked list
# Your code here

Hint

Traverse the circular linked list starting from the new head and collect names until you reach the head again.

Practice

1. What happens when you delete the head node from a circular linked list with multiple nodes?

easy

A. The head moves to the next node and the list remains circular

B. The list becomes empty

C. The last node is deleted instead

D. The list breaks and becomes linear

Solution

1. Step 1: Understand the head deletion in circular linked list

   When the head node is deleted, the next node becomes the new head.

2. Step 2: Maintain circular link

   The last node's next pointer is updated to point to the new head, keeping the list circular.

3. Final Answer:

   The head moves to the next node and the list remains circular -> Option A

4. Quick Check:

   Head deletion updates head and keeps circular [OK]

Hint: Deleting head shifts head to next, list stays circular [OK]

Common Mistakes:

• Assuming list becomes empty after head deletion
• Not updating last node's next pointer
• Breaking circular link accidentally

2. Which of the following is the correct syntax to delete a node with value `key` from a circular linked list in Python?

easy

A. def deleteNode(head, key):
if head.data == key:
# delete head logic

B. def deleteNode(head, key):
while head.data != key:
head = head.next

C. def deleteNode(head, key):
if head is None:
return None

D. def deleteNode(head, key):
head = None
return head

Solution

1. Step 1: Check for empty list

   Before deleting, check if the list is empty (head is None) to avoid errors.

2. Step 2: Return None if list is empty

   If head is None, return None as there is nothing to delete.

3. Final Answer:

   def deleteNode(head, key): if head is None: return None -> Option C

4. Quick Check:

   Empty list check is essential before deletion [OK]

Hint: Always check if list is empty before deleting [OK]

Common Mistakes:

• Not checking if head is None before deletion
• Incorrectly looping without exit condition
• Setting head to None without condition

3. What will be the output list after deleting node with value 3 from this circular linked list: 1 -> 3 -> 5 -> 7 -> (back to 1)?

medium

A. 1 -> 5 -> 7 -> 3 -> (back to 1)

B. 1 -> 5 -> 7 -> (back to 1)

C. 1 -> 3 -> 5 -> 7 -> (back to 1)

D. 3 -> 5 -> 7 -> (back to 3)

Solution

1. Step 1: Locate node with value 3

   Traverse the list to find node with value 3 between 1 and 5.

2. Step 2: Remove node 3 and link 1 to 5

   Update node 1's next pointer to node 5, skipping node 3.

3. Final Answer:

   1 -> 5 -> 7 -> (back to 1) -> Option B

4. Quick Check:

   Deleted 3, linked 1 to 5 [OK]

Hint: Skip the node with key, link previous to next [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Deleting wrong node or not deleting at all
• Breaking circular link after deletion

4. Given this code snippet to delete a node from a circular linked list, what is the bug?

def deleteNode(head, key):
    if head is None:
        return None
    curr = head
    while curr.next != head:
        if curr.next.data == key:
            curr.next = curr.next.next
            return head
        curr = curr.next
    return head

medium

A. Does not handle deletion if head node contains the key

B. Infinite loop due to missing break

C. Deletes all nodes instead of one

D. Returns None instead of head

Solution

1. Step 1: Analyze deletion logic

   The code checks nodes after head but never checks if head itself has the key.

2. Step 2: Identify missing head deletion handling

   If head contains the key, this code will not delete it, causing incorrect behavior.

3. Final Answer:

   Does not handle deletion if head node contains the key -> Option A

4. Quick Check:

   Head node deletion must be handled separately [OK]

Hint: Always check if head node matches key before loop [OK]

Common Mistakes:

• Ignoring head node in deletion logic
• Assuming loop covers all nodes including head
• Not updating head pointer after deletion

5. You have a circular linked list with only one node containing value 10. What should be the list after deleting node with value 10?

hard

A. List with node 10 pointing to None

B. List with node 10 pointing to itself

C. List unchanged

D. Empty list (None)

Solution

1. Step 1: Identify single node list condition

   When the list has only one node, head.next points to head itself.

2. Step 2: Delete the only node

   Deleting this node means the list becomes empty, so head should be None.

3. Final Answer:

   Empty list (None) -> Option D

4. Quick Check:

   Single node deletion empties the list [OK]

Hint: Deleting sole node results in empty list (None) [OK]

Common Mistakes:

• Leaving node pointing to itself after deletion
• Not setting head to None
• Assuming list still has one node