Arrays

Also Known As

TL;DR

Explanation

True arrays (C-style) store elements contiguously in memory — index access is O(1) because element address = base + (index × element_size). PHP arrays are actually ordered hash maps, not true arrays, which is why they support mixed keys and O(1) key lookup. Dynamic arrays (ArrayList, Python list) resize by doubling capacity when full — amortised O(1) append. Understanding the difference explains why array_push() is fast but array_unshift() is O(n), and why a PHP array with integer keys 0..n behaves differently from one with gaps.

Common Misconception

Why It Matters

Common Mistakes

• array_unshift() in a loop — O(n) reindex on every call; use a queue or prepend to a linked list.
• Using PHP arrays for large numeric datasets — SplFixedArray uses ~60% less memory for integer-keyed arrays.
• Assuming count() is O(1) — it is in PHP (cached), but in other languages it may traverse the structure.
• Copying large arrays by value — PHP arrays are copy-on-write, but explicit assignment in loops still causes copies.

Code Examples

// O(n²) — array_unshift in a loop reindexes entire array each time:
$result = [];
foreach ($items as $item) {
    array_unshift($result, $item); // O(n) reindex — loop becomes O(n²)
}

// O(n) — append then reverse once:
$result = [];
foreach ($items as $item) {
    $result[] = $item; // O(1) append
}
$result = array_reverse($result); // O(n) once at end

// Or use SplStack / SplDoublyLinkedList for O(1) prepend:
$stack = new SplStack();
foreach ($items as $item) $stack->push($item);

References

• ↗ https://en.wikipedia.org/wiki/Array_(data_structure)

Tags

Related Terms