В мире frontend есть проблема: многие разработчики плохо ориентируются в структурах данных и не умеют их грамотно применять, чтобы получать эффективные и производительные решения своих задач.

Мы, Руслан Мирзоев и Тимофей Соломенников, разработчики онлайн-кинотеатра PREMIER, хотим поделиться своим опытом и на реальных примерах показать, что даёт правильное использование структур данных.

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

Вот какие структуры данных мы рассмотрим в этой статье: связный список, стек, очередь, дерево, граф, множество, массив, карта.

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

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

• реализации навигации в плеере, где связный список позволяет легко перемещаться между треками, добавлять и удалять их из плейлиста;

• редактора, поддерживающего операции отмены и возврата действий (undo-redo), таких как текстовый редактор Word или графический редактор Figma, где связные списки помогают эффективно управлять историей изменений.

Когда использовать?

Преимущество связного списка заключается в том, что удаление элемента выполняется за константное время O(1). В то время как в массиве для удаления элемента необходимо не только удалить сам элемент, но и сдвинуть все последующие элементы. В связном списке достаточно изменить ссылки prev и next у соответствующих нод.

Особенности

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

Решение проблемы сборки мусора: можно использовать слабые ссылки (Weak References) — они позволяют сборщику мусора удалять объекты, на которые они указывают, даже если на эти объекты существуют другие слабые ссылки. Это помогает избежать утечек памяти, связанных с кольцевыми зависимостями.

Пример использования связного списка #1. Музыкальный плеер

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

Покликать самостоятельно — здесь, исходный код всего примера — в репозитории.

export class LinkedListNode<T> {
  value: T;
  next: LinkedListNode<T> | null;
  prev: LinkedListNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}


export class DoublyLinkedList<T> {
  head: LinkedListNode<T> | null;
  tail: LinkedListNode<T> | null;
  current: LinkedListNode<T> | null;

  constructor() {
    this.head = null;
    this.tail = null;
    this.current = null;
  }

  add(value: T): void {
    const newNode = new LinkedListNode(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      this.current = newNode;
    } else {
      if (this.tail) {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
      }
    }
  }

  removeCurrent(): void {
    if (!this.current) return;

    if (this.current.prev) {
      this.current.prev.next = this.current.next;
    } else {
      this.head = this.current.next;
    }

    if (this.current.next) {
      this.current.next.prev = this.current.prev;
    } else {
      this.tail = this.current.prev;
    }

    this.current = this.current.next || this.current.prev || null;
  }

  next(): void {
    if (this.current && this.current.next) {
      this.current = this.current.next;
    } else {
      this.current = this.head;
    }
  }

  prev(): void {
    if (this.current && this.current.prev) {
      this.current = this.current.prev;
    } else {
      this.current = this.tail;
    }
  }
}

Пример использования связного списка #2. Графический редактор

В редакторе можно что-то нарисовать, отменить, вернуть отменённое назад — всё это с помощью списка.

Демка редактора с undo и redo— здесь, исходный код примера— здесь.

class Node<T> {
  data: T;
  next: Node<T> | null = null;
  prev: Node<T> | null = null;

  constructor(data: T) {
    this.data = data;
  }
}

export class LinkedList<T> {
  private head: Node<T> | null = null;
  private current: Node<T> | null = null;

  add(data: T): void {
    const newNode = new Node(data);

    if (!this.head) {
      this.head = newNode;
      this.current = this.head;
    } else if (this.current) {
      this.current.next = newNode;
      newNode.prev = this.current;
      this.current = newNode;
    }
  }

  undo(): T | null {
    if (this.current && this.current.prev) {
      this.current = this.current.prev;
      return this.current.data;
    }
    return null;
  }

  redo(): T | null {
    if (this.current && this.current.next) {
      this.current = this.current.next;
      return this.current.data;
    }
    return null;
  }

  canUndo(): boolean {
    return !!this.current && !!this.current.prev;
  }

  canRedo(): boolean {
    return !!this.current && !!this.current.next;
  }

  getCurrentData(): T | null {
    return this.current ? this.current.data : null;
  }
}

Стек

Стек — это структура данных, работающая по принципу LIFO (Last In, First Out), что означает, что последний добавленный элемент будет первым извлечён. Во frontend-разработке стек полезен для управления историей навигации или для валидации данных.

Когда использовать?

Когда требуется управление состоянием или выполнение операций по принципу «последний пришёл — первый вышел» (LIFO).

Особенности

• Ограниченный доступ — доступен только последний элемент).

• Ограниченная функциональность — не подойдет, когда нужен доступ до определенного элемента.

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

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

Представим ситуацию, есть два модальных окна:

• модальное окно удаления аккаунта, которое открывается по кнопке;

• модальное окно подтверждения удаления аккаунта, которое открывается после нажатия на кнопку в первом модальном окне.

