Circular Linked List Implementation in C#

1. Introduction

A Circular Linked List is a variation of the linked list where the last node of the list points back to the first node instead of having a null reference. This circular nature can be useful in scenarios where data needs to be rotated, such as in round-robin scheduling or certain types of cache algorithms.

2. Implementation Steps

1. Define a Node class to represent individual items in the circular linked list. Each node will have two attributes: Value and Next.

2. Create a CircularLinkedList class to manage the nodes and operations.

3. Implement basic operations:

- Append: Add a node to the end of the list.

- DeleteWithValue: Remove the node with a specific value.

- PrintList: Display the contents of the list.

4. Test the circular linked list with these operations.

3. Implementation in C#

using System;
public class Node {
    public int Value;
    public Node Next;
    public Node(int value) {
        this.Value = value;
        this.Next = this;  // By default, it points to itself
    }
}
public class CircularLinkedList {
    private Node head;
    // Add node to the end of the list
    public void Append(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.Next != head) {
                temp = temp.Next;
            }
            temp.Next = newNode;
            newNode.Next = head;
        }
    }
    // Remove the node with a specific value
    public void DeleteWithValue(int value) {
        if (head == null) return;
        Node temp = head;
        Node prev = null;
        do {
            if (temp.Value == value) {
                if (prev != null) {
                    prev.Next = temp.Next;
                    if (head == temp) head = temp.Next;
                } else {
                    Node nextNode = head.Next;
                    if (head == nextNode) {
                        head = null;
                    } else {
                        while (temp.Next != head) {
                            temp = temp.Next;
                        }
                        head = nextNode;
                        temp.Next = nextNode;
                    }
                }
                return;
            }
            prev = temp;
            temp = temp.Next;
        } while (temp != head);
    }
    // Display the contents of the list
    public void PrintList() {
        if (head == null) return;
        Node temp = head;
        do {
            Console.WriteLine(temp.Value);
            temp = temp.Next;
        } while (temp != head);
    }
}
public class Program {
    public static void Main() {
        CircularLinkedList list = new CircularLinkedList();
        list.Append(1);
        list.Append(2);
        list.Append(3);
        list.DeleteWithValue(2);
        list.PrintList();  // Should print: 1 3
    }
}

Output:

1
3

Explanation:

1. The Node class is similar to the one in a singly linked list, but by default, the Next attribute points to itself, making the node circular.

2. In the CircularLinkedList class, the Append method needs to locate the end of the list and then make sure that the new node's Next attribute points back to the head.

3. The DeleteWithValue method becomes a bit more complex because we need to account for the circular nature of the list when removing nodes, especially the head node.

4. The PrintList method traverses the list until it returns to the head node.

5. The logic is tested in the Program class, where nodes are added and removed from the circular linked list.

With this implementation, you can efficiently manage a set of nodes in a circular fashion, making sure that there's no true "end" to the list.


Comments