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

Последнее обновление: 25.10.2016

Кольцевой двусвязный список представляет замкнутый список, в котором указатель на элемент может перемещаться как вперед, так и назад по кругу.

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

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

Однако несмотря на то, что формально список замкнут, и у него нет начала и конца, все равно для некоторого базового отчета в таком списке будет храниться ссылка на первый элемент, относительно которого будет идти добавление новых элементов. В тоже время в отличие от кольцевого односвязного списка теперь уже не надо хранить указатель на формально последний элемент списка:

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

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

        // добавление элемента
        public void Add(T data)
        {
            DoublyNode<T> node = new DoublyNode<T>(data);

            if (head == null)
            {
                head = node;
                head.Next = node;
                head.Previous = node;
            }
            else
            {
                node.Previous = head.Previous;
                node.Next = head;
                head.Previous.Next = node;
                head.Previous = node;
            }
            count++;
        }
		// удаление элемента
        public bool Remove(T data)
        {
            DoublyNode<T> current = head;

            DoublyNode<T> removedItem = null;
            if (count == 0) return false;

            // поиск удаляемого узла
            do
            {
                if (current.Data.Equals(data))
                {
                    removedItem = current;
                    break;
                }
                current = current.Next;
            }
            while (current!=head);

            if (removedItem != null)
            {
                // если удаляется единственный элемент списка
                if (count==1)
                    head = null;
                else
                {
                    // если удаляется первый элемент
                    if(removedItem==head)
                    {
                        head = head.Next;
                    }
                    removedItem.Previous.Next = removedItem.Next;
                    removedItem.Next.Previous = removedItem.Previous;
                }
                count--;
                return true;
            }
            return false;
        }
        public int Count { get { return count; } }
        public bool IsEmpty { get { return count == 0; } }

        public void Clear()
        {
            head = null;
            count = 0;
        }

        public bool Contains(T data)
        {
            DoublyNode<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()
        {
            DoublyNode<T> current = head;
            do
            {
                if (current != null)
                {
                    yield return current.Data;
                    current = current.Next;
                }
            }
            while (current != head);
        }
    }
}

Суть добавления состоит в том, что мы переустанавливаем предыдущий элемент по отношению к head:

public void Add(T data)
{
    DoublyNode<T> node = new DoublyNode<T>(data);

    if (head == null)
    {
        head = node;
        head.Next = node;
        head.Previous = node;
    }
    else
    {
        node.Previous = head.Previous;
        node.Next = head;
        head.Previous.Next = node;
        head.Previous = node;
    }
    count++;
}
Добавление в кольцевой двусвязный список в C#

Частным случаем здесь будет являться ситуация, когда список пуст. Тогда устанавливается головной элемент head.

При удалении переустанавливаем указатели у предыдущего и следующего элементов, по отношению к удаляемому:

public bool Remove(T data)
{
    DoublyNode<T> current = head;

    DoublyNode<T> removedItem = null;
    if (count == 0) return false;

    // поиск удаляемого узла
    do
    {
        if (current.Data.Equals(data))
        {
            removedItem = current;
            break;
        }
        current = current.Next;
    }
    while (current!=head);

    if (removedItem != null)
    {
        // если удаляется единственный элемент списка
        if (count==1)
            head = null;
        else
        {
            // если удаляется первый элемент
            if(removedItem==head)
            {
                head = head.Next;
            }
            removedItem.Previous.Next = removedItem.Next;
            removedItem.Next.Previous = removedItem.Previous;
        }
        count--;
        return true;
    }
    return false;
}
Удаление из кольцевого двусвязного списка в C#

Применение класса:

CircularDoublyLinkedList<string> circularList = new CircularDoublyLinkedList<string>();
circularList.Add("Tom");
circularList.Add("Bob");
circularList.Add("Alice");
circularList.Add("Sam");

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
Sam

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

Tom
Alice
Sam
Помощь сайту
Юмани:
410011174743222
Перевод на карту
Номер карты:
4048415020898850