Поработав с массивами в предыдущем рассказе, на этот раз мы рассмотрим второй тип структуры данных в нашей серии — связанные списки.

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

# Что такое указатель?

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

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

# Что такое связанные списки?

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

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

Первый узел в связанном списке называется head и служит точкой входа. С другой стороны, последний узел указывает на null и часто называется «хвостом».

# односвязных и двусвязных списков

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

Однако в двусвязном списке каждый узел содержит, кроме данных, два указателя, один на следующий узел, а другой на предыдущий. Поэтому обход в двусвязном списке двунаправленный. Другими словами, из текущего узла nвы можете получить доступ к узлу n-1 (предыдущему)и узлу n+1 (далее).

# Зачем использовать связанные списки?

  1. Постоянное время вставки и удаления…

В отличие от массивов, временная сложность вставки и удаления в заданной точке связанного списка составляет O(1). Это не требует никакого смещения, нам просто нужно переключить указатели, и все готово.

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

2. Больше никакой потери памяти…

Тот факт, что расположение памяти для связанного списка выполняется несмежным образом, дает им преимущество перед массивами. Память выделяется динамически, когда это необходимо. Таким образом, нет места для потери памяти.

3. В основе других структур данных…

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

Связанные списки: реализация в JavaScript

В некоторых языках программирования реализованы встроенные связанные списки, в некоторых нет. В JavaScript нет такой вещи, как связанные списки, поэтому нам нужно реализовать их самостоятельно.

Давай сделаем это…

Я уверен, что вам не понадобится моя помощь, чтобы понять этот простой фрагмент кода — все равно воспользуйтесь разделом комментариев. Тем не менее, я хотел бы выделить кое-что, прежде чем мы закончим эту статью…

Если вы посмотрите на диаграмму временной сложности, которую мы видели раньше здесь, вы заметите, что она говорит о том, что временная сложность для вставки и удаления составляет O(1). Однако, если вы посмотрите на приведенный выше фрагмент кода, вы увидите, что insertAt() временная сложность составляет O(n). Как идет?

Следует четко различать, что в диаграмме они означают само действие вставки в заданную точку (указатель). Эквивалентом метода в нашем примере кода выше является метод insert().

И да! С массивами дело обстоит иначе, потому что для вставки в заданную позицию может потребоваться смещение массива. Вот почему временная сложность вставки и удаления в массивах составляет O(n).

Понятно? Прохладный.

Связанные списки: теперь ваша очередь…

# Задача 1

Используйте предпочитаемый язык программирования для реализации отсутствующего метода remove() в приведенном выше фрагменте кода.

# Задача 2

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

Подождите секунду, пожалуйста! Прежде чем мы уйдем, если хотите, давайте подключимся…