Связный список: класс LinkedList<T>

C# --- Руководство по C# --- Связный список: класс LinkedList<T>

Класс 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. Двунаправленный характер подобных связных списков имеет особое значение для приложений, управляющих базами данных, где нередко требуется перемещаться по списку в обоих направлениях.