8. Списки. Линейные односвязные и двумерные списки. Класс LinkedList<T>.

1. Списки.

И снова мы возвращаемся к структурам данных.

Мы уже научились использовать массивы для решения самых разных задач, поговорили про их основные недостатки.

Разобрали достоинства и недостатки динамических массивов и структуры List.

Сегодня мы продолжим разговор о динамических структурах и познакомимся с понятием Список.

Связный список представляет собой коллекцию связанных элементов, которые содержат в себе хранимые данные, а также ссылку на связанные с ним элементы (один или несколько). Основным преимуществом данной структуры данных перед обычным массивом является ее динамичность — возможность легко менять количество элементов.

2. Линейные односвязные списки.

Основной недостаток обычных массивов, кроме фиксированного (или с большим трудом изменяемого размера) – высокая сложность операций вставки и удаления элементов О(n). Для решения двух этих проблем часто динамические структуры представляются в виде связных списков. Это не значит, что связные списки идеальны: приобретая что-то, мы чем-то жертвуем взамен. Но об этом чуть позже…

Связный список – структура, элементы которой имеют один и тот же формат и связаны друг с другом с помощью указателей, хранящихся в самих элементах.

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

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

Основные операции над линейным односвязным списком:

• перемещение по списку;
• включение элемента в линейный односвязный список;
• исключение элемента из линейного односвязного списка;
• извлечение данных из любого элемента;
• изменение данных любого элемента;
• подсчет количества элементов списка.

Продвижение в линейном односвязном списке возможно только в одном направлении.

3. Линейные двусвязные списки.

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

Продвижение в линейном двусвязном списке возможно в любом направлении. Операции вставки элемента в линейный двусвязный список и удаления элемента из линейного двусвязного списка реализуются аналогично соответствующим операциям над линейным односвязным списком.

4. Класс LinkedList<T>.

Конечно, понимая принципы работы списка, можно самостоятельно написать все методы обработки данных в списках, но в языке C# есть готовый класс для работы с двусвязными списками.

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

В LinkedList<T> каждый узел представляет объект класса LinkedListNode<T>.

Этот класс имеет следующие свойства:

• Value: само значение узла, представленное типом T.
• Next: ссылка на следующий элемент типа LinkedListNode<T> в списке. Если следующий элемент отсутствует, то имеет значение null.
• Previous: ссылка на предыдущий элемент типа LinkedListNode<T> в списке. Если предыдущий элемент отсутствует, то имеет значение null.

Используя методы класса LinkedList<T>, можно обращаться к различным элементам, как в конце, так и в начале списка:

• AddAfter (LinkedListNode<T> node, LinkedListNode<T> newNode): вставляет узел newNode в список после узла node.
• AddAfter (LinkedListNode<T> node, T value): вставляет в список новый узел со значением value после узла node.
• AddBefore (LinkedListNode<T> node, LinkedListNode<T> newNode): вставляет в список узел newNode перед узлом node.
• AddBefore (LinkedListNode<T> node, T value): вставляет в список новый узел со значением value перед узлом node.
• AddFirst (LinkedListNode<T> node): вставляет новый узел в начало списка.
• AddFirst (T value): вставляет новый узел со значением value в начало списка.
• AddLast (LinkedListNode<T> node): вставляет новый узел в конец списка.
• AddLast (T value): вставляет новый узел со значением value в конец списка.
• RemoveFirst(): удаляет первый узел из списка. После этого новым первым узлом становится узел, следующий за удаленным.
• RemoveLast(): удаляет последний узел из списка.
• Find(): возвращает ссылку на первый узел в списке, имеющий передаваемое значение. Если искомое значение отсутствует в списке, то возвращается пустое значение.
• Remove(): удаляет из списка первый узел, содержащий передаваемое значение. Возвращает логическое значение true, если узел удален, т.е. если узел со значением обнаружен в списке и удален; в противном случае возвращает логическое значение false.

Преимущество связного списка проявляется в том, что операция вставки элемента в середину выполняется очень быстро. При этом только ссылки Next (следующий) предыдущего элемента и Previous (предыдущий) следующего элемента должны быть изменены так, чтобы указывать на вставляемый элемент.

Естественно, у связных списков есть и свои недостатки. Так, например, все элементы связных списков доступны лишь друг за другом. Поэтому для нахождения элемента, находящегося в середине или конце списка, требуется довольно много времени. Кроме этого, связный список не просто хранит элементы внутри себя, вместе с каждым из них ему необходимо иметь информацию о следующем и предыдущем элементах, то есть он занимает больше памяти.

Давайте рассмотрим пример использования связных списков.

Фрагмент кода программы:

public static void Main(string[] args)
{
    // Создадим связный список
    LinkedList<string> link = new LinkedList<string>();

    // Добавим несколько элементов
    link.AddFirst("Alex");
    link.AddFirst("Djek");
    link.AddFirst("Bob");
    link.AddFirst("Doug");

    // Отобразим элементы в прямом направлении
    LinkedListNode<string> node;
    Console.WriteLine("Элементы коллекции в прямом направлении: ");
    node = link.First;
    while (node != null)
    {
        Console.Write(node.Value + "\t");
        node = node.Next;
    }

    // Отобразить элементы в обратном направлении
    Console.WriteLine("\n\nЭлементы коллекции в обратном направлении: ");
    node = link.Last;
    while (node != null)
    {
        Console.Write(node.Value + "\t");
        node = node.Previous;
    }
}

И еще один пример на двухсвязный список в действии:

class Person
{
    public string Name { get; set; }
}

internal class Program
{
    static void Main(string[] args)
    {
        LinkedList<Person> persons = new LinkedList<Person>();

        Person tom = new Person() {Name = "Tom"};
        persons.AddLast(tom);
        persons.AddLast(new Person() {Name = "John"});
        persons.AddFirst(new Person() {Name = "Bill"});

        LinkedListNode<Person> tomLink = persons.Find(tom);

        Console.WriteLine(tomLink.Previous.Value.Name);
        Console.WriteLine(tomLink.Next.Value.Name);
    }
}

Здесь создается и используется список для объектов класса Person.

Вопрос 1: Оцените сложность поиска элемента по его порядковому номеру в LinkedList.

Вопрос 2: Оцените сложность удаления последнего элемента в LinkedList.

Итоги занятия