Мы хотим написать код, чтобы при нажатии на клавишу Esc или при клике вне области модального окна оно закрывалось. При обычной реализации — если на обеих модальных окнах стоит обработчик закрытия по нажатию Esc — они закроются одновременно. Решение заключается в том, чтобы складывать модальные окна в Stack. Тогда при нажатии на Esc удалится последний элемент из стека, в котором содержатся обе модалки. Выглядеть будет так:

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

export class Stack<T> {
  private items: T[] = []

  push(item: T): void {
    this.items.push(item)
  }

  pop(): T | undefined {
    return this.items.pop()
  }

  getItems(): T[] {
    return [...this.items]
  }

  size(): number {
    return this.items.length
  }

  get(index: number): T | undefined {
    if (index >= 0 && index < this.items.length) {
      return this.items[index]
    }
    return undefined
  }

  isEmpty(): boolean {
    return this.items.length === 0
  }
}

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

Очередь

Очередь — это структура данных, работающая по принципу FIFO (First In, First Out), что означает, что первый добавленный элемент будет первым извлечён.

Когда использовать?

Когда нужно следовать принципу «первый пришёл — первый вышел» (FIFO, First In First Out), например, по порядку обрабатывать входящие уведомления.

Особенности

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

Пример использования очереди #1. Загрузка файлов

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

Подробнее посмотреть на пример и протестировать демореализацию можно здесь.

class Queue<T> {
  protected items: T[] = []

  enqueue(item: T): void {
    this.items.push(item)
  }

  dequeue(): T | undefined {
    return this.items.shift()
  }

  peek(): T | undefined {
    return this.items[0]
  }

  isEmpty(): boolean {
    return this.items.length === 0
  }

  size(): number {
    return this.items.length
  }

  getItems(): T[] {
    return [...this.items]
  }

  clear(): void {
    this.items = []
  }
}

export type UploadItem = {
  id: string
  file: File
  status: 'pending' | 'uploading' | 'done'
  progress: number
}
type UploadCallback = (item: UploadItem, markDone: () => void) => void

export class UploadQueue extends Queue<UploadItem> {
  private isUploading = false
  private onUpload: UploadCallback

  constructor(onUpload: UploadCallback) {
    super()
    this.onUpload = onUpload
  }

  enqueueFile(file: File): UploadItem {
    const item: UploadItem = {
      id: `${Date.now()}-${Math.random()}`,
      file,
      status: 'pending',
      progress: 0,
    }
    super.enqueue(item)
    this.tryUploadNext()
    return item
  }

  getAllItems(): UploadItem[] {
    return super.getItems()
  }

  private tryUploadNext() {
    if (this.isUploading) return

    const next = this.getItems().find((item) => item.status === 'pending')
    if (!next) return

    this.isUploading = true
    next.status = 'uploading'

    this.onUpload(next, () => {
      next.status = 'done'
      this.isUploading = false
      this.tryUploadNext()
    })
  }
}

Пример использования очереди #2. Уведомления

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

class Queue<T> {
  protected items: T[] = []

  enqueue(item: T): void {
    this.items.push(item)
  }

  dequeue(): T | undefined {
    return this.items.shift()
  }

  peek(): T | undefined {
    return this.items[0]
  }

  isEmpty(): boolean {
    return this.items.length === 0
  }

  size(): number {
    return this.items.length
  }

  getItems(): T[] {
    return [...this.items]
  }

  clear(): void {
    this.items = []
  }
}

export type ToastItem = {
  id: number;
  message: string;
};

export class ToastQueue extends Queue<ToastItem> {
  private id: number = 1
  private maxSize: number;

  constructor(maxSize: number = 3) {
    super();
    this.maxSize = maxSize;
  }

  enqueueToast(message: string): ToastItem {
    if (this.size() >= this.maxSize) {
      this.dequeue();
    }

    const item: ToastItem = {
      id: this.id,
      message,
    };

    this.id++;

    this.enqueue(item);
    return item;
  }
}

Дерево

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

Когда использовать?

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

Особенности

Производительность: одной из основных проблем деревьев является их балансировка. Несбалансированные деревья могут привести к значительному снижению производительности при выполнении операций поиска, вставки и удаления.

Ключевые слова, чтобы углубиться в тему производительности и балансировки деревьев: вращение деревьев, балансировка деревьев, AVL-дерево.

Пример использования дерева #1. Комментарии

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

Как работают комментарии?

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

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

/* Файл nested-comment.vue */
    <div v-if="comment.children" class="nested-comment-next">
      <nested-comment v-for="child in comment.children" :key="child.id" :comment="child" />
    </div>

Полный код примера на GitHub

Пример использования дерева #2. Файловая структура

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

/* FileDirectory.vue */
      <div v-for="subFolder in folder.folders" :key="subFolder.name">
        <FileDirectory :folder="subFolder" />
      </div>

Здесь реализация, а здесь — её исходный код

Граф

