Связный список: класс LinkedList
Класс LinkedList<T> представляет собой двухсвязный список, в котором каждый элемент ссылается на следующий и предыдущий, как показано на рисунке:
Преимущество связного списка проявляется в том, что операция вставки элемента в середину выполняется очень быстро. При этом только ссылки Next (следующий) предыдущего элемента и Previous (предыдущий) следующего элемента должны быть изменены так, чтобы указывать на вставляемый элемент. В классе List<T> при вставке нового элемента все последующие должны быть сдвинуты.
Естественно, у связных списков есть и свои недостатки. Так, например, все элементы связных списков доступны лишь друг за другом. Поэтому для нахождения элемента, находящегося в середине или конце списка, требуется довольно много времени. Связный список не может просто хранить элементы внутри себя. Вместе с каждым из них ему необходимо иметь информацию о следующем и предыдущем элементах. Вот почему LinkedList<T> содержит элементы типа LinkedListNode<T>. С помощью класса LinkedListNode<T> появляется возможность обратиться к предыдущему и последующему элементам списка. Класс LinkedListNode<T> определяет свойства List, Next, Previous и Value. Свойство List возвращает объект LinkedList<T>, ассоциированный с узлом. Свойства Next и Previous предназначены для итераций по списку и для доступа к следующему и предыдущему элементам. Свойство Value типа T возвращает элемент, ассоциированный с узлом.
Сам класс LinkedList<T> определяет члены для доступа к первому (First) и последнему (Last) элементам в списке, для вставки элементов в определенные позиции (AddAfter(), AddBefore(), AddFirst(), AddLast()), для удаления элементов из заданных позиций (Remove(), RemoveFirst(), RemoveLast()) и для нахождения элементов, начиная поиск либо с начала (Find()), либо с конца (FindLast()) списка.
В классе LinkedList<T> реализуются интерфейсы ICollection, ICollection<T>, IEnumerable, IEnumerable<T>, ISerializable и IDeserializationCallback. В двух последних интерфейсах поддерживается сериализация списка. В классе LinkedList<T> определяются два приведенных ниже открытых конструктора:
public LinkedList() public LinkedList(IEnumerable<T> collection)
В первом конструкторе создается пустой связный список, а во втором конструкторе — список, инициализируемый элементами из коллекции collection.
В классе LinkedList<T> определяется немало методов. Наиболее часто используемые методы, определенные в классе LinkedList<T> представлены ниже:
- AddAfter()
-
Добавляет в список узел со значением непосредственно после указанного узла. Указываемый узел не должен быть пустым (null). Метод возвращает ссылку на узел, содержащий значение.
- AddBefore()
-
Добавляет в список узел со значением value непосредственно перед указанным узлом. Указываемый узел не должен быть пустым (null). Метод возвращает ссылку на узел, содержащий значение.
- AddFirst(), AddLast()
-
Добавляют узел со значением в начало или в конец списка.
- Find()
-
Возвращает ссылку на первый узел в списке, имеющий передаваемое значение. Если искомое значение отсутствует в списке, то возвращается пустое значение.
- Remove()
-
Удаляет из списка первый узел, содержащий передаваемое значение. Возвращает логическое значение true, если узел удален, т.е. если узел со значением обнаружен в списке и удален; в противном случае возвращает логическое значение false.
Давайте рассмотрим пример использования связных списков:
using System; using System.Collections.Generic; namespace ConsoleApplication1 { class Program { static void Main() { // Создадим связный список LinkedList<string> link = new LinkedList<string>(); // Добавим несколько элементов link.AddFirst("Alex"); link.AddFirst("Djek"); link.AddFirst("Bob"); link.AddFirst("Doug"); // Отобразим элементы в прямом направлении LinkedListNode<string> node; Console.WriteLine("Элементы коллекции в прямом направлении: "); for (node = link.First; node != null; node = node.Next) Console.Write(node.Value + "\t"); // Отобразить элементы в обратном направлении Console.WriteLine("\n\nЭлементы коллекции в обратном направлении: "); for (node = link.Last; node != null; node = node.Previous) Console.Write(node.Value + "\t"); Console.ReadLine(); } } }
Самое примечательное в этой программе — это обход списка в прямом и обратном направлении, следуя по ссылкам, предоставляемым свойствами Next и Previous. Двунаправленный характер подобных связных списков имеет особое значение для приложений, управляющих базами данных, где нередко требуется перемещаться по списку в обоих направлениях.
Комментарии