ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ. В этой статье предполагается, что читатель знаком с теоретическими концепциями двусвязного списка и ООП в JS, и основное внимание уделяется пониманию и реализации псевдокода и программы JavaScript для них. Кроме того, я из тех, кто не использует точки с запятой в коде, поэтому, пожалуйста, не волнуйтесь. Код работает отлично ;) Приступим!

ПРЕДВАРИТЕЛЬНЫЕ ТРЕБОВАНИЯ — Двойной (двойной) связанный список — это структура данных, в которой каждый узел содержит данные/значение и ссылается на два других узла. Ссылка next указывает на следующий узел, а ссылка prev указывает на предыдущий узел. (Ссылка в основном аналогична указанию или сохранению адреса следующего или предыдущего узла.) Как и односвязный список, двусвязный список (DLL) имеет головной узел и tail узел, где головной узел является первым узлом, вошедшим в связанный список, а хвостовой узел — последним узлом, вошедшим в связанный список.

ОПЕРАЦИИ НА ДВУСТОРОННЕМ СПИСКЕ

Существуют различные операции, которые можно выполнять с DLL. Мы столкнемся с ними по мере продвижения. Мы будем писать код, используя парадигму ООП, где мы определяем план (класс) нашего связанного списка и нашего узла.

УЗЕЛ

Узел в DLL содержит три значения; предыдущая, данные, следующая, где

prev = значение предыдущего узла.

data = значение текущего узла.

next = значение следующего узла.

Таким образом, план нашей ноды в JS будет выглядеть примерно так:

ДВОЙНОЙ ССЫЛОЧНЫЙ СПИСОК

Наша DLL содержит несколько узлов, связанных друг с другом, где будет только один головной узел и конечный узел.

Таким образом, план нашего двусвязного списка в JS будет выглядеть примерно так:

Как видите, у нас также есть свойство «длина», мы увидим его позже в статье, зачем оно нам нужно. Пожалуйста, побудь со мной немного :D

Мы создали классы для DLL и Node. Теперь, чтобы работать с DLL, нам нужно определить методы в DLL, которые воздействуют на свойства DLL.

1. Добавление хвостового узла

Этот метод определен в классе DoubleLL. Эта операция добавляет хвостовой узел в двусвязный список.

  1. Создайте новый узел.
let newNode = new Node(this.tail, data, null)
// Creating an instance of the Node Class.

Случай 1: когда список не пуст

  1. Значение следующее всегда равно null.
  2. Значение prev всегда является текущим хвостовым узлом.
  3. Значением next текущего хвостового узла всегда является новый хвостовой узел.
  4. Назначьте новый узел хвостовым узлом.
let newNode = new Node(this.tail, data, null)
this.tail.next = newNode
this.tail = newNode

Случай 2: Когда список пуст.

  1. Значение следующее всегда равно null.
  2. Значение prev всегда является текущим хвостовым узлом.
  3. Поскольку нет текущего хвостового узла, так как список пуст, значение prev будет null, поэтому мы помечаем новый узел как головной. узел.
  4. Назначьте новый узел хвостовым узлом.
let newNode = new Node(this.tail, data, null)
if (!this.tail)
 this.head = newNode
this.tail = newNode

Теперь общий метод добавления хвостового узла выглядит следующим образом:

P.S. Как упоминалось ранее, мы обсудим строку номер 3 через некоторое время. Терпения, дорогой читатель :)

2. Добавление головного узла

Этот метод добавляет головной узел в двусвязный список.

  1. Создайте новый узел.
let newNode = new Node(null, data, this.head)
// Creating an instance of the Node Class.

Случай 1: когда список не пуст

  1. Значение prev всегда равно null.
  2. Значение следующий всегда является текущим головным узлом.
  3. Значением prev текущего головного узла всегда является новый головной узел.
  4. Назначьте новый узел головным узлом.
let newNode = new Node(null, data, this.head)
this.head.prev = newNode
this.head = newNode

