Вы отыграли свою долю имитационных интервью на YouTube и все еще думаете про себя: «Что, черт возьми, за связанный список? И почему MAMAA волнует, могу ли я это отменить?».

Ну, это именно то, на что они похожи: список. Вы, вероятно, лучше знакомы с массивами, когда дело доходит до хранения списка данных. Оказывается, все, что вы можете сделать с массивом, вы можете сделать и со связанным списком. Если это так, то почему вас должны волновать связанные списки и когда они превосходят массив? Прежде всего, давайте познакомимся со связанными списками.

Что, черт возьми, связанный список?

Связанные списки состоят из элементов или узлов, каждый из которых состоит из:

  • Данные: то, что нам важно
  • Ссылка: адрес, по которому мы можем найти следующий элемент

Первый элемент связанного списка называется head.

Существуют различные виды связанных списков:

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

Вы также можете иметь циклические односвязные списки и циклические двусвязные списки.

На данный момент вам не нужно запоминать различные типы — основная идея состоит в том, что они состоят из последовательных элементов, содержащих данные и ссылку на следующий элемент.

Обзор массивов

Теперь давайте поразмыслим о типах операций, которые мы можем выполнять с массивом.

  • Добавить элемент
  • Удалить элемент
  • Доступ к элементу

Есть еще несколько, но мы сосредоточимся на них сейчас.

Итак, если мы можем применить те же операции с массивом к связанному списку, зачем использовать связанный список? Ну, все сводится к распределению памяти и временной сложности. Чтобы понять, как каждая структура данных влияет на эти вещи, давайте посмотрим фильм.

В кино

Допустим, я хочу пригласить 20 друзей посмотреть новый фильм «Черная пантера» (представляете? На самом деле у меня не так много друзей). На случай, если все соберутся, я заранее покупаю остальные 20 билетов с зарезервированными местами. Ну, что вы знаете! Появляются только 6 моих «друзей». Билеты на шоу распроданы, 15 мест пусты, у меня нет 300 долларов, и мы выглядим как придурки.

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

Давайте пойдем немного дальше и рассмотрим временную сложность и нотацию большого O в отношении операций с массивами. Это наихудшие сценарии (например, работа с произвольно большими массивами):

  • Добавить/удалить элемент в конце массива (последний индекс): O(1)
  • Добавить/удалить элемент, который не находится в конце массива: O(n)
  • Доступ к элементу: O(1)

Сложность времени массива

В нашей аналогии мои покойные друзья сразу получили доступ к местам, потому что я их зарезервировал. В массивах вы можете получить доступ к любому элементу по его индексу за постоянное время O(1). Это связано с тем, что выполняемая операция представляет собой простую арифметику, а не итерацию. Когда мы создаем массив, у нас есть ссылка на 0-й индекс и размер (в байтах) одного элемента (спойлер: они все одного размера. Почему? Это не та статья). Операция выглядит следующим образом:

Адрес i-го индекса = Адрес 0-го индекса + i × (размер одного элемента)

К сожалению, у меня нет толковой аналогии добавления и удаления элементов, но вы только представьте, как тяжело было бы купить больше мест на уже распроданный кинопоказ. На самом деле здесь происходит то, что все элементы справа от этого добавления/удаления теперь должны быть смещены, и этим элементам назначается новый индекс. Это занимает линейное время O(n). Если ничего не находится справа от этого элемента, то есть конца массива, это занимает время O(1), потому что смещение не требуется.

Временная сложность связанного списка

Большой. Итак, что насчет связанных списков? В отличие от массивов, связанные списки не имеют индексов. Таким образом, чтобы получить доступ к произвольному элементу в связанном списке, вы начинаете с головы и проходите элемент за элементом, пока не найдете тот, который вам нужен. Это занимает линейное время O(n). Не волнуйся. Это не является преимуществом для связанных списков.

Настоящим преимуществом связанных списков является их способность вставлять и удалять элементы в постоянное время, O(1). Я полагаю, если бы мне все еще пришлось использовать аналогию с фильмом, просто представьте, что я покупаю одно место для аншлагового представления «Черная пантера» и выгоняю случайных людей всякий раз, когда появляется каждый из моих друзей.

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

По сути, массивы хранятся в памяти вместе, поэтому элементы смещаются при добавлении/удалении. Элементы в связанном списке хранятся в разбросанной памяти, поэтому элементы содержат адрес следующего элемента.

Когда вы хотите добавить/удалить элемент, вы просто переназначаете адрес элемента до того места, где мы хотим, чтобы произошло добавление или удаление. В случае двусвязного списка мы меняем «следующий» адрес предыдущего элемента и «предыдущий» адрес следующего элемента.

В этот момент вы, вероятно, задаетесь вопросом: «O(1) кажется немного обманчивым. Вам по-прежнему нужно пройтись по связанному списку, чтобы найти место, где вы хотите добавить/удалить что-то!». И знаете что? Ты так права, дружище.

Если у вас еще нет ссылки на это место, вся операция занимает O(n) времени. Однако, поскольку нам не нужно сдвигать элементы, это все же намного эффективнее, чем добавление/удаление в массивах.

Применение связанных списков и массивов

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

Массивы:

  • Когда вам нужно быстро получить доступ к произвольным элементам
  • Когда вы знаете, насколько большим может быть список

Связанные списки:

  • Когда вам нужно быстро добавить/удалить произвольные элементы
  • Когда вы не знаете, насколько большим может быть список

Итак, каковы реальные приложения связанных списков?

  1. Ваш лучший друг: ctrl/cmd + (shift +) z. Отмена или повторное выполнение действий.
  2. Кнопки назад и вперед в вашем любимом браузере.
  3. Ваше любимое приложение для потоковой передачи музыки. Следующая, предыдущая, добавление или удаление песен из очереди.

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

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

Ссылки и расширенные чтения: