Original: http://antirez.com/news/138
Пару дней назад, в твиттере я говорил об очень плохой реализации связных списков, написанной на Rust. Из тонны определенных реплаев я понял думают о связном списке как о шутке. Тривиальная структура данных, которая только и хороша, что для coding interview, в других случаях бесполезна. Другим словом: bubble sort в мире структур данных. Я с этим не согласен, поэтому я думал написать этот блог пост, в котором есть описание того, что я люблю в связных списках.
Итак, приготовьтесь прочитать сентиментальный текст о структуре данных и потом не говорите, что я не предупреждал вас.
Связные списки образовательны. Когда ваш учитель или страница книги или что-либо еще что открыло вам в первый раз связный список показывают тебе этот маленький кружок со стрелкой, ссылающейся на другой кружок, что глобальное случается в твоей голове. Похожее на то, что случается, когда понимаешь рекурсию в первый раз. Вы понимаете чем на самом деле является структура данных сделанная из ссылок – тривиальность одного узла которая становится более мощной и сложной, когда он ссылается на другой узел. Связные списки показывают новым программистам фундаментальные вещи о пространстве и времени в вычислениях – как это возможно добавить элементы за константное время и как порядок фундаментально затратен, потому что если вы хотите вставить элемент "in place" вы должны пройтись от одного узла к другому. Вы незамедлительно начинаете думать о способе ускорить процесс (подготовка вас к следующему шагу), и, в тоже самое время вы понимаете, что O(1) и O(n) это действительно важные штуки.
Связный список дополняемый. Добавить указатель на предыдущий элемент и вот уже можно ходить в обе стороны. Добавить "far" указатели и у вас получился skip list с совершенно другими свойствами. Измените каждый узел, чтобы он содержал несколько элементов и ваш связный список станет развернутым, обеспечивающим различные возможности кеширования (1). Связный список может быть так же встроенным. В ядре линукс, например, есть макрос для добавления поля в любую структуру для того, чтобы связать их вместе. Еще связные списки компонуемые. Это важное свойство – вы можете разделить связные списки за O(1) и так же склеить их за O(1). Если вы будете использовать это свойство с умом, то можно делать интересные вещи. Например, так в Redis модулях реализуются операции в потоками. Обработка потока медленного запроса имело дело с фейковой структурой клиента. В этом случае нет блокировки, нет борьбы за ресурсы (contention). Когда команда, запущенная в потоке, закончит свое выполнение, буфер вывода клиента может быть склеен с настоящим буфером реального клиента. Это просто сделать, потому что выходной буфер был представлен как связный список.
Связные списки полезные структуры данных, потому что они напоминают естественные процессы – добавление элементов в том порядке, в котором они поступают или в обратном порядке – это естественно даже в физическом мире. Пошаговое извлечение элементов так же полезно, так как можно переместить элемент из головы в хвост или переместить его на определенную позицию после определенного элемента.
Связные списки простые. Это одна из тех редких структур данных, наряду с бинарными деревьями и хэш таблицами и некоторыми другими, которые вы можете реализовать просто из памяти не допуская больших ошибок.
Связные списки концептуальны. Узел, указывающий сам на себя – это наиболее эгоистичная вещь, которую я себе могу представить в вычислениях – идеальная репрезентация более вульгарного бесконечного цикла. Узел, указывающий на NULL – это метафора одиночества. Связный список с соединенным головой и хвостом – мощный символ замкнутого цикла.
По всем этим причинам, я люблю связные списки и надеюсь, что ты тоже, по крайней мере, начнешь им улыбаться ;).
