Часть 1 из серии «Структуры данных с JavaScript».
Говорят, лучший способ чему-то научиться — это научить этому. В этой серии статей я расскажу вам о различных структурах данных и о том, как их создавать с помощью классов и методов JavaScript. Прежде всего, мы рассмотрим односвязный список.
Что такое связанный список?
Связный список — это структура данных, состоящая из узлов. Каждый узел имеет значение и указатель на другой узел. Связанный список будет иметь свойства head, tail и length. В односвязном списке каждый узел имеет только одно соединение со следующим узлом. На диаграмме ниже голова — это узел со значением 5, хвост — это узел со значением 1, а длина равна 4.
Связанные списки против массивов
В отличие от массива, односвязные списки не имеют индексов, поэтому единственный способ поиска или доступа к данным — начать с головы и пройти по каждому узлу. Это может быть крайне неэффективно.
Однако вставка и удаление данных из односвязного списка эффективны, поскольку вам не нужно устанавливать новые индексы для каждого узла.
Нотация Big O для односвязных списков
- Вставка — О(1)
- Удаление — O(1) или O(N)
- Поиск — O(N)
- Доступ — О(Н)
Создание односвязного списка
Прежде всего, мы определим класс для создания узла. Он принимает значение и устанавливает следующее свойство равным null.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
Далее мы определим класс односвязного списка. У него будет указатель на голову, указатель на хвост и длину. Длина будет инициализирована как 0, а начало и конец будут нулевыми. В следующих разделах мы добавим в этот класс методы для обработки различных функций. Каждый метод имеет несколько крайних случаев (например, если длина равна 0 и т. д.), поэтому см. код для проверки различных случаев.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
Добавление узла в конец связанного списка
Первый метод, который мы определим, это push. Push добавит новый узел в конец связанного списка. Он принимает значение, и мы создадим новый узел с этим значением. Следующее свойство текущего хвоста будет установлено на новый узел, а свойство хвоста списка будет установлено на новый узел. Длина также будет увеличена на единицу, и мы вернем список в конце.
push(val) {
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
Удаление узла из конца связанного списка
Второй метод, который мы определим, это pop. Pop удалит узел из конца связанного списка. Прежде чем мы удалим последний узел, нам сначала нужно найти предпоследний узел, потому что нам нужно установить его как новый хвост. Для этого нам нужно пройтись по списку в цикле, затем установить свойство next второго и последнего узла равным null и, наконец, установить конец связанного списка, чтобы он был от второго до последнего узла. Наконец, уменьшите длину на единицу и верните значение удаленного узла.
pop() {
if (!this.head) return undefined;
let current = this.head;
let newTail = current;
while (current.next) {
newTail = current;
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
Удаление узла из начала связанного списка
Третий метод, который мы определим, — это сдвиг. Это удалит узел из начала связанного списка. Все, что нам нужно сделать, это установить следующее свойство текущей головы как новую голову, уменьшить длину на 1 и вернуть удаленный узел.
shift() {
if (!this.head) return undefined;
let currentHead = this.head;
this.head = currentHead.next;
this.length--;
if (this.length === 0) {
this.tail = null;
}
return currentHead;
}
Добавление узла в начало связанного списка
Последний метод, который мы определим, — unshift. Это добавит узел в начало связанного списка. Метод unshift примет значение, и мы сначала создадим новый узел с этим значением. Затем мы установим следующее свойство нового узла в качестве текущего заголовка, а затем установим свойство заголовка связанного списка в качестве нового узла. Наконец, мы увеличим длину на единицу и вернем связанный список.
unshift(val) {
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
Окончательный код будет выглядеть примерно так.
Спасибо, что прочитали! Если вам интересно узнать больше, я рекомендую ознакомиться с курсом Colt Steele Udemy Мастер-класс по алгоритмам JavaScript и структурам данных.
Посмотрите вторую часть серии, в которой мы развиваем этот список, и я научу вас, как реверсировать односвязный список с помощью JavaScript.
Скоро появятся другие статьи.
- Построение двусвязного списка с помощью JavaScript
- Построение двоичного дерева поиска с помощью JavaScript
- Стеки и очереди с JavaScript
- Построение хеш-таблицы с помощью JavaScript
- Построение графика с помощью JavaScript