Случай 2: Когда список пуст.

  1. Значение prev всегда равно null.
  2. Значение следующий всегда является текущим головным узлом.
  3. Поскольку текущий головной узел отсутствует, так как список пуст, значение prev нового узла будет null, поэтому мы помечаем новый узел как хвостовой узел.
  4. Назначьте новый узел головным узлом.
let newNode = new Node(null, data, this.head)
if (!this.head)
this.tail = newNode
this.head = newNode

Теперь общий метод добавления хвостового узла выглядит следующим образом:

3. Удаление хвостового узла

Этот метод удаляет хвост из двусвязного списка.

Случай 1: если список пуст

  1. вернуть ‘Пустой связанный список’.
if (!this.tail)
return "Linked List is Empty"

Случай 2: если список состоит ровно из одного узла

  1. prev хвостового узла становится новым хвостовым узлом.
  2. Поскольку новый хвостовой узел имеет значение null, головной узел также становится нулевым.
  3. Возвращает значение удаленного узла.
let value = this.tail.data;
this.tail = this.tail.prev;
if(!this.tail)
this.head = null
return `removed Tail Node: ${value}`

Случай 3: Если список не пуст

  1. prev хвостового узла становится новым хвостовым узлом.
  2. Значение next хвостового узла становится нулевым.
  3. Возвращает значение удаленного узла.
let value = this.tail.data;
this.tail = this.tail.prev;
this.tail.next = null
return `removed Tail Node: ${value}`

Теперь общий метод удаления хвостового узла выглядит следующим образом:

4. Удаление головного узла

Этот метод удаляет заголовок из двусвязного списка.

Случай 1: если список пуст

  1. вернуть ‘Пустой связанный список’.
if (!this.tail)
return "Linked List is Empty"

Случай 2: если список состоит ровно из одного узла

  1. prev хвостового узла становится новым хвостовым узлом.
  2. Поскольку новый хвостовой узел имеет значение null, головной узел также становится нулевым.
  3. Возвращает значение удаленного узла.
let value = this.head.data
this.head = this.head.next
if(!this.head)
this.tail = null
return `removed Head Node: ${value}`

Случай 3: Если список не пуст

  1. prev хвостового узла становится новым хвостовым узлом.
  2. Значение next хвостового узла становится нулевым.
  3. Возвращает значение удаленного узла.
let value = this.tail.data;
this.head = this.head.next;
this.head.prev = null
return `removed Head Node: ${value}`

Теперь общий метод удаления головного узла выглядит так:

5. Обход двусвязного списка

Чтобы пройти или выполнить итерацию по двусвязному списку, мы должны начать с головного узла и закончить на хвостовом узле или наоборот. Давайте сначала начнем с узла Head.

Давайте объявим переменную current и назначим ей головной узел.

let current = this.head

Случай 1: если список пуст

  1. Вернуть «связанный список пуст»
if (!current)
return "Linked List is Empty"

Случай 2: если список не пуст

  1. Переход от головного узла до тех пор, пока узел не исчезнет.
while (curr) {            process.stdout.write(`|${curr.prev?.data}|${curr.data}|${curr.next?.data}| ---> `)
curr = curr.next
}

Теперь общий метод обхода выглядит так:

P.S. Существует великий миф о том, что мы не можем пройтись по двусвязному списку в обратном направлении, и я до глубины души потрясен тем, что программисты думают таким образом. Это абсолютно возможно и легко AF. Просто начните с хвостового узла и перейдите к предыдущему узлу.

6. Добавление узла в любую позицию (индекс)

Теперь пришло время обратиться к свойству length в классе DoubleLL. Поскольку у нас нет индексов в DLL для отслеживания длины связанного списка и вставки в заданную позицию, мы добавляем свойство «длина» в конструктор DoubleLL, чтобы отслеживать размер DLL.

