Структура данных 1960-х годов все еще довольно крута.
Мы окружены списками как в реальном мире, так и в нашем коде. Многие языки (особенно функциональные) имеют их встроенные; у остальных будут библиотеки списков.
Список - это просто упорядоченная группа значений с динамическим размером. В большинстве реализаций подразумевается, что вставка и удаление в начале (и, возможно, в конце) списка относительно дешевы, а поиск в списке в худшем случае O (n).
Как мы реализуем списки? В некоторой степени это зависит от схем доступа. Если мы ищем больше, чем изменяем, то было бы неплохо реализовать список в виде дерева, где почти все операции амортизируются до O (log n).
Если наш список используется для реализации упорядоченной очереди (например, удержания задач, которые должны быть запущены в порядке приоритета), структура данных на основе кучи может быть подходящей.
Однако для многих целей предпочтительной реализацией является простой связанный список.
Базовый список выглядит так:
Переменная my_list указывает на первый узел в списке. Этот узел указывает на следующий, а узел в конце списка имеет какой-то нулевой указатель, чтобы указать, что больше нет
Добавить узел впереди довольно просто (предупреждение о спойлере: нет, это не так):
new_node = new Node(somePayload) new_node.next = my_list my_list = new_node
Удалить первый узел еще проще:
my_list = my_list.next
Но в этом есть большая проблема: если вы когда-нибудь передадите переменную my_list, то будет передан список на момент вызова функции: добавления и удаления не будут отражены.
Есть еще одна проблема с удалением: что будет, если список пуст? Вздох ... я думаю, время для нескольких if заявлений ...
if (my_list != null)
my_list = new_node
А давайте подумаем о добавлении и удалении в середине списка. В приведенном выше примере удаление узла с полезной нагрузкой 2 означает обновление предыдущего узла, чтобы он указывал на третий узел. Когда мы просматриваем список в поисках удаляемого узла, мы должны отслеживать предыдущий узел. И, угадайте, что у нас есть особый случай, если узел, который мы ищем, является первым узлом в списке.
Две ссылки лучше, чем одна
Мы можем решить проблему добавления и удаления в середине списка, добавив дополнительную ссылку: теперь каждый узел указывает как на узел, следующий за ним, так и на узел, который ему предшествует.
Теперь удаление среднего списка узлов:
nodeToDelete.prev.next = nodeToDelete.next nodeToDelete.next.prev = nodeToDelete.prev
С добавлением указателя конца списка его можно легко добавлять и удалять в конце. Но у нас все еще есть особые случаи при манипулировании первым и последним элементами.
Что происходит…
Вот где происходит волшебство. Давайте возьмем наш двусвязный список и превратим его в круг, соединив конец с началом. Но пока мы это делаем, мы собираемся добавить еще один узел. Назовем его ГОЛОВА.
Что такого особенного в этой структуре? Две вещи. Во-первых, указатель на голову всегда будет ссылаться на этот список, независимо от того, что мы вставляем и удаляем. И, во-вторых, нет особых случаев. Никто. Не имеет значения, каким узлом мы манипулируем: первым, последним или одним в середине, операции, которые мы выполняем, одинаковы.
Вот код, который удаляет узел перед данным узлом (мы увидим, почему я указываю следующий узел через минуту).
Если мы вызвали его для удаления узла перед полезной нагрузкой 3, мы установили бы следующий указатель полезной нагрузки 2 на полезную нагрузку 4, а предыдущий указатель на 4 - на 2.
Но что это удаляем payload 1? Раньше нам приходилось рассматривать это как частный случай. Но здесь мы просто настраиваем указатели в узле HEAD и узле 2, и список обновляется.
Добавить узел также просто:
На этот раз нам нужно настроить указатели в новом узле, а также следующий указатель в предыдущем узле и предыдущий указатель в следующем узле.
С учетом этих двух функций код для добавления и удаления узлов спереди (shift и unshift) и в конце (push и pop) является тривиальным:
В этом представлении пустой список - это список, содержащий головной узел. В этом случае указатели next и prev указывают на сам заголовок, а это означает, что все написанные нами обходы будут продолжать работать.
Я оставлю выполнение дополнительных функций, таких как list.contains(payload) и list.removeMatching(payload), на ваше усмотрение. Думаю, вы будете приятно удивлены их простотой.
Элегантный?
Впервые я наткнулся на двусвязный круговой список в колледже. Мы программировали симуляции в Simula 67, и встроенный класс SimSet реализует свои очереди таким образом.
Я почти забыл об этом на пять или более лет, пока не написал некоторые алгоритмы буферизации на ассемблере. Я был разочарован всей условной логикой и прыжками вокруг того, что делал код, поэтому я вырвал его и заменил круговым списком. Код был вдвое меньше и работал (почти) с первого раза.
На мой взгляд, элегантность заключается в добавлении фиктивного узла для представления заголовка списка. Это простое и простое дополнение имеет два важных эффекта:
- Это означает, что указатель на список всегда действителен, и
- Он удаляет все особые случаи в начале и в конце списка.
Такая экономия вызывает у меня улыбку.
Примечания:
- Код для этой статьи доступен на GitHub.
