Кольцевой двусвязный список представляет замкнутый список, в котором указатель на элемент может перемещаться как вперед, так и назад по кругу.
Каждый узел такого списка опять же будет представлять элемент, который хранит указатели на следующий и предыдущий узлы:
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++; }
Частным случаем здесь будет являться ситуация, когда список пуст. Тогда устанавливается головной элемент 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; }
Применение класса:
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