Двусвязные списки также представляют последовательность связанных узлов, однако теперь каждый узел хранит ссылку на следующий и на предыдущий элементы.
Двунаправленность списка приходится учитывать при добавлении или удалении элемента, так как кроме ссылки на следующий элемент надо устанавливать и ссылку на предыдущий. Но в то же время у нас появляется возможность обходить список как от первого к последнему элементу, так и наоборот - от последнего к первому элементу. В остальном двусвязный список ни чем не будет отличаться от односвязного списка.
Для создания двусвязного списка вначале надо определить класс узла, который будет представлять элемент списка:
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.Generic; using System.Collections; namespace SimpleAlgorithmsApp { public class DoublyLinkedList<T> : IEnumerable<T> // двусвязный список { DoublyNode<T> head; // головной/первый элемент DoublyNode<T> tail; // последний/хвостовой элемент int count; // количество элементов в списке // добавление элемента public void Add(T data) { DoublyNode<T> node = new DoublyNode<T>(data); if (head == null) head = node; else { tail.Next = node; node.Previous = tail; } tail = node; count++; } public void AddFirst(T data) { DoublyNode<T> node = new DoublyNode<T>(data); DoublyNode<T> temp = head; node.Next = temp; head = node; if (count == 0) tail = head; else temp.Previous = node; count++; } // удаление public bool Remove(T data) { DoublyNode<T> current = head; // поиск удаляемого узла while (current != null) { if (current.Data.Equals(data)) { break; } current = current.Next; } if(current!=null) { // если узел не последний if(current.Next!=null) { current.Next.Previous = current.Previous; } else { // если последний, переустанавливаем tail tail = current.Previous; } // если узел не первый if(current.Previous!=null) { current.Previous.Next = current.Next; } else { // если первый, переустанавливаем head head = current.Next; } count--; return true; } 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) { DoublyNode<T> current = head; while (current != null) { if (current.Data.Equals(data)) return true; current = current.Next; } return false; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator<T> IEnumerable<T>.GetEnumerator() { DoublyNode<T> current = head; while (current != null) { yield return current.Data; current = current.Next; } } public IEnumerable<T> BackEnumerator() { DoublyNode<T> current = tail; while (current != null) { yield return current.Data; current = current.Previous; } } } }
По большому счету этот двусвязный список реализует те же действия, что и односвязный, разница заключается в необходимости установки свойства Previous для узлов списка.
В методе добавления Add()
, если в списке уже есть элементы, то у добавляемого узла свойство Previous
указывает на узел, который до этого
хранился в переменной tail:
if (head == null) head = node; else { tail.Next = node; node.Previous = tail; } tail = node;
Аналогично в методе AddFirst
добавлении в начало списка для головного элемента свойство Previous начинает указывать на новый элемент, а новый
элемент, таким образом, становиться первым элементом в списке.
При удалении вначале необходимо найти удаляемый элемент. Затем в общем случае надо переустановить две ссылки:
current.Next.Previous = current.Previous; current.Previous.Next = current.Next;
Если удаляются первый и последний элемент, соответственно надо переустановить переменные head и tail.
И также в отличие от односвязной реализации здесь добавлен метод BackEnumerator()
для перебора элементов с конца.
Применение списка:
DoublyLinkedList<string> linkedList = new DoublyLinkedList<string>(); // добавление элементов linkedList.Add("Bob"); linkedList.Add("Bill"); linkedList.Add("Tom"); linkedList.AddFirst("Kate"); foreach (var item in linkedList) { Console.WriteLine(item); } // удаление linkedList.Remove("Bill"); // перебор с последнего элемента foreach (var t in linkedList.BackEnumerator()) { Console.WriteLine(t); }