Типы
- Singly Linked — каждый узел → следующий. Обход только вперёд
- Doubly Linked — каждый узел → следующий и предыдущий. Обход в обоих направлениях
- Circular — последний узел → первый
Сравнение с массивом
- Вставка/удаление в начале: список O(1) vs массив O(n) (сдвиг)
- Вставка/удаление в середине: список O(n) (поиск) vs массив O(n) (сдвиг)
- Доступ по индексу: список O(n) vs массив O(1)
- Память: список тратит больше (указатели)
В PHP
PHP-массивы — хеш-таблицы, а не связные списки. Для настоящего связного списка: SplDoublyLinkedList или собственная реализация. На практике редко нужен.