В моем предыдущем посте я обсуждал создание односвязного списка на JavaScript (если вы еще не читали этот пост, я предлагаю сделать это сейчас). Единый связанный список состоит из узлов, каждый из которых имеет единственный указатель на следующий узел в списке. Односвязные списки часто требуют обхода всего списка для операций и, как таковые, обычно имеют низкую производительность. Один из способов повысить производительность связанных списков - добавить второй указатель на каждый узел, который указывает на предыдущий узел в списке. Связанный список, узлы которого указывают как на предыдущий, так и на следующий узлы, называется двусвязным списком.
Дизайн двусвязного списка
Подобно односвязному списку, двусвязный список состоит из ряда узлов. Каждый узел содержит некоторые данные, а также указатель на следующий узел в списке и указатель на предыдущий узел. Вот простое представление в JavaScript:
class DoublyLinkedListNode {
constructor(data) {
this.data = data;
this.next = null;
this.previous = null;
}
}В классе DoublyLinkedListNode свойство data содержит значение, которое должен хранить элемент связанного списка, свойство next является указателем на следующий элемент в списке, а свойство previous является указателем на предыдущий элемент в списке. Оба указателя next и previous начинаются как null, потому что следующий и предыдущий узлы не известны во время создания экземпляра класса. Затем вы можете создать двусвязный список, используя класс DoublyLinkedListNode следующим образом:
// create the first node
const head = new DoublyLinkedListNode(12);
// add a second node
const secondNode = new DoublyLinkedListNode(99);
head.next = secondNode;
secondNode.previous = head;
// add a third node
const thirdNode = new DoublyLinkedListNode(37);
secondNode.next = thirdNode;
thirdNode.previous = secondNode;
const tail = thirdNode;Как и в случае односвязного списка, первый узел в двусвязном списке называется заголовком. Второй и третий узлы назначаются с помощью указателей next и previous на каждом узле. На следующем изображении показана результирующая структура данных.
Вы можете перемещаться по двусвязному списку так же, как и по односвязному списку, следуя указателю next на каждом узле, например:
let current = head;
while (current !== null) {
console.log(current.data);
current = current.next;
}Двусвязный список также обычно отслеживает последний узел в списке, который называется хвостом. Конец списка полезен для отслеживания как для упрощения вставки новых узлов, так и для поиска от конца списка к началу. Для этого вы начинаете с хвоста и следуете по previous ссылкам, пока не кончатся узлы. Следующий код распечатывает каждое значение в дважды связанном в обратном порядке:
let current = tail;
while (current !== null) {
console.log(current.data);
current = current.previous;
}Эта возможность перемещаться вперед и назад по двусвязному списку дает преимущество перед односвязным списком, позволяя выполнять поиск в обоих направлениях.
DoublyLinkedList класс
Как и в случае односвязного списка, операции по управлению узлами в двусвязном списке лучше всего инкапсулировать в класс. Вот простой пример:
const head = Symbol("head");
const tail = Symbol("tail");
class DoublyLinkedList {
constructor() {
this[head] = null;
this[tail] = null;
}
}Класс DoublyLinkedList представляет собой двусвязный список и будет содержать методы для взаимодействия с данными, которые он содержит. Есть два свойства символа, head и tail, для отслеживания первого и последнего узлов в списке соответственно. Как и в случае односвязного списка, head и tail не предназначены для доступа извне класса.
Добавление новых данных в список
Добавление элемента в двусвязный список очень похоже на добавление в односвязный список. В обеих структурах данных вы должны сначала найти последний узел в списке, а затем добавить после него новый узел. В односвязном списке вам нужно было пройти весь список, чтобы найти последний узел, тогда как в двусвязном списке последний узел отслеживается с помощью свойства this[tail]. Вот метод add() для класса DoublyLinkedList:
class DoublyLinkedList {
constructor() {
this[head] = null;
this[tail] = null;
}
add(data) {
// create the new node and place the data in it
const newNode = new DoublyLinkedListNode(data);
// special case: no nodes in the list yet
if (this[head] === null) {
this[head] = newNode;
} else {
// link the current tail and new tail
this[tail].next = newNode;
newNode.previous = this[tail];
}
// reassign the tail to be the new node
this[tail] = newNode;
}
}Метод add() для двусвязного списка принимает один аргумент - данные для вставки в список. Если список пуст (и this[head], и this[tail] равны null), то новый узел назначается this[head]. Если список не пуст, то после текущего узла this[tail] добавляется новый узел. Последний шаг - установить this[tail] равным newNode, потому что как в пустом, так и в непустом списке новый узел всегда будет последним узлом.
Обратите внимание, что в случае пустого списка this[head] и this[tail] устанавливаются на один и тот же узел. Это потому, что единственный узел в списке с одним узлом является одновременно первым и последним узлами в этом списке. Важно следить за концом списка, чтобы при необходимости можно было перемещаться по списку в обратном порядке.
Сложность этого add() метода - O (1). Как для пустого, так и для непустого списка операция не требует обхода и поэтому намного менее сложна, чем add() для односвязного списка, в котором отслеживалась только заголовок списка.
Получение данных из списка
Метод get() для двусвязного списка в точности такой же, как метод get() для односвязного списка. В обоих случаях вы должны пройти по списку, начиная с this[head], и отслеживать, сколько узлов было замечено, чтобы определить, когда будет достигнут правильный узел:
class DoublyLinkedList {
// other methods hidden for clarity
get(index) {
// ensure `index` is a positive value
if (index > -1) {
// the pointer to use for traversal
let current = this[head];
// used to keep track of where in the list you are
let i = 0;
// traverse the list until you reach either the end or the index
while ((current !== null) && (i < index)) {
current = current.next;
i++;
}
// return the data if `current` isn't null
return current !== null ? current.data : undefined;
} else {
return undefined;
}
}
}Чтобы повторить из сообщения об односвязном списке, сложность метода get() варьируется от O (1) при удалении первого узла (обход не требуется) до O (n) при удалении последнего узла (требуется обход всего списка) .
Удаление данных из двусвязного списка
Алгоритм удаления данных из двусвязного списка по существу такой же, как и для односвязного списка: сначала просмотрите структуру данных, чтобы найти узел в заданной позиции (тот же алгоритм, что и get()), а затем удалите его из списка. Единственные существенные отличия от алгоритма, используемого в односвязном списке:
- Нет необходимости в переменной
previousдля отслеживания одного узла в цикле, потому что предыдущий узел всегда доступен черезcurrent.previous. - Вам нужно следить за изменениями последнего узла в списке, чтобы убедиться, что
this[tail]остается правильным.
В остальном метод remove() очень похож на метод односвязного списка:
class DoublyLinkedList {
// other methods hidden for clarity
remove(index) {
// special cases: no nodes in the list or `index` is negative
if ((this[head] === null) || (index < 0)) {
throw new RangeError(`Index ${index} does not exist in the list.`);
}
// special case: removing the first node
if (index === 0) {
// store the data from the current head
const data = this[head].data;
// just replace the head with the next node in the list
this[head] = this[head].next;
// special case: there was only one node, so also reset `this[tail]`
if (this[head] === null) {
this[tail] = null;
} else {
this[head].previous = null;
}
// return the data at the previous head of the list
return data;
}
// pointer use to traverse the list
let current = this[head];
// used to track how deep into the list you are
let i = 0;
// same loop as in `get()`
while ((current !== null) && (i < index)) {
// traverse to the next node
current = current.next;
// increment the count
i++;
}
// if node was found, remove it
if (current !== null) {
// skip over the node to remove
current.previous.next = current.next;
// special case: this is the last node so reset `this[tail]`.
if (this[tail] === current) {
this[tail] = current.previous;
} else {
current.next.previous = current.previous;
}
// return the value that was just removed from the list
return current.data;
}
// if node wasn't found, throw an error
throw new RangeError(`Index ${index} does not exist in the list.`);
}
}Когда index равно 0, что означает, что первый узел удаляется, this[head] устанавливается в this[head].next, то же самое, что и для односвязного списка. Разница наступает после этого момента, когда вам нужно обновить другие указатели. Если в списке был только один узел, то вам нужно установить this[tail] в null, чтобы эффективно удалить этот единственный узел; если было более одного узла, вам нужно установить this[head].previous на null. Помните, что новый заголовок ранее был вторым узлом в списке, и поэтому его ссылка previous указывала на узел, который был только что удален.
После цикла необходимо убедиться, что указатель next узла перед удаленным узлом и указатель previous узла после удаленного узла. Конечно, если удаляемый узел является последним узлом, вам необходимо обновить указатель this[tail].
Создание обратного итератора
Вы можете сделать двусвязный список повторяемым в JavaScript, используя те же методы values() и Symbol.iterator из односвязного списка. Однако в двусвязном списке у вас есть возможность создать обратный итератор, который производит данные, начиная с хвоста и продвигаясь к голове. Вот как выглядит метод генератора reverse():
class DoublyLinkedList {
// other methods hidden for clarity
*reverse(){
// start by looking at the tail
let current = this[tail];
// follow the previous links to the head
while (current !== null) {
yield current.data;
current = current.previous;
}
}
}Метод генератора reverse() следует тому же алгоритму, что и метод генератора values() в односвязном списке, за исключением того, что current начинается равным this[tail], а current.previous выполняется до тех пор, пока больше не будет узлов. Создание обратного итератора полезно для обнаружения ошибок в реализации, а также для предотвращения переупорядочения узлов только для доступа к данным в другом порядке.
Другие методы
Большинство других методов, не связанных с добавлением или удалением узлов, основаны на тех же алгоритмах, что и в односвязном списке.
Использование класса
После завершения вы можете использовать реализацию связанного списка следующим образом:
const list = new DoublyLinkedList();
list.add("red");
list.add("orange");
list.add("yellow");
// get the second item in the list
console.log(list.get(1)); // "orange"
// print out all items in reverse
for (const color of list.reverse()) {
console.log(color);
}
// remove the second item in the list
console.log(list.remove(1)); // "orange"
// get the new first item in the list
console.log(list.get(1)); // "yellow"
// convert to an array
const array1 = [...list.values()];
const array2 = [...list];
const array3 = [...list.reverse()];Полный исходный код доступен на GitHub в моем проекте Информатика в JavaScript.
Заключение
Двусвязные списки похожи на односвязные списки в том, что каждый узел имеет указатель next на следующий узел в списке. Каждый узел также имеет указатель previous на предыдущий узел в списке, что позволяет легко перемещаться как вперед, так и назад по списку. Двусвязные списки обычно отслеживают как первый, так и последний узел в списке, и это делает добавление узла в список операцией O (1) вместо O (n) в односвязном списке.
Однако сложность других операций с двусвязным списком такая же, как и с односвязным списком, потому что вы всегда проходите большую часть списка. Таким образом, двусвязные списки не дают никаких реальных преимуществ по сравнению со встроенным классом JavaScript Array для хранения набора несвязанных данных (хотя связанные данные, такие как одноуровневые узлы DOM в браузере), могут быть полезны для представления в каком-либо виде. связанного списка.
Эта запись изначально появилась в блоге Человек, который кодирует 5 февраля 2019 года. Если вам понравился этот пост, пожалуйста, подумайте о пожертвовании в поддержку моей работы.