Случай 1: если индекс больше длины DLL или отрицательный

  1. Возвращает «Индекс за пределами. Невозможно вставить новый узел».

Случай 2: если индекс равен НУЛЮ

  1. Если индекс равен нулю, добавьте его в качестве головного узла.
if (n === 0
return this.addHeadNode(data)

Случай 3: если индекс равен длине DLL

  1. если индекс равен длине DLL, добавьте его как хвостовой узел, так как индексация начинается с нуля (как массивы)
if (n === this.length)
return this.addTailNode(data)

Случай 4: если индекс больше НУЛЯ и меньше длины DLL

  1. Перейдите до позиции индекса и создайте новый узел.
  2. Значение prev нового узла — это значение prev текущего узла, присутствующего в позиции индекса.
  3. Значение следующий нового узла — это текущий узел, присутствующий в позиции индекса.
  4. Значение prev текущего узла является новым узлом.
  5. следующее значение узла перед новым узлом является новым узлом.

Теперь общий метод добавления узла по n-му индексу выглядит так:

7. Поиск элемента в DLL.

Перемещайтесь по DLL от головного узла до тех пор, пока узел не исчезнет.

Случай 1: если элемент существует

  1. Возврат «Элемент присутствует в связанном списке»

Случай 2: если элемент не существует (или) пуст

  1. Вернуть «Узел не существует».

Код для поиска элемента в точности аналогичен обходу LL.

8. Удаление узла в любой позиции (индекс)

Случай 1: если индекс больше или равен длине DLL или отрицательный

  1. Возвращает «Индекс за пределами. Узел не может быть удален»

Случай 2: если индекс равен НУЛЮ

  1. если индекс равен нулю, удалите головной узел.
if (n === 0)
return this.removeHead();

Случай 3: если индекс равен длине 1 библиотеки DLL

  1. если индекс равен длине DLL, удалите хвостовой узел, так как индексация начинается с нуля (как массивы)
if (n === this.length-1)
return this.removeTail()

Случай 4: если индекс больше НУЛЯ и меньше длины DLL

  1. Пройдите до позиции индекса и получите текущий узел.
  2. Пометить значение prev текущего узла как предыдущий узел.
  3. Пометить следующее значение текущего узла как следующий узел.
  4. prev значение следующего узла – это предыдущий узел.
  5. следующее значение предыдущего узла является следующим узлом.

Теперь общий метод удаления по n-му индексу выглядит так:

9. Удаление всего связанного списка

Случай 1: если список пуст

  1. Возврат «Связанный список пуст»

Случай 2: если список не пуст.

  1. Объявите переменную curr и присвойте ей значение узла head.
  2. Переход от головного узла до тех пор, пока узел не исчезнет.
let curr = this.head
while (curr) {
this.head = curr.next
curr = curr.next }

Теперь общий метод удаления связанного списка выглядит так:

10. Реверс связанного списка

Случай 1: если список пуст

  1. Возврат «Связанный список пуст»

Случай 2: если список не пуст.

  1. Объявите переменную current и присвойте ей значение узла head.
  2. Переход от головного узла до тех пор, пока узел не исчезнет.
  3. Объявите переменную temp и присвойте ей значение prev текущего узла.
  4. Назначьте следующеезначение текущегоузла предыдущемузначению текущегоузла.
  5. Назначьте значение temp следующему значению текущего узла.
  6. Обычно для перехода к следующему узлу мы делаем «curr = curr.next», но, поскольку мы поменяли ссылки, чтобы перейти к следующему узлу, мы должны присвоить текущийузел prev текущегоузла.
  7. Измените конечное значение узла head на последнее значение temp.

Теперь общий метод обращения списка выглядит так:

И мы закончили! Ниже приведен окончательный код для DLL

Теперь, когда мы поняли, как создать двусвязный список и какие операции можно выполнять, создание односвязного списка должно быть очень простым.

Много сил ушло на создание этого блога. Ставьте лайк, если этот блог был вам полезен. Мир!