Привет всем, это седьмая часть серии блогов о структурах данных и алгоритмах в JavaScript. В этом блоге я расскажу об круговом связанном списке.
Что такое циклический связанный список?
Круговой связанный список — это связанный список, в котором все узлы соединены в круг. В конце нет NULL. Круговой связанный список может быть одинарным круговым списком или дважды круговым связанным списком.— geeksforgeeks.org
Рис.: Круговой одиночный связанный список
Рис.: Круговой двусвязный список
Список доступных операций
- Все методы будут такими же, как и для одного связанного списка. Перезаписывать только методы insert, push и removeAt.
Реализация кругового связанного списка в Javascript
Класс CircularLinkedList не нуждается в дополнительных свойствах, поэтому мы можем просто расширить класс LinkedList, только перезаписав необходимые методы.
class CircularLinkedList extends LinkedList {
constructor(){
super();
}
}Толкать
Метод push добавит элемент в конец LinkedList. При добавлении элемента (узла) возможны два сценария:
- LinkedList пуст.
- установите свойство заголовка связанного списка для нового узла.
- установите новый узел рядом с головой, поскольку круговой LinkedList не имеет нулевого указателя в конце.
2. LinkedList не пуст.
- петля до конца.
- установите конечный узел на новый узел, т. е. конечный узел рядом с узлом.
- установите новый узел рядом с головой. после нажатия элемента в связанный список увеличивает счетчик
push(element){
let node = new Node(element);
let current = this.head;
if (current == undefined) {
this.head = node;
node.next = this.head;
} else {
while(current.next != null){
current = current.next;
}
current.next = node;
node.next = this.head;
}
this.count++;
return this;
}Вставлять
Метод Insert вставит элемент в заданную позицию. Позиция должна быть больше нуля и меньше или равна count (длина LinkedList). Если не вернуть undefined.
- Индекс равен нулю
I. Пусто
- То же, что и условие метода push, когда LinkedList пуст.
II. Не пусто
- установите новый узел на текущую головку.
- перейти к новому узлу.
2. Индекс равен count .т.е. длине LinkedList
- Получить элемент (index — 1) с помощью метода getElementAt, сохранить как предыдущий элемент.
- Установите предыдущий к новому узлу. И узел рядом с головой.
3. Индекс больше нуля
- Получить элемент (index — 1) с помощью метода getElementAt, сохранить как предыдущий элемент.
- Индексированный элемент будет предыдущим. затем сохранить как текущий.
- Установите предыдущий к новому узлу. И узел рядом с предыдущим.
после помещения элемента в связанный список увеличить счетчик
insert(element,index){
if (index >= 0 && index <= this.count) {
const node = new Node(element);
let current = this.head
if (index == 0) {
if (this.head == undefined) {
this.head = node;
node.next = this.head;
}else{
node.next = current;
this.head = node;
}
}else if (index == this.count) {
const previous = this.getElementAt(index -1);
previous.next = node;
node.next = this.head;
}else{
const previous = this.getElementAt(index -1);
current = previous.next;
previous.next = node;
node.next = current;
}
this.count++;
return this;
}
return undefined;
}RemoveAt
Метод RemovAt удалит элемент в заданной позиции. Позиция должна подтверждать ошибку индекса за пределами границы, проверяя, что позиция больше и равна нулю и меньше, чем count. Если не вернуть undefined.
- LinkedList пуст
- вернуть неопределенное
2.Индекс равен нулю.
- Переместите голову к следующему узлу.
3. Индекс равен количеству — 1.
- Получить элемент (index — 1) с помощью метода getElementAt, сохранить как предыдущий элемент.
- Установите предыдущий рядом с головой.
4. Индекс больше нуля
- Получить элемент (index — 1) с помощью метода getElementAt, сохранить как предыдущий элемент.
- Индексируемый элемент будет предыдущим.следующим, сохранится как текущий.
- установить предыдущий.следующий на текущий.следующий.
после удаления элемента из связанного списка уменьшить счетчик
removeAt(index){ if (index >= 0 && index < this.count) { if (this.isEmpty()) { return undefined; } let current = this.head if (index == 0) { this.head = current.next; } else if(index == this.count-1) { const previous = this.getElementAt(index-1); current = previous.next; previous.next = this.head; }else{ const previous = this.getElementAt(index -1); current = previous.next; previous.next = current.next; }this.count --; return current.element; } return undefined; }
Получить полный исходный код здесь
Вывод :
Сложность будет такой же, как и в односвязном списке. Этот блог охватывает только один круговой связанный список. Но дважды круговой связанный список будет похож на двусвязный список.
Итак, следите за обновлениями в следующем блоге, в котором я расскажу о другом отсортированном связанном списке DS.
