Вы не используете связанные списки. Но они управляют половиной вашего ПО.

Скорее всего, вы никогда не будете писать связанные списки в реальных JavaScript-проектах. Встроенные массивы вашего языка справляются с динамическим изменением размера быстрее. Интервьюеры учат вас строить их на досках, но это формирует неверную ментальную модель.

Связанные списки не нужно учить ради того, чтобы их реализовывать. Их нужно учить, чтобы понимать инструменты, которыми вы пользуетесь каждый день.

Они повсюду: • Кнопки «Назад» и «Вперед» в браузере. • История отмены действий (undo) в текстовых редакторах. • LRU-кэши в веб-серверах и базах данных. • Команды списков в Redis. • Планировщик процессов в ядре Linux.

Это не пережитки прошлого. Это инфраструктура.

Настоящая причина, по которой связанные списки проигрывают, — это локальность кэша. Ваш процессор не читает оперативную память по одному байту за раз. Он подтягивает 64-байтовый блок, называемый кэш-линией.

Массивы работают быстро, потому что они расположены в памяти последовательно. Процессор считывает первый элемент и бесплатно получает следующие 15.

Связанные списки разрушают это преимущество. Каждый узел находится в отдельном месте памяти. Переход по указателю заставляет процессор прыгать на новый адрес. Это инициирует новый запрос к оперативной памяти, что стоит сотни циклов процессора.

На современном оборудовании обход массива может быть в 10–100 раз быстрее, чем обход связанного списка. Нотация Big-O игнорирует эту константную стоимость.

Так когда же их использовать?

Используйте односвязный список для стеков или простых очередей задач, где вы добавляете или удаляете элементы только с одного конца.

Используйте двусвязный список, когда вам нужно удаление за O(1) при наличии прямой ссылки на узел. В этом и заключается секрет LRU-кэша.

Для LRU-кэша требуются:

  • Поиск за O(1).
  • Вставка за O(1).
  • Вытеснение за O(1).
  • Продвижение (promotion) за O(1).

Массив не может этого сделать, так как перемещение элементов требует сдвига всех остальных. Одна лишь хеш-таблица не справится, потому что у нее нет порядка.

Решение — в комбинации. Хеш-таблица обеспечивает поиск. Двусвязный список поддерживает порядок. Хеш-таблица хранит ссылку на узел. Когда вы обращаетесь к ключу, вы извлекаете узел напрямую из списка и перемещаете его в начало. Никакого поиска. Никаких сдвигов.

Перестаньте учить структуры данных только ради прохождения интервью. Учите их, чтобы понимать, как программное обеспечение взаимодействует с оборудованием.

Источник: https://dev.to/islamhafez0/you-dont-use-linked-lists-but-theyre-running-half-your-software-4b37