Я впервые изучаю структуры данных. Для меня некоторые преимущества, традиционно описанные в связанных списках (более легкое распределение памяти и более быстрый ввод и удаление в тело списка) кажутся спорными в js, учитывая способ работы массивов (например, объекты с пронумерованными клавишами).
Может ли кто-нибудь привести пример того, почему я хотел бы использовать связанный список в javascript?
В качестве примечания к комментариям вы сделаете это, если вам потребуется постоянная вставка/удаление времени из списка.
Существует два пути Array, которые могут быть разумно реализованы, что позволяет заполнять несмежные индексы:
length говорит, что это не важно).В любом случае стоимость вставки в конце будет амортизирована O(1), но с пиками O(n) будет выполняться всякий раз, когда исчерпана емкость базового C-подобного массива (или порога хэш-нагрузки превышено) и требуется перераспределение.
Если вы вставляете в начале или посередине (и используется этот индекс), у вас есть те же возможные всплески работы, что и раньше, и новые проблемы. Нет, данные для существующих индексов не изменяются. Но все ключи выше введенной вами позиции должны быть увеличены (фактически или логически). Если это простая реализация C-подобного массива, это в основном просто memmove (по модулю потребностей сборщиков мусора и т.п.). Если это реализация хеш-таблицы, вам нужно по существу прочитать каждый элемент (от самого высокого индекса до самого низкого, что означает либо сортировку ключей, либо поиск каждого индекса ниже текущей длины, даже если это разреженный Array), pop его и снова вставьте его с ключевым значением, которое является одним выше. Для больших Array стоимость может быть огромной. Возможно, реализация в некоторых браузерах может сделать какую-то хитроумную бессмыслицу, используя "смещение", которое внутренне использует отрицательные "ключи" относительно смещения, чтобы избежать перефразировки, все еще вставляя перед индексом 0, но это сделало бы все операции более дорогой в обмен на то, чтобы сделать shift/unshift более дешевым.
Точка, связанный список, написанный на JavaScript, повлечет за собой накладные расходы за то, что он JS (который обычно работает медленнее, чем встроенные для подобной работы с магнитудой). Но (игнорируя возможность того, что менеджер памяти сам вводит рабочие пики), он предсказуем:
shift/unshift в вашей реализации браузера (с ними shift обычно будет дешевым, а unshift дешево, пока вы не достигнете unshift -ed больше, чем у вас shift -ed), тогда вы обязательно захотите использовать связанный список при работе с очередью FIFO потенциально неограниченного размера.Вполне возможно, что все браузеры используют смещения для оптимизации (избегая memmove или повторной клавиатуры при определенных условиях, хотя он не может избежать случайных realloc и memmove или переименования без потери памяти). Я не знаю, как это делают основные браузеры, но если вы пытаетесь написать переносимый код с постоянной производительностью, вы, вероятно, не хотите предполагать, что они пожертвовали общей производительностью, чтобы сделать shift/unshift быстрее с огромными Array s, возможно, они предпочли бы сделать все остальные операции более быстрыми, и предполагается, что shift/unshift будет использоваться только с небольшим Array, где стоимость тривиальна.
Я думаю, что есть некоторые законные случаи/причины, чтобы предпочесть связанные списки:
Причина 1: Как уже было описано, операции вставки и удаления выполняются в O (1) время для связанных списков. Это может быть значительным преимуществом в зависимости от вашей проблемы.
Причина 2: Вы можете делать что-то со связанными списками, которые нельзя делать с массивами. Это связано с природой связанного списка → в каждой записи списка есть ссылки на его последователя (и прецеператор, если это двойной связанный список).
Пример1:
Итак, если у вас есть связанный список элементов, то ку может хранить ссылку на "currentItem" в переменной. Если вам нужно получить доступ к соседи по элементам, вы можете просто написать:
curItem.getNext();
или
curItem.getPrev();
Теперь вы можете утверждать, что вы можете сделать то же самое с массивами, в то время как curItem является только текущим индексом. В принципе это верно (и в большинстве случаев я бы это использовал), но помните, что в javascript можно пропустить индексы. Поэтому, если ваш массив выглядит так, индексный метод не будет работать так же легко, как думал:
myArray = [];
myArray[10] = 'a';
myArray[20] = 'b';
Если вы окажетесь в такой ситуации, возможно, связанный ist - лучший выбор.
Однако, если вам нужен произвольный доступ к данным (что более редко, чем кажется в большинстве случаев), вы будете обращаться к массивам почти каждый раз.
Пример 2:
Если вы хотите "разбить" ваш список на 2 отдельных списка, это также будет возможно O (1) раз. С массивами вам нужно будет использовать срез, который является более неустойчивым. Однако это только проблема, если вы работаете с большими наборами данных и часто выполняете эту операцию. 20 повторений нарезки массива из 10 миллионов строк заняли около 4 секунд на моей машине, тогда как разделение одного списка на 2 заняло менее 1 секунды (при условии, что у вас уже есть ссылка на элемент списка, в котором вы хотите начать разделение конечно!).
Вывод:
В некоторых случаях вам будет полезен характер списка и его производительность. В некоторых случаях вы будете страдать от этого неспособности (невозможность случайного доступа к нескольким данным). Я никогда не использовал список в javascript, но аналогичные структуры, такие как деревья или графики, используются для представления данных (как в бэкэнд, так и в интерфейсе javascript). Таким образом, анализ/реализация списков в javascript - хорошая идея для более сложных структур.
@noob-in-need Я рекомендую вам посмотреть это видео о сборщике мусора JavaScript: https://www.youtube.com/watch?v=RWmzxyMf2cE
В нем он объясняет, почему использование связанного списка может дать вам более тонкий контроль над скоростью вашего кода (как подробно обсуждает ShadowRanger), а также предотвратить неожиданные замедления сбора мусора. Плюс это было снято на ток-а-пиратском дне.:)
Это сводится к самым основным различиям array vs linkedlist.
next.