В продолжение моего набега на мастер-класс по структурам данных и алгоритмам Colt Steele на Udemy, первая структура данных, которую мы рассмотрим, - это связанный список. Я расскажу о реализации связанного списка и о том, как реализовать перевернутый связанный список в JavaScript.
В некоторых языках программирования предусмотрены собственные структуры данных, но в JavaScript нам нужно будет создать класс с определенными атрибутами, чтобы иметь возможность использовать эти структуры данных. К настоящему моменту вы должны знать, что классы можно рассматривать как схемы и что всякий раз, когда мы хотим использовать структуру данных, мы можем создавать экземпляры этих схем, которые унаследовали атрибуты этих вышеупомянутых классов.
Во-первых, что такое связанный список? Связанный список - это набор узлов, и каждый список имеет свойства заголовок, длина и хвост. Каждый узел будет иметь значение и указатель, который направлен на следующий узел или ноль, если текущий узел является хвостовым. Некоторые особые характеристики связанных списков заключаются в том, что они не индексируются (в отличие от массивов, которые индексируются от 0 до n-1, где n - длина массива), произвольный доступ не разрешен, а узлы связаны указателем next, отмеченным ранее. Под произвольным доступом я подразумеваю, что мы можем получить доступ к любому элементу в списке по индексу, в связанном списке мы можем перемещаться только от головы к хвосту с помощью этого указателя next.
Если вы хотите поиграть с приведенным выше примером, посетите Visualgo.net, там есть отличные визуализации для различных алгоритмов и структур данных.
Реализация связанных списков в JavaScript
Сначала мы создаем класс Node, который имеет только 2 свойства: значение и указатель next.
Используя этот класс Node вместе с некоторой логикой, мы можем реализовать класс односвязного списка с помощью следующих методов:
- 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