Структуры данных: Lists, LinkedList, HashTable, Stacks, Queue, Graphs, Tree

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

1. Lists (Списки)

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

Особенности

• Позволяет доступ к элементам по индексу.
• Легко изменяем (добавление/удаление элементов).

Пример на JavaScript

const list = [1, 2, 3, 4, 5];
console.log(list[2]); // 3
list.push(6); // Добавление
list.splice(2, 1); // Удаление

Применение

• Хранение данных в упорядоченной форме.
• Используется в задачах поиска и сортировки.

2. LinkedList (Связный список)

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

Особенности

• Нет доступа по индексу — для поиска нужно обходить список.
• Добавление и удаление узлов выполняются быстрее, чем в массиве.

Пример на JavaScript

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

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
}

const list = new LinkedList();
list.append(1);
list.append(2);
console.log(list);

Применение

• Имплементация стека или очереди.
• Работа с динамическими наборами данных.

3. HashTable (Хеш-таблица)

Хеш-таблица — это структура данных, которая использует хеш-функции для отображения ключей на значения.

Особенности

• Доступ к элементам по ключу за O(1).
• Может возникать коллизия, если разные ключи дают одинаковый хеш.

Пример на JavaScript

const hashTable = {};
hashTable['key1'] = 'value1';
hashTable['key2'] = 'value2';
console.log(hashTable['key1']); // 'value1'

Применение

• Реализация словарей.
• Поиск по ключу.

4. Stacks (Стек)

Стек — это структура данных, работающая по принципу LIFO (последний вошел, первый вышел).

Особенности

• Основные операции: push (добавление) и pop (удаление).
• Используется для управления историей операций.

Пример на JavaScript

const stack = [];
stack.push(1);
stack.push(2);
console.log(stack.pop()); // 2

Применение

• Обратный порядок операций (например, отмена действий).
• Обход деревьев (DFS).

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

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

Особенности

• Основные операции: enqueue (добавление) и dequeue (удаление).

Пример на JavaScript

const queue = [];
queue.push(1);
queue.push(2);
console.log(queue.shift()); // 1

Применение

• Планирование задач.
• Обход графов (BFS).

6. Graphs (Графы)

Граф — это набор узлов (вершин), соединённых рёбрами (связями).

Особенности

• Может быть направленным или ненаправленным.
• Может содержать веса на рёбрах.

Пример на JavaScript

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C']
};
console.log(graph);

Применение

• Поиск пути (например, алгоритм Дейкстры).
• Социальные сети (связи между пользователями).

7. Tree (Дерево)

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

Особенности

• Корневой узел — вершина дерева.
• Листовые узлы — узлы без потомков.

Пример на JavaScript

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

  addChild(node) {
    this.children.push(node);
  }
}

const root = new TreeNode('root');
const child1 = new TreeNode('child1');
const child2 = new TreeNode('child2');
root.addChild(child1);
root.addChild(child2);
console.log(root);

Применение

• Поиск данных (например, двоичные деревья поиска).
• Парсинг выражений (например, AST).

Итоговые вопросы для подготовки

1. Чем отличается список от связного списка?
2. Как решаются коллизии в хеш-таблицах?
3. Как работают стек и очередь, и где они используются?
4. В чём разница между графом и деревом?
5. Как применять структуры данных для оптимизации алгоритмов?

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