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

Обзор

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

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

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

Есть несколько других типов связанных списков, и они следующие:

Двусвязный список

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

Круговой связанный список

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

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

Вставка:

  • Вставьте новый узел перед головой
  • Вставьте новый узел после хвоста
  • Вставить новый узел в середину списка

Удаление:

  • Удаление головного узла
  • Удаление хвостового узла
  • Удаление узла из середины списка

Обход:

  • Обход связанного списка требуется для доступа к любому значению не в начале или в конце списка (например, вставка или удаление в середине списка, поиски.

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

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

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

Недостатки связанных списков

  • Использование памяти: связанные списки используют больше памяти по сравнению с массивом, хранящим те же точки данных, из-за того, что указатели на следующий элемент должны храниться для каждого узла.
  • Обход: Обход связанного списка является дорогостоящим, но равен сложности времени обхода массива O (n). Однако прямой доступ к элементу недоступен, как в массиве, через его индекс. Чтобы получить доступ к узлу в позиции n, необходимо пройти все узлы до него. Второй момент обхода связанного списка заключается в том, что обратный обход невозможен в односвязном списке. Двусвязный список требуется для перехода назад к голове по предыдущему указателю. Это также усугубляет проблему использования памяти из-за того, что каждый узел теперь требует хранения второго указателя.
  • Доступ к элементам: как указано в недостатке обхода. Случайный доступ через постоянное время O(1) невозможен. Это связано с его динамическим выделением памяти во время выполнения. В случае массива этот массив присваивается переменной, которая ссылается на непрерывный набор адресов памяти, присваиваемый ему, поэтому все эти адреса могут быть известны и доступны через ссылку на переменную массива и индекс напрямую. В качестве простого примера представьте, что массив имеет длину 6 и присваивается переменной x. Переменная x будет ссылаться на непрерывный набор адресов памяти, начиная с 200 и заканчивая 205. Следовательно, тогда доступ к x[0] относится к 200, а x[1] к доступу к 200 +3 = 203, и нам не нужно проходить через каждый индекс один за другим. В случае связанного списка адреса не являются последовательными и могут быть где угодно. Как видно из приведенного ниже примера, к каждому узлу необходимо получить доступ, чтобы узнать адрес следующего узла через его следующий указатель.

Следует отметить важную информацию о распределении памяти. В низкоуровневых языках, таких как C, памятью приходится управлять вручную. Однако JavaScript управляет этим за нас, выделяя память и освобождая ее с помощью сборки мусора, когда она больше не используется. Несмотря на то, что нам не нужно писать код, чтобы управлять этим напрямую, это происходит за кулисами и увеличивает время выполнения вашего кода. Что это значит для вас? Это означает, что даже если вы проанализируете свой код и обнаружите одинаковую временную сложность между использованием двух разных структур данных, фактическая эффективность может сильно различаться.

Что? Как мне это использовать?

Хорошо, теперь у нас есть некоторая информация о связанных списках. По крайней мере, достаточно информации, чтобы быть опасным. Как на самом деле выглядит связанный список в JavaScript? Односвязный список в JavaScript выглядит примерно так:

Так как же нам реализовать связанный список? Нам понадобятся некоторые узлы, содержащие наши данные и указатели, и нам понадобится список. Узел может быть определен как класс с конструктором, который имеет два элемента: данные и указатель. Нам также понадобится класс для LinkedList, у которого есть конструктор, который инициализирует первый узел и указывает на ноль.

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

Дополнительные примеры кода, подобные перечисленным выше, и способы создания вспомогательных методов для выполнения операций в вашем связанном списке см. на странице www.freecodecamp.org/news/implementing-a-linked-list-in-javascript.

Заключительные мысли

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

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

Или музыкальный плейлист, использующий двусвязный список, предложенный Кристофером Уэббом в этой статье. https://medium.com/journey-of-one-thousand-apps/data-structures-in-the-real-world-508f5968545a

Ссылки/Ресурсы

Структура данных связанного списка www.geeksforgeeks.org. 31 августа 2018 г.

Представления связанных списков www.tutorialspoint.com

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Memory_Management

https://www.toolsqa.com/data-structures/linked-list-in-data-structures/

https://codeburst.io/linked-lists-in-javascript-es6-code-part-1-6dd349c3dcc3

https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/