Граф — это структура данных, состоящая из узлов и рёбер, где каждый узел представляет объект, а рёбра — связи между этими объектами. Самый наглядный пример графа в разработке — это социальные сети, где узлы — это люди, а рёбра — их дружеские связи.

Когда использовать?

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

Особенности

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

Ключевые слова, чтобы углубиться в тему: алгоритмы поиска в графах, обход графов, алгоритм Дейкстры.

Пример использования графа. Социальная сеть

Рассмотрим пример, визуализации связей в социальной сети.

class Graph {
  nodes: { id: string; x?: number; y?: number; fx?: number; fy?: number }[] = []
  links: { source: string; target: string }[] = []

    addNode(id: string) {
    this.nodes.push({ id })
    this.update()
  }

    addLink(source: string, target: string) {
    this.links.push({ source, target })
    this.update()
  }
}

Множество

Множество — это структура данных, состоящая из уникальных элементов без определённого порядка. Во frontend-разработке множества могут быть использованы для представления уникальных тегов или категорий.

Когда использовать?

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

Особенности

Не подойдет, когда нужен доступ к элементу по индексу или когда допустимы повторы.

Пример использования множества. Выборка по свойству

Рассмотрим пример, как в онлайн-кинотеатре PREMIER, где фильмы могут быть помечены различными жанрами. Множество может быть использовано для хранения и отображения уникальных жанров, связанных с фильмами.

// Список выбранных тегов по фильтрам
const selectedTags = ref<SelectedTags>({
  origin: new Set(),
  type: new Set(),
})

// Функция обработки клика на фильтр
function toggleTag<T extends Origin | Type>(category: Category, tag: T) {
  const set = selectedTags.value[category] as Set<T>

  if (set.has(tag)) {
    set.delete(tag)
  } else {
    set.add(tag)
  }

  selectedTags.value = {
    ...selectedTags.value,
    [category]: new Set(set),
  }
}

// Список отфильтрованных фильмов
const filteredMovies = computed(() =>
  movies.value.filter(movie =>
    (!selectedTags.value.origin.size || selectedTags.value.origin.has(movie.origin)) &&
    (!selectedTags.value.type.size || selectedTags.value.type.has(movie.type))
  )
)

Массив

Массив — это одна из самых распространённых структур данных в программировании. Они используются для хранения коллекции элементов.

Когда использовать?

• Когда нужно хранить список элементов, где важен порядок.

• Когда требуется частое выполнение операций, связанных с индексами.

• Когда вы работаете с коллекциями данных, которые требуют частых итераций или применения функций к каждому элементу.

Особенности

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

• Ограниченные ключи: в качестве ключей могут использоваться только числовые индексы, что ограничивает их использование для неиндексированных данных.

Пример использования массива. Список фильмов

const movies = [
  {
    id: 1,
    title: 'Брат',
  },
  {
    id: 2,
    title: 'Интерстеллар',
  },
  {
    id: 3,
    title: 'Во все тяжкие',
  },
  {
    id: 4,
    title: 'Мажор',
  },
]

Обратите внимание, на самом деле есть две похожие на себя структуры данных: массив (или статический массив) и вектор (динамический массив).

Записи в виде const arr = []; или const arr = new Array() на самом деле являются векторами. Массивом же является, например, BigInt64Array

Карта

Карта (как и объект или хэш-таблица) — коллекция пар ключ/значение.

Когда использовать?

• Когда нужно хранить данные, где каждый элемент имеет уникальный ключ.

• Когда данные имеют сложную структуру с различными свойствами.

• Когда требуется быстрый доступ к данным по ключу, а не по индексу.

Особенности

Методы итерации по картам менее удобны по сравнению с другими структурами данных.

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

Рассмотрим структуру данных карты на примере онлайн-кинотеатра, где каждый фильм имеет несколько свойств, например: название, жанр, изображение.

const movie = {
  id: 1,
  title: 'Брат',
  imgSrc: './posters/1.jpg',
  tags: [
    ['origin', 'Российские'],
    ['type', 'Фильмы'],
  ],
)

Заключение

Надеемся, что эта статья помогла вам лучше понять, как применять различные структуры данных в ваших проектах и как они могут помочь в решении реальных задач, с которыми вы сталкиваетесь ежедневно. Используйте приложенные примеры их исходники, чтобы экспериментировать и на собственномы опыте оценить, как выбор правильной структуры данных влияет на производительность и эффективность вашего приложения. Мы, как разработчики PREMIER, продолжаем исследовать и внедрять лучшие практики в нашу работу, и рады делиться опытом. Удачи в ваших начинаниях и до новых встреч в мире frontend-разработки!

Если хотите узнать больше о том, как разрабатывают медиасервисы — подписывайтесь на телеграм-канал Смотри за IT. Там инженеры цифровых активов «Газпром-Медиа Холдинга» таких, как PREMIER, RUTUBE и Yappy делятся своим опытом и тонкостями разработки видеоплатформ.