Circular singly linked list
Circular lists are a type of linked list. They can be singly or doubly linked. Their distinguishing feature is that the last element stores a reference to the first element, creating a closed or circular list.
For example, if we have a list consisting of one head element, then we can close such a list as follows:
1 | head.next = head; |
For implementation, we will take the element class that is used in a singly linked list:
1 2 3 4 5 6 7 8 9 | public class Node<T>{ public Node(T data) { Data = data; } public T Data { get; set; } public Node<T> Next { get; set; }} |
Now, let’s define a circular list class:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | using System.Collections;using System.Collections.Generic;namespace SimpleAlgorithmsApp{ public class CircularLinkedList<T> : IEnumerable<T> // circular linked list { Node<T> head; // head/first element Node<T> tail; // last/tail element int count; //number of elements in the list //adding an element public void Add(T data) { Node<T> node = new Node<T>(data); // if the list is empty if (head == null) { head = node; tail = node; tail.Next = head; } else { node.Next = head; tail.Next = node; tail = node; } count++; } public bool Remove(T data) { Node<T> current = head; Node<T> previous = null; if (IsEmpty) return false; do { if (current.Data.Equals(data)) { // If the knot is in the middle or at the end if (previous != null) { // we remove the current node, now previous refers not to current, but to current.Next previous.Next = current.Next; // If the node is the last one, // change the variable tail if (current == tail) tail = previous; } else // if the first element is removed { // if there is only one element in the list if(count==1) { head = tail = null; } else { head = current.Next; tail.Next = current.Next; } } count--; return true; } previous = current; current = current.Next; } while (current != head); return false; } public int Count { get { return count; } } public bool IsEmpty { get { return count == 0; } } public void Clear() { head = null; tail = null; count = 0; } public bool Contains(T data) { Node<T> current = head; if (current == null) return false; do { if (current.Data.Equals(data)) return true; current = current.Next; } while (current != head); return false; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator<T> IEnumerable<T>.GetEnumerator() { Node<T> current = head; do { if (current != null) { yield return current.Data; current = current.Next; } } while (current != head); } }} |
Here, we’ll also need references to the conditional first and last elements in the form of the variables head and tail, although formally the list will be circular and have no beginning or end. Adding actually amounts to resetting the pointer to the last element, tail, and placing the new element between tail and head:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public void Add(T data){ Node<T> node = new Node<T>(data); // if the list is empty if (head == null) { head = node; tail = node; tail.Next = head; } else { node.Next = head; tail.Next = node; tail = node; } count++;} |
When deleting, we reset the pointer to the next element at the previous element in relation to the one being deleted:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | public bool Remove(T data){ Node<T> current = head; Node<T> previous = null; if (IsEmpty) return false; do { if (current.Data.Equals(data)) { // If the knot is in the middle or at the end if (previous != null) { // We remove the current node, now previous refers not to current, but to current.Next previous.Next = current.Next; // If the node is the last one, // change the variable tail if (current == tail) tail = previous; } else //if the first element is removed { // if there is only one element in the list if(count==1) { head = tail = null; } else { head = current.Next; tail.Next = current.Next; } } count--; return true; } previous = current; current = current.Next; } while (current != head); return false;} |
Using a ring list:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | CircularLinkedList<string> circularList = new CircularLinkedList<string>();circularList.Add("Tom");circularList.Add("Bob");circularList.Add("Alice");circularList.Add("Jack");foreach (var item in circularList){ Console.WriteLine(item);}circularList.Remove("Bob");Console.WriteLine("\n After removal: \n");foreach (var item in circularList){ Console.WriteLine(item);} |
Console output:
Tom
Bob
Alice
Jack
After removal:
Tom
Alice
JackExplore More IT Terms
A
B
C
D
E
F
H
K
W
- What are databases, and why do they need DBMS and SQL?
- What do Linux distributions consist of?
- What is a GPU in a computer, in simple terms?
- What is Linux? The History of Linux
- What is the OSI Model: A Complete Explanation of the Seven Layers and Their Role in Networking
- Which Linux distribution should you choose? A Linux distribution overview