Алгоритмы и структуры данных для начинающих: связный список

Первая структура данных, которую мы рассмотрим — связный список. На то есть две причины: первое — связный список используется практически везде — от ОС до игр, и второе — на его основе строится множество других структур данных.


Также смотрите другие материалы этой серии: бинарное дерево, стеки и очереди, динамический массив, оценка сложности алгоритма, сортировка и множества.

Связный список

Основное назначение связного списка — предоставление механизма для хранения и доступа к произвольному количеству данных. Как следует из названия, это достигается связыванием данных вместе в список.

Прежде чем мы перейдем к рассмотрению связного списка, давайте вспомним, как хранятся данные в массиве.

data_structures_001

Как показано на рисунке, данные в массиве хранятся в непрерывном участке памяти, разделенном на ячейки определенного размера. Доступ к данным в ячейках осуществляется по ссылке на их расположение — индексу.

Это отличный способ хранить данные. Большинство языков программирования позволяют так или иначе выделить память в виде массива и оперировать его содержимым. Последовательное хранение данных увеличивает производительность (data locality), позволяет легко итерироваться по содержимому и получать доступ к произвольному элементу по индексу.

Тем не менее, иногда массив — не самая подходящая структура.

Предположим, что у нашей программы следующие требования:

  • Прочесть некоторое количество целых чисел из источника (метод NextValue), пока не встретится число 0xFFFF.
  • Передать считанные числа в метод ProcessItems

Поскольку в требованиях указано, что считанные числа передаются в метод ProcessItems за один раз, очевидным решение будет массив целых чисел:

У этого решения есть ряд проблем, но самая очевидная из них — что случится, если будет необходимо прочесть больше 20 значений? В данной реализации значения с 21 и далее просто проигнорируются. Можно выделить больше памяти — 200 или 2000 элементов. Можно дать пользователю возможность выбрать размер массива. Или выделить память под новый массив большего размера при заполнении старого и скопировать элементы. Но все эти решения усложняют код и бесполезно тратят память.

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

Прежде чем перейти к его реализации, давайте посмотрим на то, как могло бы выглядеть решение нашей задачи.

Обратите внимание: проблем, присущих первому варианту решения больше нет — мы не можем выделить недостаточно или, наоборот, слишком много памяти под массив.

Кроме того, из этого кода можно увидеть, что наш список будет принимать параметр типа <T> и реализовывать интерфейс IEnumerable

Реализация класса LinkedList

Класс Node

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

data_structures_002

В самом простом случае класс Node можно реализовать так:

Теперь мы можем создать примитивный связный список. Выделим память под три узла (first, middle, last) и соединим их последовательно:

Теперь у нас есть список из трех элементов, начиная с first и заканчивая last. Поле Next последнего узла имеет значение null, что показывает, что это последний элемент. С этим списком уже можно производить различные операции. Например, напечатать данные из каждого элемента:

Метод PrintList итерируется по элементам списка: печатает значение поля Value и переходит к следующему узлу по ссылке в поле Next.

Теперь, когда мы знаем, как должен выглядеть узел связанного списка, давайте посмотрим на пример реализации класса LinkedListNode.

Класс LinkedList

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

Ранее мы увидели, что коллекция должна поддерживать любой тип данных, а значит, нам нужно реализовать обобщенный интерфейс.

Поскольку мы используем платформу .NET, имеет смысл реализовать наш класс таким образом, чтобы его поведение было похоже на поведение встроенных коллекций. Самый простой способ сделать это — реализовать интерфейс ICollection<T>. Заметьте, что мы реализуем ICollection<T>, а не Ilist<T>, поскольку интерфейс Ilist<T> позволяет получать доступ к элементам по индексу. Несмотря на то, что произвольный доступ к элементам в целом полезен, его невозможно эффективно реализовать в связном списке.

Учитывая все вышесказанное, давайте набросаем примерный план класса, а затем заполним недостающие методы.

Метод Add

  • Поведение: Добавляет элемент в конец списка.
  • Сложность: O(1)

Добавление элемента в связный список производится в три этапа:

  1. Создать экземпляр класса LinkedListNode.
  2. Найти последний узел списка.
  3. Установить значение поля Next последнего узла списка так, чтобы оно указывало на созданный узел.

