Продолжая серию статей об алгоритмах и структурах данных в JavaScript, рассмотрим другие линейные (массивоподобные) структуры – стеки, очереди и связные списки.

В первой части цикла мы познакомились с основными подходами к решению задач, а также реализовали несколько алгоритмов для массивов.

В очередной статье продолжим работать с линейными структурами данных. На очереди связные списки, стеки и – простите за каламбур – очереди.

Связный список

Связный список – это последовательность отдельных узлов, каждый из которых содержит данные, а также ссылку на следующий узел. Таким образом, все узлы последовательно связаны друг с другом.

Принципиальная схема связного списка Отличие от массива Список – более гибкая структура, чем массив. Он позволяет быстрее и удобнее добавлять и удалять элементы в любом месте структуры.

В ряде языков программирования необходимо указывать размер массива при его создании, и потом его нельзя изменить. Связные списки помогают решить эту проблему для создания динамических коллекций. В JavaScript такого нет, но, тем не менее, знать об этом полезно, так как на более низких уровнях абстракции (более близких к машинном коду) все работает примерно одинаково.

Недостатком списка (в сравнении с массивами) является невозможность прямого доступа к конкретному элементу.

Отсюда вытекает разное практическое использование этих структур данных. Массивы полезны, если приходится чаще получать данные, а связные списки, если чаще нужно добавлять/удалять элементы.

Сложность базовых операций

Реализация в 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 для последовательного обхода всех узлов списка.

Его реализация очень проста – начать с головы и двигаться по цепочке ссылок 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;   } }     

При необходимости можно немного переделать реализацию и передавать в метод find не значение, а функцию для сравнения, как мы делаем это с методом Array.prototype.find.

Разновидности связных списков

Двусвязный список

В этом варианте каждый узел имеет ссылку не только на следующий элемент списка (next), но и на предыдущий. Это облегчает обход в обратном направлении, но требует большего количества операций при каждом изменении списка.

Принципиальная схема двусвязкного списка Кольцевой связный список Односвязный и двусвязный список может быть замкнутым (циклическим). При этом хвост содержит указатель на голову, а голова – на хвост (если список двусвязный).

Зачем в JavaScript использовать списки, если есть массивы?

Хороший вопрос.

Если речь идет о производительности, то принципиального смысла в этом нет. Массивы – это встроенный модуль, напичканный всевозможными оптимизациями, поэтому преимущества написанного вручную связного списка уже не кажутся существенными.

Однако, интерфейс этой структуры представляет интерес. Например, может быть удобно получать ссылки на предыдущий (prev) и следующий (next) элементы коллекции прямо из узла, чтобы не привязываться к их индексам.

• Обсуждение на StackOverflow: Вы когда-нибудь писали связные списки на JavaScript?

Стек

Стек – это коллекция элементов, организованная по принципу LIFO (последним пришел – первым вышел). В реальном мире примером стека является стопка тарелок: новые мы кладем наверх стопки и сверху же начинаем забирать.

Элемент, пришедший последним и первый на выход, обычно называется головным, то есть голова у стека фактически находится в хвосте.

Принципиальная схема работы стека

У стеков есть три основные операции:

• добавление нового элемента (push);
• удаление головного элемента (pop);
• чтение головного элемента без удаления (peek).

Реализация в JavaScript

Стек может быть реализован на базе массива или однонаправленного списка.

В 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;  }      

Стек в данном случае – это просто обертка над связным списком, использующая его методы.

Примеры использования

Стек в программировании – очень важная структура. Он, например, используется для парсинга, транспиляции, обхода древоподобных структур данных, а также для выполнения рекурсивных функций (стек вызовов, или Call Stack).

В приложениях на JavaScript стеки тоже часто используются. Очень популярный кейс – реализация истории изменений с возможностью отмены последнего действия.

Очередь

Очередь – это еще один вид коллекции элементов, но работает он по другому принципу – FIFO (первым пришел – первым вышел). Это буквально очередь, такая же, как та, в которой вы стоите, когда хотите купить билеты в кассе кинотеатра.

Принципиальная схема работы очереди

Основные операции очереди:

• добавление нового элемента в конец очереди (enqueue);
• удаление элемента из начала очереди (dequeue);
• чтение элемента из начала очереди без удаления (peek).

Реализация в JavaScript

Как и стек, очередь может быть реализована как на базе массива, так и на базе связного списка. И опять же, массивы в 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;   } }      

Очередь очень похожа по реализации на стек за исключением того, что новые элементы добавляются в хвост связного списка (в стеке добавление происходит со стороны головы).

Примеры использования

Применение для очереди в JavaScript найти нетрудно. Сам язык использует очередь для обработки поступающих событий. Мы можем по аналогии выстраивать в очередь различные коллбэки для обработки данных.

Очередь с приоритетом

Это разновидность очереди, в которой некоторые элементы обладают VIP-статусом.

Каждый элемент в такой очереди имеет приоритет. Первыми будут обрабатываться элементы с высоким приоритетом, независимо от того, когда они были добавлены.

У такой очереди две основные операции:

• добавить новый элемент в конец;
• извлечь элемент с максимальным приоритетом.

Очередь с приоритетом – это более сложная структура, чем обычная очередь, и реализуется обычно по-другому – на основе структуры данных куча, о которой мы поговорим в следующей статье цикла.

Сложность базовых операций в стеках и очередях

Очевидно, что сложность операций зависит от того, на базе какой структуры реализованы стек или очередь. В массивах проще получить доступ к элементу, а в связных списках изменять количество.

Заключение

Сначала мы изучили основы, а сегодня сравнили четыре очень похожих линейных структуры данных: массивы, связные списки, стеки и очереди. Какую из них выбрать выбрать, зависит от конкретной задачи. Учитывайте размер коллекции, с которой работаете, специфику добавления и удаления элементов, а также частоту обращения к случайным элементам внутри коллекции. Выбирая, обращайте внимание как на эффективность структуры данных, так и на удобство ее интерфейса.

В следующей части мы подробно разберем очень интересную структуру данных – дерево, а также рассмотрим связанные с этой структурой алгоритмы.