Какие структуры данных можно создать поверх массива?

Структуры данных на основе массива

Массивы — фундамент компьютерных наук. Расскажу о 10+ структурах, которые можно реализовать поверх них.

1. Stack (Стек)

LIFO — Last In, First Out. Используется в браузере (call stack), отката действий (undo/redo).

class Stack {
  constructor() {
    this.items = [];
  }
  
  push(element) {
    this.items.push(element);
  }
  
  pop() {
    return this.items.pop();
  }
  
  peek() {
    return this.items[this.items.length - 1];
  }
  
  isEmpty() {
    return this.items.length === 0;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.pop()); // 2

2. Queue (Очередь)

FIFO — First In, First Out. Например, обработка задач, печать документов.

class Queue {
  constructor() {
    this.items = [];
  }
  
  enqueue(element) {
    this.items.push(element);
  }
  
  dequeue() {
    return this.items.shift();
  }
  
  front() {
    return this.items[0];
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue()); // 1

3. Deque (Двусторонняя очередь)

Можно добавлять/удалять с обоих концов:

class Deque {
  constructor() {
    this.items = [];
  }
  
  pushFront(element) {
    this.items.unshift(element);
  }
  
  pushBack(element) {
    this.items.push(element);
  }
  
  popFront() {
    return this.items.shift();
  }
  
  popBack() {
    return this.items.pop();
  }
}

4. Linked List (Связный список)

Динамическая структура, отлично для частых вставок/удалений:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
  
  insert(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
  }
  
  remove(data) {
    if (this.head.data === data) {
      this.head = this.head.next;
    } else {
      let current = this.head;
      while (current.next) {
        if (current.next.data === data) {
          current.next = current.next.next;
          break;
        }
        current = current.next;
      }
    }
  }
}

5. Hash Table (Хеш-таблица)

Быстрый поиск за O(1) в среднем:

class HashTable {
  constructor(size = 50) {
    this.table = new Array(size);
  }
  
  hash(key) {
    return key.length % this.table.length;
  }
  
  set(key, value) {
    const index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    this.table[index].push([key, value]);
  }
  
  get(key) {
    const index = this.hash(key);
    if (this.table[index]) {
      for (let [k, v] of this.table[index]) {
        if (k === key) return v;
      }
    }
    return undefined;
  }
}

const map = new HashTable();
map.set('name', 'John');
console.log(map.get('name')); // John

6. Heap (Куча)

Для приоритетных очередей, min/max операций:

class MinHeap {
  constructor() {
    this.items = [];
  }
  
  parent(i) {
    return Math.floor((i - 1) / 2);
  }
  
  left(i) {
    return 2 * i + 1;
  }
  
  right(i) {
    return 2 * i + 2;
  }
  
  insert(value) {
    this.items.push(value);
    this.bubbleUp(this.items.length - 1);
  }
  
  bubbleUp(index) {
    while (index > 0 && this.items[this.parent(index)] > this.items[index]) {
      [this.items[index], this.items[this.parent(index)]] = 
      [this.items[this.parent(index)], this.items[index]];
      index = this.parent(index);
    }
  }
  
  extractMin() {
    if (this.items.length === 0) return null;
    const min = this.items[0];
    this.items[0] = this.items[this.items.length - 1];
    this.items.pop();
    this.bubbleDown(0);
    return min;
  }
}

7. Tree (Дерево)

Для иерархических данных:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  
  addChild(node) {
    this.children.push(node);
  }
}

class Tree {
  constructor(root) {
    this.root = root;
  }
  
  dfs(node, callback) {
    if (node) {
      callback(node.value);
      for (let child of node.children) {
        this.dfs(child, callback);
      }
    }
  }
  
  bfs(callback) {
    const queue = [this.root];
    while (queue.length > 0) {
      const node = queue.shift();
      callback(node.value);
      queue.push(...node.children);
    }
  }
}

8. Graph (Граф)

Для сетевых структур:

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }
  
  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
}

9. Trie (Префиксное дерево)

Для автодополнения, спеллчекинга:

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  
  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }
  
  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

10. Binary Search Tree (BST)

Для быстрого поиска:

class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  
  insert(value) {
    if (value < this.value) {
      if (this.left === null) {
        this.left = new BST(value);
      } else {
        this.left.insert(value);
      }
    } else {
      if (this.right === null) {
        this.right = new BST(value);
      } else {
        this.right.insert(value);
      }
    }
  }
  
  contains(value) {
    if (value === this.value) return true;
    if (value < this.value) return this.left ? this.left.contains(value) : false;
    return this.right ? this.right.contains(value) : false;
  }
}

Итоговая таблица

Выбирай структуру в зависимости от операций, которые нужны: вставка, удаление, поиск.