Arrays

Picture a long row of school lockers, numbered from 0. Someone asks you for locker 412. You do not open lockers 0 to 411 on the way. You know where 412 is, so you walk straight to it.

Now the school wants to squeeze a new student in at locker 3 and keep everyone in number order. Every student from locker 3 onwards has to move their things one locker to the right. Reading is instant. Inserting in the middle is a chore. That is an array, and those two facts explain most of what you need to know about it.

#One block of memory, numbered from 0

An array stores its items side by side in one unbroken block of memory. Every slot is the same size. The computer remembers only one thing: where the block starts.

That is enough to find any item. If the block starts at address 1000 and each slot takes 4 bytes, item 3 lives at 1000 + 3 × 4 = 1012. One multiplication and one addition, whether the array holds 5 items or 5 million. This is why reading or writing arr[i] is O(1), and it is also why indexes start at 0: the index is the number of slots to skip from the start.

A JavaScript array or Python list can mix numbers, strings and other lists, which are not all the same size. That works because a slot can hold a reference: a fixed-size note saying where the real value lives. The slots are still side by side, so the same arithmetic finds them.

#Inserting means shifting

The flip side of "everything side by side" is that there are no gaps. To put a new item at index 1, every item from index 1 onwards must move one slot right first. Start from the end, so you never overwrite a value before you have copied it.

add one empty slot at the endfor i from last index down to index + 1:  arr[i] = arr[i - 1]arr[index] = value

Deleting works the same way in reverse: every item after the gap moves one slot left to close it. So inserting or deleting at position i costs about n − i moves. At the end it is cheap. At the front it is O(n).

// What arr.splice(index, 0, value) does for you.
function insertAt(arr, index, value) {
  arr.push(undefined); // make room at the end
  for (let i = arr.length - 1; i > index; i--) {
    arr[i] = arr[i - 1]; // shift one slot right
  }
  arr[index] = value;
}
 
const nums = [3, 8, 5, 2];
insertAt(nums, 1, 9); // nums is now [3, 9, 8, 5, 2]

# What arr.insert(index, value) does for you.
def insert_at(arr, index, value):
    arr.append(None)  # make room at the end
    for i in range(len(arr) - 1, index, -1):
        arr[i] = arr[i - 1]  # shift one slot right
    arr[index] = value
 
nums = [3, 8, 5, 2]
insert_at(nums, 1, 9)  # nums is now [3, 9, 8, 5, 2]

You will rarely write this loop yourself. The point is to know it is there. splice and unshift in JavaScript, and insert and pop(0) in Python, all hide a loop like this one behind a single name.

#How an array grows

A block of memory has a fixed size, yet push and append keep working however many items you add. The trick is that the language keeps some spare slots at the end. The number of slots in use is the length; the number reserved is the capacity.

When the spare slots run out, the language reserves a new block, often about twice as big, copies every item across, and frees the old one. That one append costs O(n). But it happens rarely: when a full block of 8 grows to 16, the next 7 appends need no copying at all.

Add it up. Filling an array to 16 items by doubling from 1 copies 1 + 2 + 4 + 8 = 15 items in total, fewer than one copy per append. That is why appending to the end is called amortized O(1): an occasional append is slow, but the average over many appends is constant.

Searching is the other slow one. Knowing an item's index is instant, but knowing which index holds the value 42 means checking items one by one. If you need that question answered often, keep a hash table next to the array, or keep the array sorted and use binary search.

#Common mistakes

#Check yourself

#What to practise next

Strings are arrays of characters with one important twist: you cannot change them in place. That twist, and how to work around it, is the subject of Strings.