Что такое структура данных? Это способ хранения и организации данных в памяти. Различные структуры данных (например, массивы, стеки, очереди и т. д.) организуют данные по-разному. Сегодня вы рассмотрите связанные списки с точки зрения временной и пространственной сложности вместе с примером.
Связанные списки — это линейная структура данных или набор значений, в котором все они хранятся последовательно. Они более эффективны по сравнению с массивами, когда речь идет о вставке и удалении O (1) по сравнению с O (n) временной сложностью. Неэффективность массивов заключается в смещении элементов после вставки или удаления, таким образом, O (n). С точки зрения пространственной сложности хранилище занято в памяти для массивов независимо от того, содержат они элементы или нет. При добавлении в конец массива и достижении емкости пространство удваивается с новым массивом и значениями, скопированными из существующего массива. Для связанных списков пространственная сложность также равна O(n) из-за того, что вам нужно отслеживать дополнительные указатели, которые занимают место.
Давайте теперь посмотрим на код. Чтобы создать структуру данных связанного списка целых чисел, это может выглядеть так:
В связанном списке у вас есть ссылка на следующий узел и значение для текущего узла.
Чтобы вставить данные в ListNode, вы можете сделать следующее:
В приведенном выше примере вы создаете два списка: list1
и list2
. Рекомендуется проверить, правильно ли вы вставили элементы. Итак, давайте сделаем это. Недавно я научился аккуратному способу вывода значений в связанном списке из книги Кевина Лау и Винсента Нго Структуры данных и алгоритмы в Swift. Давайте перейдем к коду, а затем я объясню, что мы сделали после.
В приведенном выше коде вы сначала соответствуете протоколу CustomStringCovertible
, а затем реализуете описание. Реализация описания использует интерполяцию строк для печати значения узла и значения следующего узла. Поэтому, когда вы передаете ListNode
инициализатору String(describing:)
, функция print(_:)
будет использовать значение, возвращаемое description
. Глядя на приведенный выше пример, списки печатаются следующим образом:
Давайте расширим пример и объединим два списка в один отсортированный список. Можно предположить, что каждый список отсортирован. Есть 3 случая, которые вы будете обрабатывать:
- Разное количество элементов в двух списках
- Одинаковые значения в списках
- Разные значения в списках
Одно решение может выглядеть так:
Вот что происходит:
Вы создадите временные узлы для ссылки на два отсортированных списка и выполните следующие действия:
- Вы будете перебирать список до тех пор, пока любой из них содержит значение или не равен нулю.
- Если узел во втором списке нулевой, вы будете использовать
insertNode
функцию для вставки узла из первого списка в результирующий связанный списокheadNode
Вы увидите, какinsertNode
реализуется позже. Вы переместите временный указатель на следующий элемент в первом списке. - Повторите проверку, аналогичную шагу 2, но для узла в первом списке и переместите временный указатель на следующий элемент во втором списке.
- else проверит, когда оба элемента не равны нулю
- Если оба значения в списках равны друг другу, то вы вставляете их оба в результирующий связанный список и продвигаете оба временных указателя на следующий узел.
- Если узел в первом списке меньше узла во втором списке, вы вставляете узел из первого списка и перемещаете временный указатель на следующий узел.
- Вы делаете обратное, когда вместо этого узел во втором списке меньше.
Функция insertNode
показана ниже:
Логика insertNode
состоит из двух частей:
headNode
указывает на главный элемент результирующего связанного списка. Поэтому, если он равен нулю, вы создадите новый узел с заданным значением для вставки в результирующий связанный список.currentNode
будет указывать на текущий узел, когда вы вставляете каждый новый узел.- Если
headNode
содержит узел или не равно нулю, новый узел с заданным значением создается и вставляется в качестве следующего узла результирующего связанного списка. Вы продвигаете ссылкуcurrentNode
к следующему узлу.
В целом вставка выполняется за O(1) за постоянное время. Это достигается путем отслеживания недавно вставленного узла. И последнее, но не менее важное: вот напечатанное решение объединенного списка:
Куда пойти отсюда?
Изучите другие темы в книге Кевина Лау и Винсента Нго Структуры данных и алгоритмы в Swift.