Кольцевой односвязный список

Кольцевые (круговые, циклические) списки являются разновидностью связных списков. Они могут быть односвязными или двусвязными. Их отличительной особенностью является то, что условной последний элемент хранит ссылку на первый элемент, поэтому список получается замкнутым или кольцевым.

Например, если у нас список состоит из одного головного элемента head, то мы можем замкнуть такой список следующим образом:

head.next = head;

Для реализации возьмем класс элемента, который используется в односвязном списке:

public class Node<T>
{
    public Node(T data)
    {
        Data = data;
    }
    public T Data { get; set; }
    public Node<T> Next { get; set; }
}

Теперь определим класс кольцевого списка:

using System.Collections;
using System.Collections.Generic;

namespace SimpleAlgorithmsApp
{
    public class CircularLinkedList<T> : IEnumerable<T>  // кольцевой связный список
    {
        Node<T> head; // головной/первый элемент
        Node<T> tail; // последний/хвостовой элемент
        int count;  // количество элементов в списке

        // добавление элемента
        public void Add(T data)
        {
            Node<T> node = new Node<T>(data);
            // если список пуст
            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 (previous != null)
                    {
                        // убираем узел current, теперь previous ссылается не на current, а на current.Next
                        previous.Next = current.Next;

                        // Если узел последний,
                        // изменяем переменную tail
                        if (current == tail)
                            tail = previous;
                    }
                    else // если удаляется первый элемент
                    {
                        
                        // если в списке всего один элемент
                        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);
        }
    }
}

Здесь нам также потребуются ссылки на условно первый и последний элемент в виде переменных head и tail, хотя формально список будет кольцевым не будет иметь начала и конца.

Добавление фактически сводится к переустановке указателя на последний элемент tail, а новый элемент помещается между tail и head:

public void Add(T data)
{
    Node<T> node = new Node<T>(data);
    // если список пуст
    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 (previous != null)
            {
                // убираем узел current, теперь previous ссылается не на current, а на current.Next
                previous.Next = current.Next;

                // Если узел последний,
                // изменяем переменную tail
                if (current == tail)
                    tail = previous;
            }
			else // если удаляется первый элемент
			{
				// если в списке всего один элемент
				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;
}

Применение кольцевого списка:

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 После удаления: \n");
foreach (var item in circularList)
{
    Console.WriteLine(item);
}

Консольный вывод:

Tom
Bob
Alice
Jack

После удаления:

Tom
Alice
Jack