Двунаправленный связный список (Double Linked List) — это структура данных, в которой каждый узел содержит ссылки на следующий и предыдущий узлы. Это позволяет легко перемещаться в обоих направлениях по списку.
Вот пример реализации двунаправленного связного списка на JavaScript:
Каждый узел содержит данные, ссылку на следующий узел и ссылку на предыдущий узел:
class Node {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
Класс двунаправленного связного списка содержит методы для добавления, удаления и поиска узлов:
class DoubleLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// Добавление узла в конец списка
append(data) {
const newNode = new Node(data);
if (this.tail === null) {
this.head = newNode;
this.tail = newNode;
return;
}
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
// Добавление узла в начало списка
prepend(data) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
return;
}
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
// Удаление узла по значению
delete(data) {
if (this.head === null) {
return;
}
if (this.head.data === data) {
this.head = this.head.next;
if (this.head !== null) {
this.head.prev = null;
} else {
this.tail = null;
}
return;
}
let current = this.head;
while (current !== null && current.data !== data) {
current = current.next;
}
if (current !== null) {
if (current.next !== null) {
current.next.prev = current.prev;
} else {
this.tail = current.prev;
}
if (current.prev !== null) {
current.prev.next = current.next;
}
}
}
// Поиск узла по значению
find(data) {
let current = this.head;
while (current !== null && current.data !== data) {
current = current.next;
}
return current;
}
// Печать списка с начала
printFromHead() {
let current = this.head;
while (current !== null) {
console.log(current.data);
current = current.next;
}
}
// Печать списка с конца
printFromTail() {
let current = this.tail;
while (current !== null) {
console.log(current.data);
current = current.prev;
}
}
}
const list = new DoubleLinkedList();
// Добавление элементов
list.append(1);
list.append(2);
list.append(3);
// Печать списка с начала
list.printFromHead(); // 1, 2, 3
// Добавление элемента в начало
list.prepend(0);
list.printFromHead(); // 0, 1, 2, 3
// Печать списка с конца
list.printFromTail(); // 3, 2, 1, 0
// Поиск элемента
const foundNode = list.find(2);
console.log(foundNode ? foundNode.data : 'Not found'); // 2
// Удаление элемента
list.delete(2);
list.printFromHead(); // 0, 1, 3
list.printFromTail(); // 3, 1, 0
Эта реализация включает основные операции для работы с двунаправленным связным списком: добавление узлов в начало и конец списка, удаление узлов по значению, поиск узлов по значению и печать всего списка с начала и с конца.