Распространенные алгоритмы и структуры данных в JavaScript: стеки, очереди и связные списки |
||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2022-09-23 15:00 Продолжая серию статей об алгоритмах и структурах данных в JavaScript, рассмотрим другие линейные (массивоподобные) структуры – стеки, очереди и связные списки. Связный список Связный список – это последовательность отдельных узлов, каждый из которых содержит данные, а также ссылку на следующий узел. Таким образом, все узлы последовательно связаны друг с другом. Отличие от массива Список – более гибкая структура, чем массив. Он позволяет быстрее и удобнее добавлять и удалять элементы в любом месте структуры. В ряде языков программирования необходимо указывать размер массива при его создании, и потом его нельзя изменить. Связные списки помогают решить эту проблему для создания динамических коллекций. В JavaScript такого нет, но, тем не менее, знать об этом полезно, так как на более низких уровнях абстракции (более близких к машинном коду) все работает примерно одинаково. Недостатком списка (в сравнении с массивами) является невозможность прямого доступа к конкретному элементу. Отсюда вытекает разное практическое использование этих структур данных. Массивы полезны, если приходится чаще получать данные, а связные списки, если чаще нужно добавлять/удалять элементы. Сложность базовых операций Реализация в JavaScript Реализуем связный список в виде класса с методами для основных операций:
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); 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; } } }
Для удобства можно также добавить в класс отдельные методы для удаления головы или хвоста списка. 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; } } Обход списка В класс связного списка можно добавить еще несколько полезных методов. Например, аналог Его реализация очень проста – начать с головы и двигаться по цепочке ссылок next, выполняя для каждого узла функцию-коллбэк. 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; } } При необходимости можно немного переделать реализацию и передавать в метод Разновидности связных списков Двусвязный список В этом варианте каждый узел имеет ссылку не только на следующий элемент списка ( Кольцевой связный список Односвязный и двусвязный список может быть замкнутым (циклическим). При этом хвост содержит указатель на голову, а голова – на хвост (если список двусвязный). Зачем в JavaScript использовать списки, если есть массивы? Хороший вопрос. Если речь идет о производительности, то принципиального смысла в этом нет. Массивы – это встроенный модуль, напичканный всевозможными оптимизациями, поэтому преимущества написанного вручную связного списка уже не кажутся существенными. Однако, интерфейс этой структуры представляет интерес. Например, может быть удобно получать ссылки на предыдущий ( Стек Стек – это коллекция элементов, организованная по принципу LIFO (последним пришел – первым вышел). В реальном мире примером стека является стопка тарелок: новые мы кладем наверх стопки и сверху же начинаем забирать. Элемент, пришедший последним и первый на выход, обычно называется головным, то есть голова у стека фактически находится в хвосте. У стеков есть три основные операции:
Реализация в JavaScript Стек может быть реализован на базе массива или однонаправленного списка. В JavaScript массивы фактически являются стеками, так как уже предоставляют методы 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; } Стек в данном случае – это просто обертка над связным списком, использующая его методы. Примеры использования Стек в программировании – очень важная структура. Он, например, используется для парсинга, транспиляции, обхода древоподобных структур данных, а также для выполнения рекурсивных функций (стек вызовов, или Call Stack). В приложениях на JavaScript стеки тоже часто используются. Очень популярный кейс – реализация истории изменений с возможностью отмены последнего действия. Очередь Очередь – это еще один вид коллекции элементов, но работает он по другому принципу – FIFO (первым пришел – первым вышел). Это буквально очередь, такая же, как та, в которой вы стоите, когда хотите купить билеты в кассе кинотеатра. Основные операции очереди:
Реализация в JavaScript Как и стек, очередь может быть реализована как на базе массива, так и на базе связного списка. И опять же, массивы в JavaScript фактически могут работать как очереди, благодаря встроенным методам Реализуем очередь на основе связного списка: 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; } } Очередь очень похожа по реализации на стек за исключением того, что новые элементы добавляются в хвост связного списка (в стеке добавление происходит со стороны головы). Примеры использования Применение для очереди в JavaScript найти нетрудно. Сам язык использует очередь для обработки поступающих событий. Мы можем по аналогии выстраивать в очередь различные коллбэки для обработки данных. Очередь с приоритетом Это разновидность очереди, в которой некоторые элементы обладают VIP-статусом. Каждый элемент в такой очереди имеет приоритет. Первыми будут обрабатываться элементы с высоким приоритетом, независимо от того, когда они были добавлены. У такой очереди две основные операции:
Очередь с приоритетом – это более сложная структура, чем обычная очередь, и реализуется обычно по-другому – на основе структуры данных куча, о которой мы поговорим в следующей статье цикла. Сложность базовых операций в стеках и очередях Очевидно, что сложность операций зависит от того, на базе какой структуры реализованы стек или очередь. В массивах проще получить доступ к элементу, а в связных списках изменять количество. Заключение Сначала мы изучили основы, а сегодня сравнили четыре очень похожих линейных структуры данных: массивы, связные списки, стеки и очереди. Какую из них выбрать выбрать, зависит от конкретной задачи. Учитывайте размер коллекции, с которой работаете, специфику добавления и удаления элементов, а также частоту обращения к случайным элементам внутри коллекции. Выбирая, обращайте внимание как на эффективность структуры данных, так и на удобство ее интерфейса. Источник: m.vk.com Комментарии: |
|