Эта статья была опубликована на платформе WeChat: Programmer Interviewer
«Предварительное интервью и расширенное руководство», содержащее более 20 слов, можно переместить.github
Для многих разработчиков структура данных связанного списка одновременно и знакома, и незнакома. Знакомство связано с тем, что это действительно очень простая структура данных. Незнакомая причина заключается в том, что мы не используем ее в развитии бизнеса.
Во многих случаях мы можем использовать массивы, чтобы хорошо выполнять работу, не делая слишком много различий, так в чем смысл существования связанных списков? Есть ли какие-либо преимущества или недостатки связанных списков по сравнению с массивами?
Что такое связанный список
Связный список — это общая базовая структура данных, линейный список, но он не хранит данные в линейном порядке, а хранит в каждом узле указатель (Pointer) на следующий узел.
По сути, связанные списки и массивы имеют сходство. Их сходство заключается в том, что они являются линейными структурами данных, которые отличаются от деревьев и графов. Разница между ними заключается в том, что массив является непрерывным фрагментом памяти, а связанный список может не be В непрерывной памяти узлы связанного списка связаны указателями.
Конечно, связанные списки также имеют различные формы, в основном разделенные на три типа: односвязные списки, двусвязные списки и круговые связанные списки.
Односвязный список
Узел односвязного списка обычно состоит из двух частей, одна из которых представляет собой значение, хранящееся в узле.val, другой указатель на узелnext.
Подобно массивам, связанные списки также могут выполнять такие операции, как поиск, вставка, удаление и чтение, но из-за различных характеристик связанных списков и массивов сложность различных операций также различна.
Найти производительность
Операция поиска односвязного списка обычно выглядит следующим образом:
- Зайти с головного узла, начать сравнивать значение узла, если оно отличается, войти в следующий узел через указатель
- Повторяйте вышеуказанные действия до тех пор, пока не будет найдено такое же значение или указатель узла не укажет на ноль.
Производительность поиска в связанном списке такая же, как и в массиве, а временная сложность — O(n).
Вставить удалить производительность
Самая большая разница между связанным списком и массивом заключается в преимуществе удаления и вставки в производительности.Поскольку связанный список представляет собой несмежную память, нет необходимости выполнять смещения членов большой области при вставке и удалении операций, таких как массив, например, между узлами a и b. Чтобы вставить новый узел c, связанному списку нужно только:
- a разбивает указатель на b и указывает указатель на c
- Узел c указывает указатель на b, завершено
Эта операция вставки требует только перемещения указателя, а временная сложность вставки и удаления составляет всего O(1).
Операция вставки связанного списка выглядит следующим образом:
Операция удаления связанного списка выглядит следующим образом:
производительность чтения
Связанный список также имеет недостатки по сравнению с ним, то есть операция чтения намного уступает операции чтения массива Причина, по которой операция чтения массива эффективна, заключается в том, что это непрерывная память, и чтение массива может можно быстро найти по формуле адресации Непрерывная память, поэтому ее нужно проходить узел за узлом с помощью указателя.
Например, для массива мы хотим прочитать третий член, нам нужно толькоarr[2]Члены могут быть получены быстро, в то время как связанный список нужно вводить с головного узла, а прочитать его можно только после входа в последующие узлы через указатель.
Сценарии применения
Из-за существования двусвязного списка сценариев применения односвязного списка относительно немного, потому что многие сценарии двусвязного списка можно реализовать лучше.
Но односвязные списки не бесполезны, и односвязные списки по-прежнему используются в следующих сценариях:
- Функция отмены, этот тип операции наиболее распространен в различных текстовых и графических редакторах, отмена и повтор действия являются обычными в сцене редактора, односвязный список очень подходит для этой сцены из-за его хороших характеристик удаления
- Реализовать некоторые расширенные структуры данных, такие как граф и хэш-карта.
Двусвязный список
Как мы упоминали выше, существует не так много сценариев применения односвязных списков, и тот, который действительно широко используется в производственной среде, — этоДвусвязный список.
Что особенного в двусвязном списке по сравнению с односвязным списком?
Мы видим, что в двусвязном списке появился новый указательprevУказывая на предыдущий узел узла, естественно, потому что там на один указатель больше, двусвязный список занимает больше памяти.
Не стоит недооценивать добавление предварительного указателя к двусвязному списку: во многих сценариях это более эффективно и практично благодаря добавлению этого указателя.
Например, для операции "отменить/повторить" редактора больше подходит двусвязный список. Благодаря переднему и заднему указателям пользователь может свободно выполнять передние и задние операции. Если это односвязный список, то пользователю необходимо пройти по связанному списку.Временная сложность в настоящее время составляет O (n).
Структуры данных и шаблоны проектирования, используемые редакторами в реальных приложениях производственного уровня, более сложны.Например, Word использует структуру данных Piece Table и шаблон очереди команд для реализации «отменить/повторить», но это нечто другое.
Круговой связанный список
Циклический связанный список, как следует из названия, указывает хвостовой указатель односвязного списка на головной узел связанного списка:
Сценарий применения кругового связанного списка — это проблема разделения времени операционной системы.Например, есть компьютер, но есть несколько пользователей, и ЦП может вытеснять ресурсы при обработке запросов от нескольких пользователей.В это время, компьютер примет стратегию разделения времени, чтобы обеспечить удобство работы каждого пользователя.
Каждый пользователь может рассматриваться как узел в круговом связанном списке, ЦП будет выделять определенное время обработки каждому узлу, переходить к следующему узлу после определенного времени обработки, а затем бесконечно зацикливаться, что может обеспечить работу каждого пользователя, без Возможна ситуация, когда один пользователь вытесняет ЦП, а другие пользователи не могут ответить.
Конечно, проблема кольца Джозефа является репрезентативным приложением однонаправленного кругового связанного списка, и те, кто заинтересован, могут узнать о нем больше.
Конечно, что, если двусвязный список является сквозным? Это двусвязный список.
В Node есть класс сценариев, запроса нет, но много вставок и удалений, это модуль Timer. Почти все сетевые запросы ввода-вывода будут обеспечивать операцию тайм-аута для контроля состояния тайм-аута сокета.Здесь setTimeout будет использоваться много, и большинство этих таймеров тайм-аута не используются (данные обычно отвечают вовремя), тогда будет большое количество операций clearTimeout в ответ, поэтому узел использует дважды циклический связанный список для повышения производительности модуля Timer, и детали не будут повторяться.
插入！
TimersList <-----> timer1 <-----> timer2 <-----> timer4 <-----> timer3 <-----> ......
1000ms后执行 1050ms后执行 1100ms后执行 1200ms后执行
резюме
До сих пор у нас есть определенное понимание структуры данных связанного списка.Из-за особенностей несмежной памяти связанный список очень подходит для частых сценариев вставки и удаления, но не подходит для сценариев чтения, которые дополняют друг друга. к характеристикам массивов. Итак, теперь мы можем вернуться к вопросу в заголовке. Характеристики связанного списка дополняют характеристики массива, и у каждого есть свои сильные стороны. Кроме того, связанный список может образовывать круговой связанный список из-за наличия указателя, который также очень полезен в определенных сценариях.Поэтому наличие связанного списка очень необходимо.
Итак, теперь есть очень распространенный вопрос, ориентированный на мышление, ориентированный на интервью:
Мини-программы WeChat, которые мы обычно используем, будут иметь самые последние использовавшиеся функции. Те, у которых самое последнее время, находятся вверху и будут расположены в хронологическом порядке. Когда используемые мини-программы больше определенного числа, наименее используемые мини-программы не появятся Теперь, как бы вы разработали этот алгоритм?