Введение в структуру данных. Концепция Круговой связанный список с практическими примерами, примененными к языку Javascript.
Вы хотите улучшить свои фундаментальные знания в области информатики, особенно структуры данных и алгоритмов? Тогда вы в правильном месте. Давайте рассмотрим некоторые распространенные структуры данных и реализуем их в JavaScript.
Циклический связанный список — это вариант связанного списка, в котором нет конца списка. Последний элемент списка будет указывать на первый элемент, а не на null. Все узлы соединены, образуя круг.
Циклический связанный список может быть одинарным или дважды циклическим связанным списком. Я настоятельно рекомендую прочитать мой блог об односвязном списке и двухсвязном списке, прежде чем знакомиться с круговым связанным списком. Это даст вам обзор односвязных списков и данных двусвязных списков.
Преимущества кругового связанного списка
- Любой узел можно использовать как головную или начальную точку. Мы можем пройти весь список из любой точки и остановиться, когда снова достигнем первого узла.
- Полезно для реализации очереди. В отличие от очереди, реализованной с помощью одного связанного списка, нам не нужно отслеживать первый и последний элементы. Мы можем просто поддерживать указатель предыдущего узла, и к первому узлу всегда можно получить доступ как к следующему из последних.
- Он также широко используется в приложениях, когда нам нужно пройтись по списку или в цикле. им отводят часть времени на выполнение, а затем заставляют их ждать, пока ЦП будет передан другому приложению.
— они используются браузерами для отслеживания истории пользователя, чтобы пользователь мог перемещаться по нему.
- Он также используется в многопользовательских играх. Все игроки хранятся в круговом связанном списке, а указатель продолжает двигаться по мере того, как заканчивается шанс игрока. - Циклический связанный список, реализованный с помощью двусвязного списка, используется для создания расширенной структуры данных, такой как куча Фибоначчи.
Недостатки кругового связанного списка.
- Реализация кругового связанного списка очень сложна по сравнению с другими его вариантами.
- Обратное его также представляет собой сложную задачу.
- Если не пройти должным образом, мы можем оказаться в бесконечном цикле.
- Как и односвязные и двусвязные списки, он также не поддерживает прямой доступ к элементам.
Список операций, выполняемых в круговом связанном списке
- append(element): добавляет новый элемент в список.
- removeAt(position): удаляет элемент из заданной позиции в списке и возвращает его.
- insert(position, element): добавляет элемент в заданную позицию в списке.
- getElementAt(position): возвращает узел в заданной позиции в списке.
- toString(): объединяет все элементы списка и возвращает его в виде строки.
- toArray(): преобразует связанный список в массив и возвращает его.
- indexOf(element): возвращает позицию данного элемента в списке.
- delete(element): удаляет данный элемент из списка.
- deleteHead(): удаляет первый элемент из списка.
- isPresent(element): возвращает true, если элемент присутствует в списке, иначе false.
- isEmpty(): возвращает true, если список пуст, иначе false.
- size(): возвращает размер списка.
- getHead(): возвращает весь список для повторения в прямом направлении.
Большой O методов круговых связанных списков заключается в следующем:
- Вставка — O(n)
- Удаление — O(n)
- Поиск по)
- Доступ — O(n)
Надеюсь, вам понравился этот пост. Не стесняйтесь поделиться своими мыслями по этому поводу.
Вы можете найти больше решений Leetcode в моем блоге и в моем репозитории GitHub. Предположим, вам нравится то, что вы изучаете. смело делайте форк 🔪 и помечайте ⭐ звездочкой.
В этом блоге я попытался собрать и представить наиболее важные моменты, которые следует учитывать при создании приложений Javascript / Node.js, не стесняйтесь добавлять, редактировать, комментировать или спрашивать.
Я рекомендую вам перейти по ссылкам для получения более подробной информации. Удачного кодирования!
