Что такое связанный список? Как составить связанный список. Зачем использовать его вместо массива?

Во-первых, что такое связанный список?

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

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

Есть разные типы связанных списков.

  • Односвязный список. Он состоит из узлов и элемента, указывающего на следующий узел. Часто вы также видите, что они определены с headelement.

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

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

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

Один недостаток в том, что нам нужно выполнить дополнительное кодирование

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

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

У нас есть класс Node и класс SinglyLinkedList… теперь. Как добавить узлы в SinglyLInkedList? Пришло время представить некоторые методы для класса singlyLinkedList.

Нажмите и сдвиньте его

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

Во-первых, давайте создадим push (), чтобы добавить узлы в наш связанный список.

Во-вторых, мы создадим наш метод Shift () для удаления узлов из начала списка.

Итак, наш полный класс выглядит так.

Теперь мы можем перемещать и перемещать узлы из нашего связанного списка.

Где это может быть полезно?

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

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

Вам не нужно беспокоиться о переиндексации.

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

Это намного эффективнее для вставки элементов.

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

Это отличный тип данных для очереди, особенно в порядке очереди (FIFO).

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

Итак, это конец, почему вы должны использовать связанный список вместо массива. Мы определили, что такое связанный список. Как создать его на JavaScript. Затем обсудили преимущества этого перед массивом. Удачного кодирования.