Когда вы впервые узнаете о структурах данных, вы, вероятно, столкнулись с чем-то, что называется связанным списком. Что такое связанный список? Что ж, может быть полезно провести сравнение со структурой данных, с которой вы, вероятно, знакомы, с массивом. Как и массив, связанные списки хранят данные в «узлах», которые представляют собой отдельные элементы, составляющие связанный список. Однако каждый «узел» имеет следующее свойство, которое указывает на следующий «узел» внутри связанного списка. Первый узел в связанном списке называется заголовком, а последний узел в связанном списке - хвостом.

Какие преимущества имеет связанный список перед массивами? Одно из самых больших преимуществ связанного списка - это быстрые операции, которые могут выполняться на концах (голова и хвост). Если вы знакомы с большой нотацией O, добавление элементов в начало и конец связного списка является операцией O (1). Это означает, что эти операции всегда будут выполняться за постоянное время; не имеет значения, насколько велик связанный список. Теперь, если вы думаете о добавлении элемента в начало массива или даже в середину, вам придется «переместить» все элементы, которые идут после этого индекса.

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

Одним из недостатков связного списка является медленное время поиска. В отличие от массива, к узлу нельзя получить доступ по «индексу». Вам придется пройти весь связанный список, пока не дойдете до желаемого элемента. Операция поиска для связанного списка - O (n) или линейное время, что означает, что она зависит от размера связанного списка.

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

Создание класса узла и связанного списка

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

Теперь, когда у нас есть узел, давайте построим каркас связанного списка. В нашей реализации у нас будет только свойство head для нашего связанного списка, которое указывает на первый узел в связанном списке, но вы можете попробовать реализовать свойство tail. Наш класс связанного списка изначально будет принимать аргумент о том, что мы должны установить в качестве заголовка. Если у вас есть глава связанного списка, у вас, по сути, есть весь связанный список. Почему? Все узлы связаны следующим свойством. Заголовок указывает на следующий узел в списке, следующий узел указывает на следующий узел в списке и так далее.

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

Найдите размер нашего связанного списка

Один очень полезный метод, который может нам понадобиться, - это узнать, сколько узлов у нас есть в нашем связанном списке. Чтобы реализовать этот метод, мы можем инициировать переменную с именем node и переменную counter. Затем мы можем пройти по связанному списку и увеличивать counter, пока не будет «следующего» узла или node.next === null.

Получить первый и последний элемент связанного списка

Теперь давайте напишем два новых метода: один для получения первого узла в связанном списке, а другой для получения последнего узла. Какой элемент в связанном списке первый? Да, вы правы, вот бы голова. Получить последний элемент немного сложнее. Мы могли бы реализовать очень похожий подход к методу размера. Однако вместо этого наше условие цикла while изменится на node.next. Это потому, что мы хотим, чтобы node остановился на последнем узле связанного списка. Если мы установим условие цикла while равным node, нашим окончательным значением для node всегда будет null.

Вставить элемент в первую и последнюю позицию

Затем давайте реализуем метод для вставки узла в первую позицию и метод в узел в последней позиции связанного списка. Для метода insertFirst мы принимаем аргумент данных для создания нового узла. Затем мы установим этот новый узел в качестве нового заголовка и установим следующее свойство для предыдущего заголовка связанного списка.

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

Вставка и удаление элемента в определенной позиции

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

Когда у нас есть метод getAt, мы можем использовать его для реализации двух других наших методов. Для метода insertAt мы получим узел прямо перед индексом, в который хотим вставить. Таким образом, мы можем установить свойство next этого предыдущего узла на новый узел. Затем для свойства нового узла next будет установлено значение, которое раньше было next предыдущего узла. Мы также должны учитывать крайние случаи, например, если указанный индекс находится за пределами границ.

Метод removeAt имеет ту же идею, что и метод insertAt, но теперь мы удаляем следующий узел, устанавливая свойство next предыдущего узла на два узла впереди или prev.next.next. У нас есть возможность объединять следующие вызовы в цепочку таким образом. Теперь ничего не указывает на узел prev.next, поэтому он, по сути, «удален» из связанного списка.

Последние мысли

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

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

Https://www.udemy.com/course/coding-interview-bootcamp-algorithms-and-data-structure/