Что такое структура данных? Это способ хранения и организации данных в памяти. Различные структуры данных (например, массивы, стеки, очереди и т. д.) организуют данные по-разному. Сегодня вы рассмотрите связанные списки с точки зрения временной и пространственной сложности вместе с примером.

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

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

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

Чтобы вставить данные в ListNode, вы можете сделать следующее:

В приведенном выше примере вы создаете два списка: list1 и list2. Рекомендуется проверить, правильно ли вы вставили элементы. Итак, давайте сделаем это. Недавно я научился аккуратному способу вывода значений в связанном списке из книги Кевина Лау и Винсента Нго Структуры данных и алгоритмы в Swift. Давайте перейдем к коду, а затем я объясню, что мы сделали после.

В приведенном выше коде вы сначала соответствуете протоколу CustomStringCovertible, а затем реализуете описание. Реализация описания использует интерполяцию строк для печати значения узла и значения следующего узла. Поэтому, когда вы передаете ListNode инициализатору String(describing:), функция print(_:) будет использовать значение, возвращаемое description. Глядя на приведенный выше пример, списки печатаются следующим образом:

Давайте расширим пример и объединим два списка в один отсортированный список. Можно предположить, что каждый список отсортирован. Есть 3 случая, которые вы будете обрабатывать:

  1. Разное количество элементов в двух списках
  2. Одинаковые значения в списках
  3. Разные значения в списках

Одно решение может выглядеть так:

Вот что происходит:

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

  1. Вы будете перебирать список до тех пор, пока любой из них содержит значение или не равен нулю.
  2. Если узел во втором списке нулевой, вы будете использовать insertNodeфункцию для вставки узла из первого списка в результирующий связанный список headNode Вы увидите, как insertNode реализуется позже. Вы переместите временный указатель на следующий элемент в первом списке.
  3. Повторите проверку, аналогичную шагу 2, но для узла в первом списке и переместите временный указатель на следующий элемент во втором списке.
  4. else проверит, когда оба элемента не равны нулю
  5. Если оба значения в списках равны друг другу, то вы вставляете их оба в результирующий связанный список и продвигаете оба временных указателя на следующий узел.
  6. Если узел в первом списке меньше узла во втором списке, вы вставляете узел из первого списка и перемещаете временный указатель на следующий узел.
  7. Вы делаете обратное, когда вместо этого узел во втором списке меньше.

Функция insertNode показана ниже:

Логика insertNode состоит из двух частей:

  1. headNode указывает на главный элемент результирующего связанного списка. Поэтому, если он равен нулю, вы создадите новый узел с заданным значением для вставки в результирующий связанный список. currentNode будет указывать на текущий узел, когда вы вставляете каждый новый узел.
  2. Если headNode содержит узел или не равно нулю, новый узел с заданным значением создается и вставляется в качестве следующего узла результирующего связанного списка. Вы продвигаете ссылку currentNode к следующему узлу.

В целом вставка выполняется за O(1) за постоянное время. Это достигается путем отслеживания недавно вставленного узла. И последнее, но не менее важное: вот напечатанное решение объединенного списка:

Куда пойти отсюда?

Изучите другие темы в книге Кевина Лау и Винсента Нго Структуры данных и алгоритмы в Swift.