Arrays
Explanations in this animation:
- Traversal
- Visiting every value in an array means indexes 0, 1, 2 and so on to the end - the order a loop takes, and n reads for n values. Each read is independent and costs the same, so the price of the walk is the number of values, not their positions. Any one of them could equally have been reached on its own, which is the difference between traversing an array and accessing it. Reading, either way, moves nothing.
- Access
- Reaching a[3] does not involve the four values around it. The position is worked out from the index rather than searched for, so the read goes straight to that one slot and costs the same as reaching a[0] or a[4]. Nothing in the row is moved or looked at on the way, which is the difference between accessing an array and traversing it.
- Search
- Nothing about an array says where a value is, only where an index is. So finding a value means checking the elements one at a time from the front. These five are in no order, which is the situation that leaves no faster option. Looking for 23, which sits at the very last index, costs all five checks - the worst case, and the one that sets the bound.
- Insert
- A dynamic array - an ArrayList, a vector, a Python list - is a plain array with spare capacity at the end. This one holds five values in room for six. Inserting 25 at index 2 still has to make a gap: 30, 40 and 50 each move one place right, starting from the back so nothing is overwritten before it has been copied. Only then is index 2 free. The spare capacity is what lets the array grow at all; it does nothing about the shifting, which is why inserting into the middle stays expensive.
- Delete
- Deleting is inserting in reverse. Removing 30 from index 2 leaves a hole, and an array is not allowed to have one, so every value after it moves one place left to close it. Two values move to remove one, and the slot at the end stops being part of the array. As with inserting, the cost is not the removal but everything that has to shift after it.
Task: Read every value in order
Why we need arrays
Analogy
- Imagine a row of lockers in a school hallway.
- Each locker has a number (the index) and holds one item (the value).
- To find your book in locker 3, you go straight to locker number 3, no searching, no checking the other lockers on the way.
- That is exactly how an array stores and reaches data, related items kept together in one organised line.
What is an array?
Definition
An array is a collection of elements of the same type, stored side by side in memory.
int numbers[3] = {10, 20, 30};Here numbers[0] is 10, numbers[1] is 20, and numbers[2] is 30. One name for all three, and a position you can compute with.
What is an index?
The index is the position of an item. Every element is reached through its index, and arrays start counting from 0, not 1.
int scores[5] = {95, 80, 72, 88, 91};- Index 0 → 95
- Index 1 → 80
- Index 4 → 91
So scores[2] gives 72 - the third value.
Watch out
The beginner mistake: Forgetting that the first element is at index 0.
In an array of 5 items the last index is 4. Reaching for scores[5] runs off the end of the array.
Fixed size
An array's size is decided when it is created, and it does not change.
int marks[5]; // can store exactly 5 integers. Not 4, not 6.You cannot add more elements once it’s full.
Why are arrays fast?
Because every item is the same size and they sit together with no gaps, the computer never has to look for a value. It calculates where the value is and jumps straight there:
address = start + index × size of one item
That is one multiplication, one addition and one read, the same three steps whether the array holds 5 items or 5 million. This is what O(1) access means: reaching any position costs the same.
Adding a new item
- At the end → easy, if there is space. Nothing else moves.
- In the middle → every item from that position onwards has to shift right to open the slot.
Inserting 25 into [10, 20, 30, 40] gives [10, 20, 25, 30, 40], notice how 30 and 40 shifted to make room.
Note
"But I add to lists all the time." You are almost certainly using a dynamic array- ArrayList in Java, vector in C++, list in Python.
It is a plain array with a growth rule bolted on: when it fills up, it quietly allocates a new, bigger block (usually about double) and copies everything across. So it can always accept one more item at the end.
What it does not fix is the shifting. Inserting into the middle of a dynamic array still moves everything after it.
Removing an item
Taking a value out leaves a gap, and a gap breaks the arithmetic that made the index instant. So the remaining items shift left to close it.
Removing 10 from [5, 10, 15, 20] gives [5, 15, 20]. The elements move so they stay together.
| Operation | What happens | Cost |
|---|---|---|
| Read by index | Calculate the address, read it | O(1) |
| Add at the end | Write into the next free slot | O(1) |
| Insert in the middle | Shift everything after it right | O(n) |
| Remove from the middle | Shift everything after it left | O(n) |
Try it yourself
Numbered positions, starting at 0
arrChoose an operationWatch the index numbers when you insert or delete in the middle. Every element after the one you touched gets a new index, and that renumbering is the O(n) in the table above.
When should you use an array?
Reach for an array when:
- The items belong together.
- You need quick access by position.
- The order of the items matters.
Everyday examples: the days of a week, a student's marks, daily temperatures, a playlist of songs.
Advantages
- Instant lookups: Jump straight to any element using its index.
- Hardware friendly: CPUs love reading continuous memory; it's extremely fast to cache.
- The foundation: Advanced structures like matrices, hash tables, and heaps are all built on top of arrays.
Where arrays already are
- Strings → stored as arrays of characters.
- Images → pixels stored in arrays, row by row.
- Buffers → audio samples and network packets land in arrays before anything reads them.
Key takeaway
An array is a neatly organised row of numbered lockers: finding an item is instant, but inserting or removing one in the middle means shifting everything after it.