Сегодня я расскажу о том, как сделать круговой двусвязный список. Затем я расскажу о танцующих ссылках и покажу, как создать и то, и другое в Typescript.
Давайте поговорим о том, что такое циклический двусвязный список.
Это структура данных, очень похожая на односвязный список. Он содержит ряд узлов, как и любой другой список, и узлы будут указывать друг на друга. Все узлы идентичны в том смысле, что каждый из них будет иметь свой собственный набор атрибутов, который будет одинаковым для каждого узла. Сам список также является всего лишь одним экземпляром класса List.
Преимуществ у такой структуры множество. Во-первых, вы можете перебирать список в двух направлениях, что может позволить вам найти конкретное значение быстрее, чем в односвязном списке, поскольку вы можете выполнять поиск с обоих концов одновременно. Как только вы нашли узел, вы можете удалить его из списка или добавить еще быстрее, чем массив. Кроме того, это одна из самых основных структур данных, обладающая необходимыми свойствами, подходящими для танцевальных ссылок.
Я собираюсь показать вам реализацию и изображение структуры, чтобы начать. Если вы хотите скопировать этот код и использовать его, вам может потребоваться опустить операторы экспорта перед каждым классом.
export class DCnode {
value:number;
right:DCnode|null;
left:DCnode|null;
accessed:boolean;
constructor(value:number) {
this.value = value;
this.right = null;
this.left = null;
this.accessed = false;
}
}
export class DCLL {
head:DCnode|null
constructor(){
this.head = null;
}
appendDCnode:Function = (value:number) => {
if(this.head == null) {
let a:DCnode = new DCnode(value)
this.head = a;
a.left = a;
a.right = a;
} else {
let b:DCnode|null = this.head
while (b.right != this.head) {
b = b.right;
}
let c:DCnode|null = new DCnode(value)
b.right = c
this.head.left = c
c.right = this.head
c.left = b
}
}
deleteDCNode:Function = (target:number) => {
if(this.head == null) {
return "The list is empty"
} else if (this.head.value == target) {
if (this.head.left == this.head) {
this.head = null
} else {
let a:DCnode|null = this.head.left
let b:DCnode|null = this.head.right
a.right = b
b.left = a
this.head = b
}
} else {
let a:DCnode|null = this.head.left
let b:DCnode|null = this.head.right
this.head.accessed = true;
while (a.accessed == false && a.value != target && b.value != target) {
a = a.left
b = b.right
}
if (a.value == target) {
let p:DCnode|null = a.left
let f:DCnode|null = a.right
p.right = f
f.left = p
this.head.accessed = false;
return a
} else if (b.value == target) {
let p:DCnode|null = b.left
let f:DCnode|null = b.right
p.right = f
f.left = p
this.head.accessed = false;
return b
} else {
return "The list has been searched and the value has not been found"
}
}
}
displayList:Function = () => {
let output: number[] = [];
if (this.head == null) {
return "The List is Empty"
} else {
let a:DCnode|null = this.head.right
this.head.accessed = true
output.push(this.head.value)
while (a.accessed == false) {
output.push(a.value)
a = a.right
}
console.log("complete")
return output
}
}
}
Если вы читали мой блог с односвязными списками, это должно быть довольно прямолинейным для вас. Я также собираюсь следовать тем же инструкциям, что и в прошлый раз.
Если вы не знакомы с односвязными списками, я предлагаю вам ознакомиться с ними, прежде чем переходить к этому.
Только основы
Для начала нам понадобится класс списка и класс узла.
class DCnode {
}
class DCLL {
}
DC — двойной цикл, LL — связанный список, если вам интересно.
Наш узел будет иметь как минимум одно значение, доступ к логическому значению, правое свойство и левое свойство.
В нашем списке будет только свойство head.
class DCnode {
right: DCnode | null;
left: DCnode | null;
value: number;
accessed: boolean;
constructor (value:number) {
this.right = null;
this.left = null;
this.value = value;
this.accessed = false;
}
}
class DCLL {
head: DCnode | null;
constructor () {
this.head = null;
}
}
Отлично, теперь мы готовы начать работу с минимальной функциональностью. Это будет включать удаление узлов и добавление узлов.
Вставить узел
То, как мы вставляем узел, будет очень похоже на наш односвязный список. Мы собираемся проверить, является ли голова нулевой. Если заголовок нулевой, список пуст. В противном случае нам нужно найти хвост и добавить узел.
Но, поскольку это круговой двусвязный список, нам нужно будет установить свойства right и left для добавленного узла, а также свойство right предыдущего узла и свойство left следующего узла.
Поскольку я делаю минимальную реализацию, я собираюсь вставить узел только в конец списка, а новый хвост всегда будет указывать вперед на голову. Точно так же голова всегда будет указывать на новый хвост.
Кроме того, список будет выглядеть довольно странно, если в списке будет только один узел, потому что свойства будут циклически ссылаться на один и тот же узел.
Эти картинки должны помочь нам понять логику, прежде чем мы начнем кодировать. Список с одним узлом просто будет указывать на себя со своими правыми и левыми свойствами.
Чтобы вставить узел, мы можем просто перебирать список, перемещаясь в одном направлении, пока следующий узел в списке не укажет вперед на голову. Мы будем перебирать структуру так же, как односвязный список. Установите головной узел в переменную трекера, затем повторяйте, пока свойство переменной трекера «.right» не укажет на голову.
Затем сделайте так, чтобы его правое свойство ссылалось на новый узел, а не на голову. Затем установите для свойства left нового узла значение старого хвоста. Затем правое свойство нового хвоста к голове и, наконец, левое свойство головы к новому хвосту.
appendDCnode:Function = (value:number) => {
if(this.head == null) {
let a:DCnode = new DCnode(value)
this.head = a;
a.left = a;
a.right = a;
} else {
let b:DCnode|null = this.head
while (b.right != this.head) {
b = b.right;
}
let c:DCnode|null = new DCnode(value)
b.right = c
this.head.left = c
c.right = this.head
c.left = b
}
}
Удалить узел
К счастью для нас, удаление узла из кругового двусвязного списка, на мой взгляд, проще, чем удаление узла из двусвязного или односвязного списка.
Мы могли бы просто перебирать список в одном направлении, пока не найдем узел с нужным нам значением, но если бы мы сделали это таким образом, мы могли бы просто построить односвязный список.
Чтобы использовать возможности двусвязного списка, мы собираемся перебирать список в обоих направлениях одновременно с двумя переменными, чтобы отслеживать узлы, которые мы ищем. Если значение любой переменной трекера соответствует целевому значению, цикл остановится.
Кроме того, всякий раз, когда я начинаю поиск по списку с помощью функции удаления, я собираюсь начать итерацию в узлах на один шаг влево и вправо от головы, а также установить для свойства доступа головы значение true.
Таким образом, если значение не существует в списке, цикл остановится, когда он снова получит доступ к голове.
Самое главное, как только я найду узел со значением, которое хочу удалить, как и в случае односвязного списка, нам нужно изменить указатели предыдущего и последующего узлов, чтобы пропустить удаленный узел, сделав целевой узел недоступным. Давайте обратимся к нашим рисункам, чтобы мы могли убедиться, что у нас есть логика.
deleteDCNode:Function = (target:number) => {
if(this.head == null) {
return "The list is empty"
} else if (this.head.value == target) {
if (this.head.left == this.head) {
this.head = null
} else {
let a:DCnode|null = this.head.left
let b:DCnode|null = this.head.right
a.right = b
b.left = a
this.head = b
}
} else {
let a:DCnode|null = this.head.left
let b:DCnode|null = this.head.right
this.head.accessed = true;
while (a.accessed == false && a.value != target && b.value != target) {
a = a.left
b = b.right
}
if (a.value == target) {
let p:DCnode|null = a.left
let f:DCnode|null = a.right
p.right = f
f.left = p
this.head.accessed = false;
return a
} else if (b.value == target) {
let p:DCnode|null = b.left
let f:DCnode|null = b.right
p.right = f
f.left = p
this.head.accessed = false;
return b
} else {
return "The list has been searched and the value has not been found"
}
}
}
Логика следующая:
Найдите узел-кандидат, сослаться на соседей кандидата через его свойства right и left. Затем сообщите свойству left's right кандидата ссылаться на правого соседа. И наоборот, сообщите свойству left кандидата справа ссылаться на левого соседа.
Таким образом, свойства смежности соседа пропускают кандидата, удаляя его относительное существование из списка.
Вы могли заметить, что я изменяю связанный список, но также возвращаю узел, который мы удалили. Обычно вам не нужно этого делать, но мне нужно, и вы тоже должны привыкнуть к этому, потому что, пока у нас есть способ отслеживать удаленный узел, мы можем реализовать танцующие ссылки.
Теперь, когда мы рассмотрели минимальную функциональность нашего кругового двусвязного списка, позвольте мне рассказать вам о танцующих ссылках.
Танцевальные ссылки
Танцующие связи были обнаружены Хироси Хитоцумацу и Кохей Носита в 1979 году. Вы могли заметить, что когда мы удаляем узел из списка, удаленный узел по-прежнему имеет свойства, ссылающиеся на внешние ссылки. .
Даже если узел не существует относительно списка, список все еще существует относительно удаленного узла. Поскольку мы сохранили удаленный узел, создав переменную для ссылки на него, мы можем получить доступ к списку через свойства удаленного узла.
Это остается верным, независимо от того, сколько узлов мы удалили из списка и в любой комбинации или порядке. Мы могли бы удалить тысячу узлов из большого списка, и все они будут ссылаться на места в списке в каком-то запутанном беспорядке.
Например. Обратите внимание на этот список, в котором есть несколько удаленных узлов.
Если мы восстановим ссылки удаляемых узлов в порядке, обратном их удалению, мы сможем полностью восстановить список. Это остается верным независимо от того, сколько удалений было сделано. Это особенно полезно и эффективно при выполнении сложных алгоритмов, требующих поиска с возвратом, но я приберегу поиск с возвратом для другого блога.
Теперь, когда я объяснил танцующие ссылки, позвольте мне показать вам, как вы можете реализовать их с помощью кругового двусвязного списка, который мы уже создали.
let dCLL:DCLL = new DCLL
let listentry:number = 0
while (listentry < 100) {
dCLL.appendDCnode(listentry)
listentry += 1
}
console.log(dCLL.displayList())
let y:number[] = math.primeSieve(100)
let j:Array<DCnode | null> = [];
for (let i:number = 0; i < y.length; i++) {
let a:DCnode | null = dCLL.deleteDCNode(y[i])
j.unshift(a)
console.log(a.value)
}
console.log(dCLL.displayList())
for (let i:number = 0; i< j.length; i++) {
let a:DCnode|null = j[i]
let p:DCnode|null = a.left
let f:DCnode|null = a.right
p.right = a
f.left = a
}
console.log(dCLL.displayList())
В этом блоке кода я создаю новый кольцевой двусвязный список. Затем я заполняю его 100 значениями от 0 до 99. Я использую свою функцию отображения значений, чтобы это было легче увидеть в командной строке. Моя функция отображаемого значения отображает элементы из списка в виде массива, но ее значения по-прежнему строго соответствуют структуре списка.
Затем я использую решето простых чисел, чтобы найти все простые числа меньше 100. Затем я перебираю массив простых чисел и использую значение простого числа для поиска в моем двусвязном списке и удаляю каждое простое число из моего списка.
Вот что он показывает мне, когда я вызываю отображаемые значения в моем круговом двусвязном списке, когда в списке остаются только составные значения:
Как видите, все простые числа были удалены.
Я также помещаю возвращаемый узел из каждого удаления в отдельный массив, который отслеживает мои удаления. Обратите внимание, я использую метод unshift, который последовательно помещает каждое удаление в начало моего массива. Таким образом, когда я хочу восстановить список, я могу просто перебирать массив удаления спереди назад.
Вот как выглядит мой массив заказов на удаление:
Мы можем ясно видеть, что мой массив удалений содержит мои удаленные узлы в том порядке, в котором я ожидаю.
97 — последнее простое число в списке от 0 до 99. Мы видим, что узел 97 находится впереди массива, а его свойство right по-прежнему ссылается на узел 98.
Теперь о заработке денег. В последнем цикле for моего фрагмента кода танцующих ссылок я перебираю массив удаленных узлов и восстанавливаю их связи в последовательности, обратной их уничтожению, записывая оператор восстановления, который очень похож на оператор уничтожения.
Я хочу добавить, что в своем коде я постоянно делал так, чтобы каждая переменная «p» представляла предыдущий узел, а каждая переменная «f» представляла следующий узел. Так я могу проиллюстрировать этот шаг.
В каждом удалении я писал
p.right = f f.left = p
В каждой реставрации это:
p.right = [deleted node] f.left = [deleted node]
Именно об этом рассказывается в новой книге Дональда Кнута. Искусство компьютерного программирования, том 4, выпуск 5.
И, наконец, после восстановления я могу использовать свою функцию отображения, чтобы увидеть, что мой список был полностью восстановлен.
Попробуй сам. Это был поучительный проект, и мне нравилась каждая его секунда. До скорого.
