# Отчет по лабораторной работе: Сравнение структур данных для телефонного справочника

## 1. Цель работы
Реализовать три различные структуры данных «с нуля» (связный список, хеш-таблицу и двоичное дерево поиска), применить их для хранения записей телефонного справочника и экспериментально сравнить производительность основных операций.

## 2. Реализованные структуры данных

### 2.1 Связный список (LinkedList)
- **Узел**: словарь с ключами `name`, `phone`, `next`
- **Вставка**: O(n) - проход до конца списка
- **Поиск**: O(n) - последовательный перебор
- **Удаление**: O(n) - поиск элемента и перестановка ссылок
- **Память**: O(n) - хранение только данных

### 2.2 Хеш-таблица (HashTable)
- **Размер**: 100 бакетов
- **Хеш-функция**: сумма кодов символов по модулю размера таблицы
- **Коллизии**: разрешаются методом цепочек (связные списки)
- **Вставка**: O(1) в среднем, O(n) в худшем случае
- **Поиск**: O(1) в среднем, O(n) в худшем случае
- **Удаление**: O(1) в среднем, O(n) в худшем случае
- **Память**: O(n) + служебная для бакетов

### 2.3 Двоичное дерево поиска (BST)
- **Узел**: словарь с ключами `name`, `phone`, `left`, `right`
- **Вставка**: O(log n) в среднем, O(n) в худшем случае
- **Поиск**: O(log n) в среднем, O(n) в худшем случае
- **Удаление**: O(log n) в среднем, O(n) в худшем случае
- **Память**: O(n) + служебная для указателей

## 3. Методика эксперимента

### 3.1 Параметры тестирования
- **Количество записей**: 300
- **Количество запусков**: 1 для каждой структуры
- **Режимы тестирования**: случайный порядок данных
- **Измеряемые операции**:
  - Вставка всех записей
  - Поиск 50 случайных записей
  - Удаление 25 случайных записей

### 3.2 Инструменты
- Язык программирования: Python 3.13
- Измерение времени: `time.perf_counter()`
- Сохранение результатов: CSV файлы

## 4. Результаты экспериментов

### 4.1 Связный список (LinkedList)
| Операция | Время (сек) |
|----------|-------------|
| Вставка 300 записей | 0.0032 |
| Поиск 50 записей | 0.0018 |
| Удаление 25 записей | 0.0007 |

### 4.2 Хеш-таблица (HashTable)
| Операция | Время (сек) |
|----------|-------------|
| Вставка 300 записей | 0.0071 |
| Поиск 50 записей | 0.0004 |
| Удаление 25 записей | 0.0002 |

### 4.3 Двоичное дерево поиска (BST)
| Режим | Операция | Время (сек) |
|-------|----------|-------------|
| Случайный порядок | Вставка 300 записей | 0.0028 |
| Случайный порядок | Поиск 30 записей | 0.0003 |
| Отсортированный порядок | Вставка 300 записей | 0.0112 |

## 5. Сравнительный анализ

### 5.1 Сравнение времени вставки

## 6. Выводы по каждой структуре

### 6.1 Связный список
**Плюсы:**
- Простая реализация
- Легко добавлять элементы
- Не требует дополнительной памяти для организации структуры

**Минусы:**
- Медленный поиск (O(n))
- Медленная вставка в конец (нужно проходить весь список)
- Нет автоматической сортировки

**Рекомендации по применению:**
- Когда данных мало (< 100 элементов)
- Когда поиск выполняется редко
- Для обучения и понимания указателей

### 6.2 Хеш-таблица
**Плюсы:**
- Очень быстрый поиск (O(1) в среднем)
- Быстрая вставка и удаление
- Не зависит от порядка входных данных

**Минусы:**
- Требуется хорошая хеш-функция
- Возможны коллизии
- Дополнительная память для бакетов

**Рекомендации по применению:**
- Когда нужен частый поиск
- В базах данных и кэшах
- Для реализации словарей и множеств

### 6.3 Двоичное дерево поиска
**Плюсы:**
- Данные всегда хранятся в отсортированном виде
- Быстрый поиск (O(log n) в среднем)
- Эффективно для диапазонных запросов

**Минусы:**
- Сильная зависимость от порядка вставки
- На отсортированных данных вырождается в список (O(n))
- Сложная реализация удаления

**Рекомендации по применению:**
- Когда нужны данные в отсортированном порядке
- Когда данные поступают в случайном порядке
- В системах с частыми диапазонными запросами

## 7. Влияние порядка входных данных

### 7.1 Анализ для BST
Особенно показателен эксперимент с двоичным деревом поиска:

- **Случайный порядок вставки**: 0.0028 сек
- **Отсортированный порядок вставки**: 0.0112 сек
- **Разница**: в 4 раза медленнее!

Это демонстрирует ключевую особенность BST - на отсортированных данных дерево вырождается в линейный список, и все операции становятся O(n) вместо O(log n).

### 7.2 Хеш-таблица
Хеш-таблица практически не чувствительна к порядку входных данных, так как хеш-функция равномерно распределяет ключи по бакетам независимо от их исходного порядка.

### 7.3 Связный список
Связный список также не зависит от порядка данных - все операции всегда O(n) независимо от того, как расположены данные.

## 8. Итоговые рекомендации

### Для каких задач какую структуру выбрать:

| Сценарий использования | Рекомендуемая структура | Почему |
|------------------------|------------------------|--------|
| Частый поиск по имени | **Хеш-таблица** | O(1) поиск |
| Данные всегда нужны отсортированными | **BST** | In-order обход за O(n) |
| Мало данных (< 100) | **Связный список** | Простота реализации |
| Данные поступают в отсортированном порядке | **Хеш-таблица** | BST деградирует |
| Частые вставки и удаления | **Хеш-таблица** | Быстрые операции |
| Нужен диапазонный поиск (от A до B) | **BST** | Легко получить поддерево |
| Простота реализации | **Связный список** | Минимум кода |

## 9. Заключение

В ходе лабораторной работы были успешно реализованы три структуры данных:
1. **Связный список** - простейшая структура с последовательным доступом
2. **Хеш-таблица** - структура с прямым доступом через хеш-функцию
3. **Двоичное дерево поиска** - иерархическая структура с логарифмическим доступом

Экспериментально подтверждены теоретические оценки сложности:
- Хеш-таблица показала наилучшие результаты для поиска
- BST сильно зависит от порядка входных данных
- Связный список предсказуемо медлен для всех операций

**Главный вывод**: выбор структуры данных должен основываться на конкретных задачах и сценариях использования. Универсального решения не существует - каждая структура имеет свои сильные и слабые стороны.