Loading...
Master the most fundamental data structure
Section 3 of 4
Every complex algorithm is built on these foundation blocks: Access, Insertion, and Deletion. Understand the cost before you write the code.
Arrays are the undisputed kings of access speed. Because elements are contiguous, the computer can jump directly to any element in exactly the same amount of time.
Consistent time regardless of array size.
1// Complexity: O(1) Constant Time value = array[index] // What the computer does: // Address = Base + (index * size_of_type)Visualize how the indices shift during operations
Inserting into an array (anywhere except the end) requires shifting all subsequent elements to make space. This is a manual, labor-intensive process for the CPU.
Deletion leaves a "hole" in the contiguous block. To maintain the array structure, you must fill the gap by shifting everything left.
Searching an unsorted array is like looking for a name in a book where names are listed randomly. You have no choice but to check every single page.
The basic search. Compare target with every index from 0 to N-1.
The optimized search. **Requires a sorted array**. Cuts the search space in half every step.
| Operation | Average | Worst Case | Why? |
|---|---|---|---|
| Access (Read) | O(1) | O(1) | Direct address calculation |
| Search | O(n) | O(n) | Possible full traversal needed |
| Insertion | O(n) | O(n) | Shifting elements right |
| Deletion | O(n) | O(n) | Shifting elements left |