Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI26 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Что такое односвязный список
Односвязный список (Singly Linked List) — это одна из фундаментальных структур данных. Это линейная структура, состоящая из узлов, где каждый узел содержит данные и ссылку на следующий узел.
Базовая концепция
Представь цепочку вагончиков, где каждый вагончик знает только о следующем вагончике, но не о предыдущем. Вот это и есть односвязный список.
Полная реализация
Структура включает класс Node с данными и ссылкой на следующий узел. Основные операции: добавление в конец, вставка в начало, удаление, получение по индексу, определение длины.
Операции и их сложность
| Операция | Сложность |
|---|---|
| Добавить в начало | O(1) |
| Добавить в конец | O(n) |
| Удалить | O(n) |
| Доступ по индексу | O(n) |
| Поиск | O(n) |
Преимущества
- Экономия памяти при частых вставках/удалениях
- Динамический размер
- Эффективные вставки в начало (O(1))
Недостатки
- Медленный доступ по индексу (O(n))
- Дополнительная память на ссылки
- Нет обратного хода
- Cache unfriendly
Когда использовать
Используй для стеков, очередей, когда часто вставляют/удаляют в начало.