Основная сложность заключается в том, чтобы найти последний узел списка. Можно сделать это двумя способами. Первый — сохранять указатель на первый узел списка и перебирать узлы, пока не дойдем до последнего. В этом случае нам не требуется сохранять указатель на последний узел, что позволяет использовать меньше памяти (в зависимости от размера указателя на вашей платформе), но требует прохода по всему списку при каждом добавлении узла. Это значит, что метод Add займет O(n) времени.

Второй метод заключается в сохранении указателя на последний узел списка, и тогда при добавлении нового узла мы поменяем указатель так, чтобы он указывал на новый узел. Этот способ предпочтительней, поскольку выполняется за O(1) времени.

Первое, что нам необходимо сделать — добавить два приватных поля в класс LinkedList: ссылки на первый (head) и последний (tail) узлы.

Теперь мы можем добавить метод, который выполняет три необходимых шага.

Сначала мы создаем экземпляр класса LinkedListNode. Затем проверяем, является ли список пустым. Если список пуст, мы просто устанавливаем значения полей _head и _tail так, чтобы они указывали на новый узел. Этот узел в данном случае будет являться одновременно и первым, и последним в списке. Если список не пуст, узел добавляется в конец списка, а поле _tail теперь указывает на новый конец списка.

Поле Count инкрементируется при добавлении узла для того, чтобы сохранялся контракт интерфейса ICollection<T>. Поле Count возвращает точное количество элементов списка.

Метод Remove

  • Поведение: Удаляет первый элемент списка со значением, равным переданному. Возвращает true, если элемент был удален и false в противном случае.
  • Сложность: O(n)

Прежде чем разбирать метод Remove, давайте посмотрим, чего мы хотим добиться. На следующем рисунке список с четырьмя элементами. Мы удаляем элемент со значением «3».

data_structures_003

После удаления узла поле Next узла со значением «2» будет указывать на узел со значением «4».

data_structures_004

Основной алгоритм удаления элемента такой:

  1. Найти узел, который необходимо удалить.
  2. Изменить значение поля Next предыдущего узла так, чтобы оно указывало на узел, следующий за удаляемым.

Как всегда, основная проблема кроется в мелочах. Вот некоторые из случаев, которые необходимо предусмотреть:

  • Список может быть пустым, или значение, которое мы передаем в метод может не присутствовать в списке. В этом случает список останется без изменений.
  • Удаляемый узел может быть единственным в списке. В этом случае мы установим значения полей _head и _tail равными null.
  • Удаляемый узел будет в начале списка. В этом случае мы записываем в _head ссылку на следующий узел.
  • Удаляемый узел будет в середине списка.
  • Удаляемый узел будет в конце списка. В этом случае мы записываем в _tail ссылку на предпоследний узел, а в его поле Next записываем null.
Поле Count декрементируется при удалении узла.

Метод Contains

  • Поведение: Возвращает true или false в зависимости от того, присутствует ли искомый элемент в списке.
  • Сложность: O(n)

Метод Contains достаточно простой. Он просматривает каждый элемент списка, от первого до последнего, и возвращает true как только найдет узел, чье значение равно переданному параметру. Если такой узел не найден, и метод дошел до конца списка, то возвращается false.

Метод GetEnumerator

  • Поведение: Возвращает экземпляр IEnumerator, который позволяет итерироваться по элементам списка.
  • Сложность: Получение итератора — O(1). Проход по всем элементам — O(n).

Возвращаемый итератор проходит по всему списку от первого до последнего узла и возвращает значение каждого элемента с помощью ключевого слова yield.

Метод Clear

  • Поведение: Удаляет все элементы из списка.
  • Сложность: O(1)

Метод Clear просто устанавливает значения полей _head и _tail равными null. Поскольку C# — язык с автоматическим управлением памятью, нет необходимости явно удалять неиспользуемые узлы. Клиент, вызывающий метод, должен убедиться в корректном удалении значений узлов, если это необходимо.

Метод CopyTo

  • Поведение: Копирует содержимое списка в указанный массив, начиная с указанного индекса.
  • Сложность: O(n)

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

