Linear Data Structures
Arrays
A fixed-size block of same-type elements stored next to each other in memory, accessed by index in O(1).
1Introduction
Arrays are the foundation of almost every other data structure. Strings, dynamic arrays, heaps, hash tables and matrices are all built on top of them, so understanding how an array is laid out in memory explains why some operations are instant and others are slow.
2What is it?
An array is an ordered collection of elements of the same type stored in one contiguous block of memory. Every element has an index starting at 0, and the address of element i can be computed directly: address(i) = base + i × elementSize.
3Why do we use it?
- Instant (O(1)) access to any element by index.
- Excellent cache performance because elements sit next to each other.
- Very low memory overhead — no pointers per element.
- The natural representation for sequences, tables, images and matrices.
4Real-world examples
- Pixels of an image stored row by row.
- Daily temperatures for a month, or marks of every student in a class.
- A music playlist where you jump straight to song #7.
- Lookup tables such as days-in-month[12].
5Internal working
When an array is created, the runtime reserves size × elementSize bytes in one piece. The variable holds the base address.
Reading arr[i] multiplies i by the element size, adds the base address and reads that location — one arithmetic step, regardless of the array's length.
Inserting or deleting in the middle requires shifting every later element by one position to keep the block contiguous, which costs O(n).
6Memory representation
A 5-element int array (4 bytes per int) starting at address 1000:
index: 0 1 2 3 4
+------+------+------+------+------+
value: | 5 | 3 | 8 | 1 | 2 |
+------+------+------+------+------+
address: 1000 1004 1008 1012 1016
address(i) = 1000 + i * 4 -> arr[3] lives at 10127Operations
| Operation | How it works |
|---|---|
| Access arr[i] | Compute the address directly. |
| Update arr[i] = x | Overwrite one slot. |
| Search (unsorted) | Check elements one by one. |
| Search (sorted) | Binary search halves the range. |
| Insert / delete at end | No shifting needed (if space exists). |
| Insert / delete in middle | Shift later elements right / left. |
| Reverse | Two pointers swap from both ends. |
8Visual explanation
Reverses an array in place with two pointers: swap the outermost pair, move both pointers inward, and stop when they meet.
9Code implementation
Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.
10Time complexity
| Operation | Time |
|---|---|
| Access arr[i] | O(1) |
| Update arr[i] = x | O(1) |
| Search (unsorted) | O(n) |
| Search (sorted) | O(log n) |
| Insert / delete at end | O(1) |
| Insert / delete in middle | O(n) |
| Reverse | O(n) |
11Space complexity
An array of n elements uses O(n) space. Most array algorithms (reverse, two-pointer scans, in-place sorts) need only O(1) extra space; techniques like hashing or prefix sums trade O(n) extra memory for speed.
12Advantages
- O(1) random access.
- Cache-friendly sequential access.
- Simple and memory-efficient.
- Easy to sort and binary search.
13Disadvantages
- Fixed size (static arrays) — must know the capacity up front.
- Inserting/deleting in the middle is O(n).
- Resizing means allocating a new block and copying everything.
- Can waste memory if allocated larger than needed.
14Common mistakes
- Off-by-one errors: the last index is n − 1, not n.
- Using `<=` instead of `<` in loop conditions and reading past the end.
- Modifying an array while iterating over it.
- Assuming arrays in JavaScript/Python are fixed-size (they are dynamic arrays).
- Forgetting that `b = a` copies the reference, not the elements.
15Interview questions
16Practice exercises
- Find the second largest element in one pass.
- Rotate an array to the right by k steps in O(1) extra space.
- Remove duplicates from a sorted array in place.
- Merge two sorted arrays.
- Compute prefix sums and answer range-sum queries in O(1).
Try them in the Coding Playground.