What is an array?
An array stores items in consecutive slots of memory, so every item has a numbered position called an index, starting at 0. Because the computer can calculate where any slot lives, reading or updating a[i] takes the same short time no matter how large the array is.
The trade-off is a fixed size. Inserting or deleting in the middle forces every item after that position to shift by one place, which gets slower as the array grows.
Time complexity
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(1) | Jumps straight to the slot |
| Update by index | O(1) | Overwrites one slot |
| Search (unsorted) | O(n) | Checks items one by one |
| Insert at the end | O(1) | When there is free space |
| Insert or delete in the middle | O(n) | Items after it must shift |
Try it yourself
- Press Insert at index with an index in the middle and watch the items after it shift right.
- Press Delete at index to see the gap close up.
- Use Access index to see why reading by index is instant.
- Change Array size, then fill the array to see what happens when it is full.
Array vs linked list
Choose an array when you mostly read by index and know the size in advance. Choose a linked list when you insert and delete often at the ends or at a known position and the size keeps changing.
Common questions
- Why is accessing an array element O(1)?
- The address of slot i is the start of the array plus i times the item size, so the computer jumps directly to it without looking at the other items.
- Why is inserting in the middle of an array slow?
- Every item after the insertion point has to move one slot to make room, so the work grows with the number of items. That is O(n).
- What is the difference between an array and a linked list?
- An array keeps items side by side and gives instant access by index. A linked list links separate nodes, so it inserts and deletes quickly at a known position but needs a walk to reach the n-th item.