Что такое структурированные данные? Какие структуры данных к ним относятся?

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

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

Зачем нужны структуры данных

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

Например:

• массив удобен для доступа по индексу;
• стек удобен для отмены действий;
• очередь удобна для обработки задач по порядку;
• дерево удобно для иерархий;
• хеш-таблица удобна для быстрого поиска по ключу.

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

В линейных структурах элементы расположены последовательно.

Массив

Хранит элементы в индексированной последовательности. Обеспечивает быстрый доступ по номеру элемента.

Список

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

Стек

Стек работает по принципу LIFO: последним пришел — первым вышел.

Применяется в вызовах функций, рекурсии, отмене действий.

Очередь

Очередь работает по принципу FIFO: первым пришел — первым вышел.

Применяется в очередях задач, печати, обработке запросов.

Дек

Двусторонняя очередь позволяет добавлять и удалять элементы с обоих концов.

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

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

Дерево

Дерево хранит иерархические отношения.

Примеры:

• файловая система;
• структура HTML-документа;
• дерево каталогов;
• дерево поиска.

Граф

Граф состоит из вершин и ребер. Он описывает связи произвольного вида.

Примеры:

• дороги между городами;
• социальные связи;
• зависимости между задачами;
• сети.

Ассоциативные структуры

Таблица или словарь

Хранит пары ключ — значение.

Например: логин пользователя как ключ и профиль как значение.

Хеш-таблица

Использует хеш-функцию для быстрого доступа по ключу. В среднем поиск, вставка и удаление выполняются близко к O(1).

Записи и объекты

Структурированные данные могут объединять поля разных типов.

Например, запись Пользователь может содержать имя, email, возраст и роль.

type User = {
  name;
  email;
  age;
};

type User = {
  name: string;
  email: string;
  age: number;
};

package main
func main() {
  type User = {
    name
    email
    age
  }
}

public class Example {
  public static void main(String[] args) {
    type User = {
      name;
      email;
      age;
    };
  }
}

user = {
  "name": "Иван",
  "email": "ivan@example.com",
  "age": 18,
}

Выбор структуры

Выбор зависит от операций:

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

Вывод

структурированные данные — это организованные наборы элементов. К ним относятся массивы, списки, стеки, очереди, деки, деревья, графы, записи, объекты, таблицы, словари и хеш-таблицы.