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

Структуры данных на основе JavaScript-объектов

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

1. Хеш-таблица / Ассоциативный массив

Сам объект уже является реализацией хеш-таблицы, но его можно расширить:

class HashTable {
    constructor(size = 53) {
        this.keyMap = new Array(size);
    }
    
    _hash(key) {
        let total = 0;
        for (let char of key) {
            total = (total * 31 + char.charCodeAt(0)) % this.keyMap.length;
        }
        return total;
    }
    
    set(key, value) {
        const index = this._hash(key);
        if (!this.keyMap[index]) this.keyMap[index] = [];
        this.keyMap[index].push([key, value]);
    }
}

2. Стек на основе объекта

class ObjectStack {
    constructor() {
        this.storage = {};
        this.count = 0;
    }
    
    push(element) {
        this.storage[this.count] = element;
        this.count++;
    }
    
    pop() {
        if (this.count === 0) return undefined;
        this.count--;
        const result = this.storage[this.count];
        delete this.storage[this.count];
        return result;
    }
}

3. Очередь

class ObjectQueue {
    constructor() {
        this.items = {};
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(element) {
        this.items[this.rear] = element;
        this.rear++;
    }
    
    dequeue() {
        if (this.front === this.rear) return null;
        const item = this.items[this.front];
        delete this.items[this.front];
        this.front++;
        return item;
    }
}

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

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    
    addToTail(value) {
        const newNode = { value, next: null };
        if (!this.head) {
            this.head = newNode;
        } else {
            this.tail.next = newNode;
        }
        this.tail = newNode;
        this.length++;
    }
}

5. Деревья и графы

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

// Пример графа на основе adjacency list
class Graph {
    constructor() {
        this.adjacencyList = {};
    }
    
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = [];
        }
    }
    
    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
        this.adjacencyList[vertex2].push(vertex1);
    }
}

6. Множество (Set)

class ObjectSet {
    constructor() {
        this.items = {};
    }
    
    add(value) {
        if (!this.has(value)) {
            this.items[value] = value;
            return true;
        }
        return false;
    }
    
    has(value) {
        return this.items.hasOwnProperty(value);
    }
    
    delete(value) {
        if (this.has(value)) {
            delete this.items[value];
            return true;
        }
        return false;
    }
}

7. Приоритетная очередь

class PriorityQueue {
    constructor() {
        this.values = [];
    }
    
    enqueue(val, priority) {
        this.values.push({val, priority});
        this.sort();
    }
    
    dequeue() {
        return this.values.shift();
    }
    
    sort() {
        this.values.sort((a, b) => a.priority - b.priority);
    }
}

8. 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;
    }
}

Ключевые преимущества использования объектов:

• Быстрый доступ по ключу (в среднем O(1))
• Гибкость — ключами могут быть строки или символы
• Динамическое расширение без предварительного определения размера
• Интуитивная работа с JSON-данными

Ограничения и особенности:

• Ключи автоматически приводятся к строкам (кроме Symbol)
• Нет гарантированного порядка (кроме ES6+ где порядок строковых ключей сохраняется)
• Прототипное наследование может создавать неожиданные свойства
• Менее эффективны для числовых индексов чем массивы

На практике, современный JavaScript предлагает Map и Set для многих сценариев, где раньше использовались объекты, но понимание построения структур данных на основе объектов остается важным для глубокого понимания языка и решения специфических задач оптимизации.