ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ. В этой статье предполагается, что читатель знаком с теоретическими концепциями двусвязного списка и ООП в JS, и основное внимание уделяется пониманию и реализации псевдокода и программы JavaScript для них. Кроме того, я из тех, кто не использует точки с запятой в коде, поэтому, пожалуйста, не волнуйтесь. Код работает отлично ;) Приступим!
ПРЕДВАРИТЕЛЬНЫЕ ТРЕБОВАНИЯ — Двойной (двойной) связанный список — это структура данных, в которой каждый узел содержит данные/значение и ссылается на два других узла. Ссылка next указывает на следующий узел, а ссылка prev указывает на предыдущий узел. (Ссылка в основном аналогична указанию или сохранению адреса следующего или предыдущего узла.) Как и односвязный список, двусвязный список (DLL) имеет головной узел и tail узел, где головной узел является первым узлом, вошедшим в связанный список, а хвостовой узел — последним узлом, вошедшим в связанный список.
ОПЕРАЦИИ НА ДВУСТОРОННЕМ СПИСКЕ
Существуют различные операции, которые можно выполнять с DLL. Мы столкнемся с ними по мере продвижения. Мы будем писать код, используя парадигму ООП, где мы определяем план (класс) нашего связанного списка и нашего узла.
УЗЕЛ
Узел в DLL содержит три значения; предыдущая, данные, следующая, где
prev = значение предыдущего узла.
data = значение текущего узла.
next = значение следующего узла.
Таким образом, план нашей ноды в JS будет выглядеть примерно так:
ДВОЙНОЙ ССЫЛОЧНЫЙ СПИСОК
Наша DLL содержит несколько узлов, связанных друг с другом, где будет только один головной узел и конечный узел.
Таким образом, план нашего двусвязного списка в JS будет выглядеть примерно так:
Как видите, у нас также есть свойство «длина», мы увидим его позже в статье, зачем оно нам нужно. Пожалуйста, побудь со мной немного :D
Мы создали классы для DLL и Node. Теперь, чтобы работать с DLL, нам нужно определить методы в DLL, которые воздействуют на свойства DLL.
1. Добавление хвостового узла
Этот метод определен в классе DoubleLL. Эта операция добавляет хвостовой узел в двусвязный список.
- Создайте новый узел.
let newNode = new Node(this.tail, data, null) // Creating an instance of the Node Class.
Случай 1: когда список не пуст
- Значение следующее всегда равно null.
- Значение prev всегда является текущим хвостовым узлом.
- Значением next текущего хвостового узла всегда является новый хвостовой узел.
- Назначьте новый узел хвостовым узлом.
let newNode = new Node(this.tail, data, null) this.tail.next = newNode this.tail = newNode
Случай 2: Когда список пуст.
- Значение следующее всегда равно null.
- Значение prev всегда является текущим хвостовым узлом.
- Поскольку нет текущего хвостового узла, так как список пуст, значение prev будет null, поэтому мы помечаем новый узел как головной. узел.
- Назначьте новый узел хвостовым узлом.
let newNode = new Node(this.tail, data, null) if (!this.tail) this.head = newNode this.tail = newNode
Теперь общий метод добавления хвостового узла выглядит следующим образом:
P.S. Как упоминалось ранее, мы обсудим строку номер 3 через некоторое время. Терпения, дорогой читатель :)
2. Добавление головного узла
Этот метод добавляет головной узел в двусвязный список.
- Создайте новый узел.
let newNode = new Node(null, data, this.head) // Creating an instance of the Node Class.
Случай 1: когда список не пуст
- Значение prev всегда равно null.
- Значение следующий всегда является текущим головным узлом.
- Значением prev текущего головного узла всегда является новый головной узел.
- Назначьте новый узел головным узлом.
let newNode = new Node(null, data, this.head) this.head.prev = newNode this.head = newNode
Случай 2: Когда список пуст.
- Значение prev всегда равно null.
- Значение следующий всегда является текущим головным узлом.
- Поскольку текущий головной узел отсутствует, так как список пуст, значение prev нового узла будет null, поэтому мы помечаем новый узел как хвостовой узел.
- Назначьте новый узел головным узлом.
let newNode = new Node(null, data, this.head) if (!this.head) this.tail = newNode this.head = newNode
Теперь общий метод добавления хвостового узла выглядит следующим образом:
3. Удаление хвостового узла
Этот метод удаляет хвост из двусвязного списка.
Случай 1: если список пуст
- вернуть ‘Пустой связанный список’.
if (!this.tail) return "Linked List is Empty"
Случай 2: если список состоит ровно из одного узла
- prev хвостового узла становится новым хвостовым узлом.
- Поскольку новый хвостовой узел имеет значение null, головной узел также становится нулевым.
- Возвращает значение удаленного узла.
let value = this.tail.data; this.tail = this.tail.prev; if(!this.tail) this.head = null return `removed Tail Node: ${value}`
Случай 3: Если список не пуст
- prev хвостового узла становится новым хвостовым узлом.
- Значение next хвостового узла становится нулевым.
- Возвращает значение удаленного узла.
let value = this.tail.data; this.tail = this.tail.prev; this.tail.next = null return `removed Tail Node: ${value}`
Теперь общий метод удаления хвостового узла выглядит следующим образом:
4. Удаление головного узла
Этот метод удаляет заголовок из двусвязного списка.
Случай 1: если список пуст
- вернуть ‘Пустой связанный список’.
if (!this.tail) return "Linked List is Empty"
Случай 2: если список состоит ровно из одного узла
- prev хвостового узла становится новым хвостовым узлом.
- Поскольку новый хвостовой узел имеет значение null, головной узел также становится нулевым.
- Возвращает значение удаленного узла.
let value = this.head.data this.head = this.head.next if(!this.head) this.tail = null return `removed Head Node: ${value}`
Случай 3: Если список не пуст
- prev хвостового узла становится новым хвостовым узлом.
- Значение next хвостового узла становится нулевым.
- Возвращает значение удаленного узла.
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: если список пуст
- Вернуть «связанный список пуст»
if (!current) return "Linked List is Empty"
Случай 2: если список не пуст
- Переход от головного узла до тех пор, пока узел не исчезнет.
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 или отрицательный
- Возвращает «Индекс за пределами. Невозможно вставить новый узел».
Случай 2: если индекс равен НУЛЮ
- Если индекс равен нулю, добавьте его в качестве головного узла.
if (n === 0 return this.addHeadNode(data)
Случай 3: если индекс равен длине DLL
- если индекс равен длине DLL, добавьте его как хвостовой узел, так как индексация начинается с нуля (как массивы)
if (n === this.length) return this.addTailNode(data)
Случай 4: если индекс больше НУЛЯ и меньше длины DLL
- Перейдите до позиции индекса и создайте новый узел.
- Значение prev нового узла — это значение prev текущего узла, присутствующего в позиции индекса.
- Значение следующий нового узла — это текущий узел, присутствующий в позиции индекса.
- Значение prev текущего узла является новым узлом.
- следующее значение узла перед новым узлом является новым узлом.
Теперь общий метод добавления узла по n-му индексу выглядит так:
7. Поиск элемента в DLL.
Перемещайтесь по DLL от головного узла до тех пор, пока узел не исчезнет.
Случай 1: если элемент существует
- Возврат «Элемент присутствует в связанном списке»
Случай 2: если элемент не существует (или) пуст
- Вернуть «Узел не существует».
Код для поиска элемента в точности аналогичен обходу LL.
8. Удаление узла в любой позиции (индекс)
Случай 1: если индекс больше или равен длине DLL или отрицательный
- Возвращает «Индекс за пределами. Узел не может быть удален»
Случай 2: если индекс равен НУЛЮ
- если индекс равен нулю, удалите головной узел.
if (n === 0) return this.removeHead();
Случай 3: если индекс равен длине 1 библиотеки DLL
- если индекс равен длине DLL, удалите хвостовой узел, так как индексация начинается с нуля (как массивы)
if (n === this.length-1) return this.removeTail()
Случай 4: если индекс больше НУЛЯ и меньше длины DLL
- Пройдите до позиции индекса и получите текущий узел.
- Пометить значение prev текущего узла как предыдущий узел.
- Пометить следующее значение текущего узла как следующий узел.
- prev значение следующего узла – это предыдущий узел.
- следующее значение предыдущего узла является следующим узлом.
Теперь общий метод удаления по n-му индексу выглядит так:
9. Удаление всего связанного списка
Случай 1: если список пуст
- Возврат «Связанный список пуст»
Случай 2: если список не пуст.
- Объявите переменную curr и присвойте ей значение узла head.
- Переход от головного узла до тех пор, пока узел не исчезнет.
let curr = this.head while (curr) { this.head = curr.next curr = curr.next }
Теперь общий метод удаления связанного списка выглядит так:
10. Реверс связанного списка
Случай 1: если список пуст
- Возврат «Связанный список пуст»
Случай 2: если список не пуст.
- Объявите переменную current и присвойте ей значение узла head.
- Переход от головного узла до тех пор, пока узел не исчезнет.
- Объявите переменную temp и присвойте ей значение prev текущего узла.
- Назначьте следующеезначение текущегоузла предыдущемузначению текущегоузла.
- Назначьте значение temp следующему значению текущего узла.
- Обычно для перехода к следующему узлу мы делаем «curr = curr.next», но, поскольку мы поменяли ссылки, чтобы перейти к следующему узлу, мы должны присвоить текущийузел prev текущегоузла.
- Измените конечное значение узла head на последнее значение temp.
Теперь общий метод обращения списка выглядит так:
И мы закончили! Ниже приведен окончательный код для DLL
Теперь, когда мы поняли, как создать двусвязный список и какие операции можно выполнять, создание односвязного списка должно быть очень простым.
Много сил ушло на создание этого блога. Ставьте лайк, если этот блог был вам полезен. Мир!