☕ Распространенные алгоритмы и структуры данных в JavaScript: стеки, очереди и связные списки

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

1. углубишься в решение практических задач;
2. узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.

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

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

Другие статьи цикла:

• Часть 1. Основные понятия и работа с массивами
• Часть 3. Деревья
• Часть 4. Графы
  
• Часть 5. Объекты и хеширование
  
• Часть 6. Полезные алгоритмы для веб-разработки
  

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

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

В ряде языков программирования необходимо указывать размер массива при его создании, и потом его нельзя изменить. Связные списки помогают решить эту проблему для создания динамических коллекций. В 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);
    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;
  }
}
    

Обход списка

Его реализация очень проста – начать с головы и двигаться по цепочке ссылок 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) элементы коллекции прямо из узла, чтобы не привязываться к их индексам.

Стек

Стек – это коллекция элементов, организованная по принципу 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).

Очередь

Очередь – это еще один вид коллекции элементов, но работает он по другому принципу – 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-статусом.

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

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

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

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

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

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

Заключение

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