Arrays

What you'll learn

How an array is laid out, the cost of reading, inserting and deleting, and why.

Why it matters

Arrays are behind lists, strings, images and tables. Many other data structures are built on them, so knowing their strengths and weaknesses pays off everywhere.

Explanation

An array stores items one after another in a row of memory. Each item has an index, its position, starting at 0.

Because the items are side by side, the computer can jump straight to any index by arithmetic: no searching needed. That makes reading by index O(1).

But if you insert in the middle, every item after it has to shift one place to make room. Deleting shifts items back to close the gap. Both are O(n) in the worst case.

Example

const arr = [10, 20, 30, 40];

console.log(arr[2]);        // read: 30

arr.splice(1, 0, 15);       // insert 15 at index 1
console.log(arr);           // [ 10, 15, 20, 30, 40 ]

arr.splice(3, 1);           // delete the item at index 3
console.log(arr);           // [ 10, 15, 20, 40 ]

arr.push(50);               // add to the end: fast
console.log(arr);           // [ 10, 15, 20, 40, 50 ]

Step-by-step walkthrough

Press play and watch the array shift as items are inserted and removed.

1. arr[2] jumps straight to index 2 and reads 30. One step.
2. Insert at index 1: items 20, 30, 40 each shift one place to the right, then 15 drops in.
3. Delete at index 3 removes 30, and everything after it shifts left to close the gap.
4. push adds at the end, where nothing needs to move.

Try it yourself

Insert 99 at index 0 and print the array. How many items had to move?

Common mistakes

• Off-by-one on indexes. The first item is index 0, and the last is length - 1.
• Inserting at the front in a loop, making the whole thing O(n squared).
• Reading out of range. arr[10] on a 4-item array gives undefined.
• Confusing splice and slice. splice changes the array, slice copies a part.

Quick quiz

Summary

• Arrays are items side by side, found by index.
• Read by index is O(1). Insert or delete in the middle is O(n).
• Appending to the end is cheap.

Next: hash maps, for fast lookup by key.