Односвязный список — это динамическая структура данных, состоящая из узлов (нод). Каждый узел (кроме последнего) содержит данные и ссылку на следующий узел. Последний узел имеет пустую ссылку.
Основные характеристики:
- Узлы: Каждый узел содержит значение и указатель на следующий узел.
- Голова (Head): Указатель на первый узел списка.
- Хвост (Tail): Указатель на последний узел.
- Последовательность: Элементы расположены в определенной последовательности.
- Прямой доступ: Доступ к элементам возможен только последовательно, начиная с головы.
- Динамический размер: Размер списка может изменяться во время выполнения программы.
Преимущества:
- Эффективная вставка и удаление элементов в начале списка.
- Экономия памяти по сравнению с массивами при непредсказуемом размере данных.
Недостатки:
- Медленный доступ к элементам по индексу (требуется обход с начала).
- Требует дополнительной памяти для хранения указателей.
Простая реализация на PHP:
php
Применяется в различных алгоритмах и структурах данных, например, в стеках и очередях.