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.