Types
- Singly Linked — each node → next node. Forward traversal only
- Doubly Linked — each node → next and previous. Traversal in both directions
- Circular — the last node → the first
Comparison with arrays
- Insert/delete at head: list O(1) vs array O(n) (shift)
- Insert/delete in middle: list O(n) (search) vs array O(n) (shift)
- Index access: list O(n) vs array O(1)
- Memory: list uses more (pointers)
In PHP
PHP arrays are hash tables — not linked lists. For a true linked list: SplDoublyLinkedList or a custom implementation. Rarely needed in practice.