1D Array Visualizer

Picture a row of lockers, numbered from 0, all the same size, with no gaps between them. That is an array: one block of memory divided into equal slots. The number on the locker is the index, and because every locker is the same size, the computer can work out where locker 7 is without opening lockers 0 to 6. It multiplies 7 by the slot size and adds it to the address of the first locker.

Two consequences follow, and they explain every cost on this page. Reading or writing any slot is one step, however long the array is. But the slots are fixed in place: you cannot squeeze a new locker in between two others. To make room you have to move the neighbours, and to close a gap you have to move them back.

In the visualizer above, a[i] means the value in slot i, and the counters show every read and write the computer makes. Watch them: they are the whole story.

Pick Access and any index. The computer computes base + index × size and reads that slot. One multiplication, one addition, one read. Nothing depends on n, which is what O(1) means: constant time.

This is the reason arrays are everywhere. A list of a million temperatures still gives you the 999,999th one instantly. Data structures that cannot do this, such as linked lists, have to walk from the start.

Take five values, 8, 3, 12, 5, 9, with one spare slot at the end, and insert 42 at index 2. Slot 2 is occupied by 12, so 12 has to move, and so does everything after it. The order matters: move 9 into the spare slot first, then 5 into 9's old slot, then 12 into 5's. Three shifts, working from the end, and only then is 42 written into slot 2. Start from the front instead and the first move overwrites a value you still need.

Delete works the same way in reverse. Remove the value at index 0 from 8, 3, 12, 5, 9 and four values move one place left, this time starting from the front: 3 into slot 0, 12 into slot 1, and so on. The last slot ends up unused.

Count the work. Inserting at index i of n values costs n − i shifts; deleting costs n − i − 1. At the end that is zero, which is why appending and popping are cheap. At the front it is the whole array, which is O(n). Set the index slider to 0 and to the end and compare the Writes counter.

If the values are in no particular order, there is no way to know where a value is except by looking. Linear search compares the target with a[0], then a[1], and stops at the first match or at the end. Found at index k costs k + 1 compares; not found costs n.

Best case one compare, worst case all of them, average about half. That spread is normal for searches, and it is why sorting the data first pays off: on a sorted array a binary search needs only about log₂ n compares. The sorting visualizers show what that ordering costs.

The obvious way to reverse an array is to copy it backwards into a second array. That works but needs n extra slots. The two-pointer version needs none: lo starts at the first slot, hi at the last. Swap the two values, move lo right and hi left, and stop when they meet or cross. Every value moves exactly once, so the cost is ⌊n/2⌋ swaps: O(n) time and O(1) extra space.

Two pointers walking towards each other is a pattern you will meet again and again: checking whether a word is a palindrome, finding two numbers that add up to a target in a sorted array, and partitioning in quicksort all use it.

n is the number of values. New to the notation? The Big-O Playground starts from zero →

The array in the visualizer has a fixed size, which is how arrays work in C, Java and at the bottom of every language. A Python list, a JavaScript array and a C++ vector feel different because they grow on demand, but underneath each one is a plain array plus a trick: when it fills up, the language allocates a bigger block, copies everything across and keeps some spare slots. It grows by a constant factor each time (CPython by about an eighth, V8 by half, libstdc++ by doubling), so the copies are rare and appending costs O(1) on average.

The trick does not change the other costs. list.insert(0, x) and list.pop(0) still shift every value, exactly as above, and so do splice and unshift in JavaScript. If you need cheap work at both ends, use a structure built for it, such as Python's collections.deque. One more nuance for JavaScript: the language never promises that an array is stored in one block, though engines such as V8 do pack dense arrays of one type that way.

• Off by one. The last index is n − 1. Reading a[n] is an error in Java and Python, and silently garbage in C.
• Shifting from the wrong end. Insert shifts from the back towards the gap; delete shifts from the gap towards the back. Get it backwards and one value overwrites another.
• Deleting inside a forward loop. Removing a[i] moves a[i + 1] into slot i, and the loop then skips it. Loop backwards, or build a new array of the values you keep.
• Assuming the built-ins are free. insert(0, x), pop(0) and unshift hide a loop over the whole array. In a loop of their own they turn O(n) into O(n²).

Rows and columns next: the 2D Array Visualizer shows how a grid is really one long array in disguise.