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

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

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

Некоторые теоретические знания

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

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

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

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

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

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

Связанные списки более эффективны в этой ситуации. Добавление элемента в любом месте списка потребует только изменения указателей. Удаление также является быстрой операцией, которая также освобождает память, выделенную для конкретного элемента. Если на него нет ссылок, он будет обработан сборщиком мусора.

Реализация связанного списка

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

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

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

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

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

Возможная ошибка - забыть увеличить свойство length, что приведет к установке нового указателя заголовка каждый раз.

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

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

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

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

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

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

На что следует обратить внимание, это случай, когда удаляемый узел является головкой. Также не забудьте изменить свойство длины.

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

Другие виды связанных списков

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

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

Что дальше?

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