☕ Распространенные алгоритмы и структуры данных в JavaScript: стеки, очереди и связные списки
Продолжая серию статей об алгоритмах и структурах данных в JavaScript, рассмотрим другие линейные (массивоподобные) структуры – стеки, очереди и связные списки. В первой части цикла мы познакомились с основными подходами к решению задач, а также реализовали несколько алгоритмов для массивов. В очередной статье продолжим работать с линейными структурами данных. На очереди связные списки, стеки и – простите за каламбур – очереди. Связный список – это последовательность отдельных узлов, каждый из которых содержит данные, а также ссылку на следующий узел. Таким образом, все узлы последовательно связаны друг с другом. Принципиальная схема связного списка Отличие от массива Список – более гибкая структура, чем массив. Он позволяет быстрее и удобнее добавлять и удалять элементы в любом месте структуры. В ряде языков программирования необходимо указывать размер массива при его создании, и потом его нельзя изменить. Связные списки помогают решить эту проблему для создания динамических коллекций. В JavaScript такого нет, но, тем не менее, знать об этом полезно, так как на более низких уровнях абстракции (более близких к машинном коду) все работает примерно одинаково. Недостатком списка (в сравнении с массивами) является невозможность прямого доступа к конкретному элементу. Отсюда вытекает разное практическое использование этих структур данных. Массивы полезны, если приходится чаще получать данные, а связные списки, если чаще нужно добавлять/удалять элементы. Реализуем связный список в виде класса с методами для основных операций: Для удобства можно также добавить в класс отдельные методы для удаления головы или хвоста списка. В класс связного списка можно добавить еще несколько полезных методов. Например, аналог Его реализация очень проста – начать с головы и двигаться по цепочке ссылок next, выполняя для каждого узла функцию-коллбэк. Можно даже реализовать обратный обход списка, начиная с хвоста. Иногда это может быть полезным: Для этого нам нужна вспомогательная функция, которая будет рекурсивно вызываться для каждого узла списка по порядку. Так как сначала происходит рекурсивный вызов и только затем выполняется коллбэк, сначала он сработает для последнего элемента в цепочке. Чтобы найти нужный элемент в списке, нужно последовательно перебирать его узлы, начиная с головы, и сравнивать их значения с искомым. При необходимости можно немного переделать реализацию и передавать в метод В этом варианте каждый узел имеет ссылку не только на следующий элемент списка ( Принципиальная схема двусвязкного списка Кольцевой связный список Односвязный и двусвязный список может быть замкнутым (циклическим). При этом хвост содержит указатель на голову, а голова – на хвост (если список двусвязный). Хороший вопрос. Если речь идет о производительности, то принципиального смысла в этом нет. Массивы – это встроенный модуль, напичканный всевозможными оптимизациями, поэтому преимущества написанного вручную связного списка уже не кажутся существенными. Однако, интерфейс этой структуры представляет интерес. Например, может быть удобно получать ссылки на предыдущий ( • Обсуждение на StackOverflow: Вы когда-нибудь писали связные списки на JavaScript? Стек – это коллекция элементов, организованная по принципу LIFO (последним пришел – первым вышел). В реальном мире примером стека является стопка тарелок: новые мы кладем наверх стопки и сверху же начинаем забирать. Элемент, пришедший последним и первый на выход, обычно называется головным, то есть голова у стека фактически находится в хвосте. Принципиальная схема работы стека У стеков есть три основные операции: Стек может быть реализован на базе массива или однонаправленного списка. В JavaScript массивы фактически являются стеками, так как уже предоставляют методы Стек в данном случае – это просто обертка над связным списком, использующая его методы. Стек в программировании – очень важная структура. Он, например, используется для парсинга, транспиляции, обхода древоподобных структур данных, а также для выполнения рекурсивных функций (стек вызовов, или Call Stack). В приложениях на JavaScript стеки тоже часто используются. Очень популярный кейс – реализация истории изменений с возможностью отмены последнего действия. Очередь – это еще один вид коллекции элементов, но работает он по другому принципу – FIFO (первым пришел – первым вышел). Это буквально очередь, такая же, как та, в которой вы стоите, когда хотите купить билеты в кассе кинотеатра. Принципиальная схема работы очереди Основные операции очереди: Как и стек, очередь может быть реализована как на базе массива, так и на базе связного списка. И опять же, массивы в JavaScript фактически могут работать как очереди, благодаря встроенным методам Реализуем очередь на основе связного списка: Очередь очень похожа по реализации на стек за исключением того, что новые элементы добавляются в хвост связного списка (в стеке добавление происходит со стороны головы). Применение для очереди в JavaScript найти нетрудно. Сам язык использует очередь для обработки поступающих событий. Мы можем по аналогии выстраивать в очередь различные коллбэки для обработки данных. Это разновидность очереди, в которой некоторые элементы обладают VIP-статусом. Каждый элемент в такой очереди имеет приоритет. Первыми будут обрабатываться элементы с высоким приоритетом, независимо от того, когда они были добавлены. У такой очереди две основные операции: Очередь с приоритетом – это более сложная структура, чем обычная очередь, и реализуется обычно по-другому – на основе структуры данных куча, о которой мы поговорим в следующей статье цикла. Очевидно, что сложность операций зависит от того, на базе какой структуры реализованы стек или очередь. В массивах проще получить доступ к элементу, а в связных списках изменять количество. Сначала мы изучили основы, а сегодня сравнили четыре очень похожих линейных структуры данных: массивы, связные списки, стеки и очереди. Какую из них выбрать выбрать, зависит от конкретной задачи. Учитывайте размер коллекции, с которой работаете, специфику добавления и удаления элементов, а также частоту обращения к случайным элементам внутри коллекции. Выбирая, обращайте внимание как на эффективность структуры данных, так и на удобство ее интерфейса. В следующей части мы подробно разберем очень интересную структуру данных – дерево, а также рассмотрим связанные с этой структурой алгоритмы.Связный список
Сложность базовых операций
Массив
Связный список
Получение элемента
1 (константное время, не зависит от кол-ва элементов)
n (нужно перебрать все предыдущие элементы)
Вставка в конец
1
1
Вставка в начало
n
1
Удаление из конца
1
1
Удаление из начала
n
1
Реализация в JavaScript
prepend
– добавление нового элемента в начало списка;append
– добавление нового элемента в конец списка;delete
– удаление всех элементов с указанным значением.
class LinkedListNode { constructor(value, next = null) { this.value = value; this.next = next; } } class LinkedList { constructor(comparator) { this.head = null; this.tail = null; this.comparator = comparator || function (i, j) { if (i < j) return -1; if (i > j) return 1; return 0; }; } prepend(value) { let newNode = new LinkedListNode(value, this.head); this.head = newNode; if (!this.tail) this.tail = newNode; } append(value) { let newNode = new LinkedListNode(value, this.head); if (this.tail) this.tail.next = newNode; this.tail = newNode; if (!this.head) this.head = newNode; } delete(value) { if (!this.head) return; // если удаляется голова списка, // нужно обозначить новую голову while (this.head && this.comparator(this.head.value, value) === 0) { this.head = this.head.next; } let current = this.head; if (current !== null) { while (current.next) { if (this.comparator(current.next.value, value) === 0) { current.next = current.next.next; } else { current = current.next; } } } if (this.comparator(this.tail.value, value) === 0) { this.tail = current; } } }
LinkedList
принимает в качестве аргумента функцию-компаратор, которая необходима для поиска нужного элемента. Если ее нет, то реализует дефолтную функцию сравнения.head
) и хвост (tail
) списка, которые обновляются при необходимости, например, если добавляется новый элемент.next
) и не допускать разрывов списка.
class LinkedList { // … deleteHead() { if (!this.head) return null; let deletedHead = this.head; if (this.head.next) { this.head = this.head.next; } else { this.head = null; this.tail = null; } return deletedHead; } deleteTail() { const deletedTail = this.tail; if (this.head === this.tail) { this.head = null; this.tail = null; return deletedTail; } // найти предпоследний элемент списка // и сделать его новым хвостом let current = this.head; while (current.next) { if (!current.next.next) { current.next = null; } else { current = current.next; } } this.tail = current; return deletedTail; } }
Обход списка
Array.prototype.forEach
для последовательного обхода всех узлов списка.
class LinkedList { // … forEach(callback) { let current = this.head; while (current) { callback(current.value); current = current.next; } } }
class LinkedList { // … reverseForEach(callback) { function tick(node) { if (node) { tick(node.next); callback(node.value); } } tick(this.head); } }
Поиск в списке
class LinkedList { // … find(value) { if (!this.head) return null; let current = this.head; while (current) { if (this.comparator(current.value, value) === 0) { return current; } current = current.next; } return null; } }
find
не значение, а функцию для сравнения, как мы делаем это с методом Array.prototype.find
.Разновидности связных списков
Двусвязный список
next
), но и на предыдущий. Это облегчает обход в обратном направлении, но требует большего количества операций при каждом изменении списка.Зачем в JavaScript использовать списки, если есть массивы?
prev
) и следующий (next
) элементы коллекции прямо из узла, чтобы не привязываться к их индексам.Стек
push
);pop
);peek
).Реализация в JavaScript
push
и pop
, поэтому нет необходимости реализовывать стек вручную. Но мы все же попробуем для интереса создать класс Stack
на основе написанного в прошлом разделе класса LinkedList
(Связный список).
class Stack { constructor() { this.linkedList = new LinkedList(); } isEmpty() { return !this.linkedList.head; } peek() { if (this.isEmpty()) { return null; } return this.linkedList.head.value; } push(value) { this.linkedList.prepend(value); } pop() { const removedHead = this.linkedList.deleteHead(); return removedHead ? removedHead.value : null; }
Примеры использования
Очередь
enqueue
);dequeue
);peek
).Реализация в JavaScript
Array.prototype.push
и Array.prototype.unshift
.
class Queue { constructor() { this.linkedList = new LinkedList(); } isEmpty() { return !this.linkedList.head; } peek() { if (!this.linkedList.head) { return null; } return this.linkedList.head.value; } enqueue(value) { this.linkedList.append(value); } dequeue() { const removedHead = this.linkedList.deleteHead(); return removedHead ? removedHead.value : null; } }
Примеры использования
Очередь с приоритетом
Сложность базовых операций в стеках и очередях
Получение
Добавление
Удаление
Стек на основе массива
1
1 (Array.push)
1 (Array.pop)
Стек на основе списка
n
1 (LinkedList.prepend)
1 (LinkedList.deleteHead)
Очередь на основе массива
1
1 (Array.push)
n (Array.unshift)
Очередь на основе списка
n
1 (LinkedList.append)
1 (LinkedList.deleteHead)
Заключение
- 3 views
- 0 Comment
Свежие комментарии