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