Метод Count

  • Поведение: Возвращает количество элементов списка. Возвращает 0, если список пустой.
  • Сложность: O(1)

Count — поле с публичным геттером и приватным сеттером. Изменение его значения осуществляется в методах Add, Remove и Clear.

Метод IsReadOnly

  • Поведение: Возвращает false, если список только для чтения.
  • Сложность: O(1)

Двусвязный список

Связный список, который мы только что создали, называется также «односвязным». Это значит, что между узлами только одна связь в единственном направлении от первого узла к последнему. Есть также достаточно распространенный вариант списка, который предоставляет доступ к обоим концам — двусвязный список.

Для того, чтобы создать двусвязный список, мы должны добавить в класс LinkedListNode поле Previous, которое будет содержать ссылку на предыдущий элемент списка.

data_structures_005

Далее мы рассмотрим только отличия в реализации односвязного и двусвязного списка.

Класс Node

Единственное изменение, которое надо внести в класс LinkedListNode — добавить поле со ссылкой на предыдущий узел.

Метод AddFirst

В то время, как односвязный список позволяет добавлять элементы только в конец, используя двусвязный список мы можем добавлять элементы как в начало, так и в конец, с помощью методов AddFirst и AddLast соответственно. Метод ICollection<T>.Add будет вызывать AddLast для совместимости с односвязным списком.

  • Поведение: Добавляет переданный элемент в начало списка.
  • Сложность: O(1)

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

  1. Установить значение поля Next в новом узле так, чтобы оно указывало на бывшый первый узел.
  2. Установить значение поля Previous в бывшем первом узле так, чтобы оно указывало на новый узел.
  3. Обновить поле _tail при необходимости и инкрементировать поле Count

Метод AddLast

  • Поведение: Добавляет переданный элемент в конец списка.
  • Сложность: O(1)

Добавление узла в конец списка легче, чем в начало. Мы просто создаем новый узел и обновляем поля _head и _tail, а затем инкрементируем поле Count.

Как было сказано ранее, ICollection<T>.Add просто зовет AddLast.

Метод RemoveFirst

Как и метод Add, Remove будет разделен на два метода, позволяющих удалять элементы из начала и из конца списка. Метод ICollection<T>.Remove будет также удалять элементы из начала, но теперь будет еще обновлять поля Previous в тех узлах, где это необходимо.

  • Поведение: Удаляет первый элемент списка. Если список пуст, не делает ничего. Возвращает true, если элемент был удален и false в противном случае.
  • Сложность: O(1)

RemoveFirst устанавливает ссылку head на второй узел списка и обнуляет поле Previous этого узла, удаляя таким образом все ссылки на предыдущий первый узел. Если список был пуст или содержал только один элемент, то поля _head и _tail становятся равны null.

Метод RemoveLast

  • Поведение: Удаляет последний элемент списка. Если список пуст, не делает ничего. Возвращает true, если элемент был удален и false в противном случае.
  • Сложность: O(1)

RemoveLast устанавливает значение поля _tail так, чтобы оно указывало на предпоследний элемент списка и, таким образом, удаляет последний элемент. Если список был пустым, или содержал только один элемент, то поля _head и _tail становятся равны null.

Метод Remove

  • Поведение: Удаляет первый элемент списка со значением, равным переданному. Возвращает true, если элемент был удален и false в противном случае.
  • Сложность: O(n)

Метод ICollection<T>.Remove() почти такой же, как и в односвязном списке. Единственное отличие — теперь нам необходимо поменять значение поля Previous при удалении узла. Для того, чтобы не повторять код, этот метод зовет RemoveFirst при удалении первого узла.

Зачем нужен двусвязный список?

Итак, мы можем добавлять элементы в начало списка и в его конец. Что нам это дает? В том виде, в котором он реализован сейчас, нет особых преимуществ перед обычным односвязным списком. Но если добавить геттеры для полей head и tail, пользователь нашего списка сможет реализовать множество различных алгоритмов.

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

В этом примере мы используем поля Tail и Previous для того, чтобы обойти список задом наперед.

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

Продолжение следует

На этом мы заканчиваем разбор связных списков. В следующий раз мы подробно разберем строение векторов (array list).

Перевод статьи «The Linked List»