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

Что такое структуры данных?

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

• Как хранить данные — в каком формате и порядке
• Какие операции доступны — добавление, удаление, поиск, обновление
• Эффективность операций — временная и пространственная сложность

Классификация структур данных

Линейные структуры

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

Основные линейные структуры:

• Линейные структуры — массивы, списки, стеки, очереди

Нелинейные структуры

Данные организованы в иерархическом или сетевом порядке.

Основные нелинейные структуры:

• Нелинейные структуры — деревья, графы, кучи, хеш-таблицы

Линейные структуры данных

Массивы

Описание: Фиксированный размер, элементы хранятся в непрерывной памяти.

Операции:

• Доступ к элементу: O(1)
• Поиск: O(n)
• Вставка: O(n)
• Удаление: O(n)

Преимущества:

• Быстрый доступ к элементам по индексу
• Простота реализации
• Эффективное использование памяти

Недостатки:

• Фиксированный размер
• Медленная вставка/удаление в середине

Связные списки

Описание: Динамический размер, элементы связаны указателями.

Операции:

• Доступ к элементу: O(n)
• Поиск: O(n)
• Вставка: O(1) в начало, O(n) в середину
• Удаление: O(1) в начало, O(n) в середину

Преимущества:

• Динамический размер
• Быстрая вставка/удаление в начало
• Эффективное использование памяти

Недостатки:

• Медленный доступ к элементам
• Дополнительная память для указателей

Стеки

Описание: LIFO (Last In, First Out) — последний добавленный элемент извлекается первым.

Операции:

• Push (добавление): O(1)
• Pop (извлечение): O(1)
• Peek (просмотр вершины): O(1)

Применение:

• Отмена операций (undo)
• Вызовы функций
• Проверка скобок
• Обход деревьев (DFS)

Очереди

Описание: FIFO (First In, First Out) — первый добавленный элемент извлекается первым.

Операции:

• Enqueue (добавление): O(1)
• Dequeue (извлечение): O(1)
• Front (просмотр начала): O(1)

Применение:

• Обработка задач
• Обход графов (BFS)
• Буферизация данных
• Планирование процессов

Нелинейные структуры данных

Деревья

Описание: Иерархическая структура с корневым узлом и дочерними узлами.

Основные типы:

• Деревья — бинарные деревья, AVL, красно-черные

Операции:

• Поиск: O(log n) в сбалансированном дереве
• Вставка: O(log n)
• Удаление: O(log n)

Графы

Описание: Набор вершин, соединенных ребрами.

Представление:

• Графы — матрица смежности и список смежности

Типы графов:

• Направленные/ненаправленные
• Взвешенные/невзвешенные
• Связные/несвязные

Хеш-таблицы

Описание: Структура для быстрого доступа к данным по ключу.

Операции:

• Вставка: O(1) в среднем
• Поиск: O(1) в среднем
• Удаление: O(1) в среднем

Применение:

• Словари
• Кэширование
• Индексы в базах данных
• Подсчет частоты элементов

Кучи

Описание: Частично упорядоченная структура, где родительский узел больше (max-heap) или меньше (min-heap) дочерних.

Операции:

• Вставка: O(log n)
• Извлечение максимума/минимума: O(log n)
• Построение кучи: O(n)

Применение:

• Приоритетные очереди
• Сортировка кучей
• Алгоритм Дейкстры
• Поиск k-го наибольшего элемента

Выбор структуры данных

Критерии выбора:

1. Тип операций — какие операции будут выполняться чаще всего
2. Размер данных — сколько элементов будет храниться
3. Память — сколько памяти доступно
4. Производительность — требования к скорости операций

Рекомендации:

Для частого доступа по индексу: Массивы--- Unknown node: hardBreak ---Для частых вставок/удалений: Связные списки--- Unknown node: hardBreak ---Для LIFO операций: Стеки--- Unknown node: hardBreak ---Для FIFO операций: Очереди--- Unknown node: hardBreak ---Для поиска: Хеш-таблицы, деревья поиска--- Unknown node: hardBreak ---Для приоритетов: Кучи--- Unknown node: hardBreak ---Для связей: Графы

Примеры реализации

Стек

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

Очередь

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

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

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

class LinkedList {
    constructor() {
        this.head = null;
    }
    
    append(val) {
        const newNode = new ListNode(val);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
}

Преимущества изучения структур данных

• Повышает эффективность кода — помогает выбирать оптимальные структуры
• Развивает системное мышление — понимание организации данных
• Готовит к собеседованиям — основа технических интервью
• Расширяет возможности — больше инструментов для решения задач

Недостатки

• Требует понимания — нужно знать особенности каждой структуры
• Много деталей — множество нюансов реализации
• Абстрактные концепции — некоторые структуры сложны для понимания

Структуры данных — это фундамент эффективного программирования!