Как создавать структуры данных с помощью классов JavaScript ES6
Структуры данных – фундаментальный аспект информатики и программирования, независимо от того, какой язык вы используете. Их глубокое знание может помочь вам эффективно организовывать, управлять, хранить и изменять данные. Определение правильной структуры данных для вашего варианта использования может значительно повысить производительность.
Однако по умолчанию JavaScript поставляется только с примитивными структурами данных, такими как массивы и объекты. Но с появлением классов ECMAScript 6 (ES6) теперь вы можете создавать собственные структуры данных, такие как стеки и очереди, с помощью примитивных структур данных.
Структура данных стека
Структура данных стека позволяет вам помещать новые данные поверх существующих данных в режиме LIFO (последний пришел, первый ушел). Эту линейную структуру данных легко визуализировать на простом примере. Представьте себе стопку тарелок на столе. Вы можете добавить или удалить тарелку только из верхней части стопки.
Вот как можно реализовать структуру данных стека с помощью массивов JavaScript и классов ES6 :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Давайте исследуем и построим некоторые операции, которые вы можете выполнять со стеком.
Нажать операцию
Операция push используется для вставки новых данных в стек. Вам необходимо передать данные в качестве параметра при вызове метода push. Перед вставкой данных верхний указатель стека увеличивается на единицу, а новые данные вставляются в верхнюю позицию.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Поп-операция
Операция pop используется для удаления самого верхнего элемента данных стека. При выполнении этой операции верхний указатель уменьшается на 1.
pop() {
if (this.top < 0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Подглядывать за операцией
Операция просмотра используется для возврата значения, находящегося в верхней части стека. Сложность извлечения этих данных составляет O (1).
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Структура данных связанного списка
Связанный список – это линейная структура данных, состоящая из множества узлов, связанных друг с другом с помощью указателей. Каждый узел в списке содержит данные и переменную-указатель, которая указывает на следующий узел в списке.
В отличие от стека, реализации связанного списка в JavaScript требуют двух классов. Первый класс – это класс Node для создания узла, а второй класс – это класс LinkedList для выполнения всех операций со связанным списком. Указатель заголовка указывает на первый узел связанного списка, а указатель хвоста указывает на последний узел связанного списка.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}Вот некоторые основные операции, которые вы можете выполнять со связанным списком:
Добавить операцию
Операция добавления используется для добавления нового узла в конец связанного списка. Вы должны передать данные в качестве параметра для вставки нового узла. Во-первых, создайте новый объект узла, используя ключевое слово new в JavaScript.
Если связанный список пуст, указатели головы и хвоста будут указывать на новый узел. В противном случае только указатель хвоста будет указывать на новый узел.
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
return this;
}Вставить операцию
Чтобы вставить новый узел по определенному индексу, вы можете использовать операцию вставки. Этот метод принимает два параметра: данные для вставки и индекс, по которому они должны быть вставлены. В худшем случае этот метод имеет временную сложность O (N), так как он может пройти через весь список.
insert(data, index) {
if (index < 0 || index > this.size) return undefined;
if (index === 0) {
this.head = new Node(data, this.head);
!this.tail ? (this.tail = this.head) : null;
this.size++;
return this;
}
if (index === this.size) return this.append(data);
let count = 0;
let beforeNode = this.head;
while (count !== index) {
beforeNode = beforeNode.next;
count++;
}
const newNode = new Node(data);
let afterNode = beforeNode.next;
newNode.next = afterNode;
beforeNode.next = newNode;
this.size++;
return this;
}Удалить операцию
Операция удаления проходит через связанный список, чтобы получить ссылку на узел, который должен быть удален, и удаляет ссылку на предыдущий узел. Подобно операции вставки, операция удаления также имеет временную сложность O (N) в худшем случае.
deleteNode(index) {
if (index === 0) {
const removedHead = this.head;
this.head = this.head.next;
this.size--;
this.size === 0 ? (this.tail = null) : null;
return removedHead;
}
if (index === this.size - 1) {
if (!this.head) return undefined;
let currentNode = this.head;
let newTail = currentNode;
while (currentNode.next) {
newTail = currentNode;
currentNode = currentNode.next;
}
this.tail = newTail;
this.tail.next = null;
this.size--;
this.size === 0 ? ([this.head, this.tail] = [null, null]) : null;
return currentNode;
}
if (index < 0 || index > this.size - 1) return undefined;
let count = 0;
let beforeNode = this.head;
while (count !== index - 1) {
beforeNode = beforeNode.next;
count++;
}
const removedNode = beforeNode.next;
let afterNode = removedNode.next;
beforeNode.next = afterNode;
removedNode.next = null;
this.size--;
return removedNode;
}Структура данных очереди
Структура данных очереди похожа на группу людей, стоящих в очереди. Человек, который первым встает в очередь, обслуживается раньше остальных. Точно так же эта линейная структура данных следует подходу FIFO (first in, first out) для вставки и удаления данных. Эту структуру данных можно воссоздать в JavaScript, используя связанный список следующим образом:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}Вот как вы можете вставлять и удалять данные из очереди в JavaScript:
Операция постановки в очередь
Операция постановки в очередь вставляет новые данные в очередь. При вызове этого метода, если структура данных очереди пуста, передний и задний указатели указывают на вновь вставленный узел в очереди. Если очередь не пуста, новый узел добавляется в конец списка, и задний указатель указывает на этот узел.
enqueue(data) {
const newNode = new Node(data);
if (!this.front) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
return this;
}Dequeue Operation
Операция удаления из очереди удаляет первый элемент в очереди. Во время операции удаления из очереди указатель заголовка перемещается вперед ко второму узлу в списке. Этот второй узел теперь становится главой очереди.
dequeue() {
if (!this.front) return undefined;
if (this.front === this.rear) this.rear = null;
const dequeuedNode = this.front;
this.front = this.front.next;
this.size--;
return dequeuedNode;
}Следующий шаг после структур данных
Структуры данных могут быть сложной задачей для понимания, особенно если вы новичок в программировании. Но, как и любой другой навык, практика может помочь вам по-настоящему понять и оценить эффективность, которую он обеспечивает для хранения и управления данными в ваших приложениях.
Алгоритмы так же полезны, как и структуры данных, и могут стать следующим логическим шагом на вашем пути к программированию. Итак, почему бы не начать с алгоритма сортировки, такого как пузырьковая сортировка?