В продолжение моего набега на мастер-класс по структурам данных и алгоритмам Colt Steele на Udemy, первая структура данных, которую мы рассмотрим, - это связанный список. Я расскажу о реализации связанного списка и о том, как реализовать перевернутый связанный список в JavaScript.

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

Во-первых, что такое связанный список? Связанный список - это набор узлов, и каждый список имеет свойства заголовок, длина и хвост. Каждый узел будет иметь значение и указатель, который направлен на следующий узел или ноль, если текущий узел является хвостовым. Некоторые особые характеристики связанных списков заключаются в том, что они не индексируются (в отличие от массивов, которые индексируются от 0 до n-1, где n - длина массива), произвольный доступ не разрешен, а узлы связаны указателем next, отмеченным ранее. Под произвольным доступом я подразумеваю, что мы можем получить доступ к любому элементу в списке по индексу, в связанном списке мы можем перемещаться только от головы к хвосту с помощью этого указателя next.

Если вы хотите поиграть с приведенным выше примером, посетите Visualgo.net, там есть отличные визуализации для различных алгоритмов и структур данных.

Реализация связанных списков в JavaScript

Сначала мы создаем класс Node, который имеет только 2 свойства: значение и указатель next.

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

  1. push: добавляет в конец списка

2. pop: удалить из конца списка

3. shift: удалить из заголовка списка

4. unshift: вставить узел в начало списка.

5. get: извлекает значение по заданному индексу.

6. set: при заданном индексе и значении обновляет значение этого узла.

7. insert: принимает индекс и значение и вставляет новый узел.

8. удалить, принимает индекс, удаляет узел по этому индексу.

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

BigO связанных списков

  • Вставка: O (1)
  • Удаление: O (1) или O (n) // удаление по сравнению со списком
  • Ищем: O (n)
  • Доступ: O (n)

Связанные списки и массивы

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

Обратный связанный список

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

  • Поменять местами голову и конец текущего списка
  • Создайте 2 новые переменные, предыдущую и следующую
  • Создайте третий узел переменной и установите для него начальное свойство head.

Прокрутка списка:

  • Установите переменную next как свойство .next любого узла.
  • Установите для свойства .next на узле значение предыдущей переменной.
  • Установите предыдущую переменную как значение переменной узла
  • Установите переменную узла как значение следующей переменной

Ваш код должен выглядеть примерно так:

Больше контента на plainenglish.io