Resources:
- T. H. Cormen, Ed., Introduction to algorithms, 2nd. ed., 10th pr. Cambridge, Mass.: MIT Press [u.a.], 2007.
- An Overview of Arrays and Memory (Data Structures & Algorithms #2), Youtube.com, 2026. https://www.youtube.com/watch?v=pmN9ExDf3yQ.
- C. to, “random-access, variable-size list data structure that allows elements to be added or removed,” Wikipedia.org, Feb. 2005. https://en.wikipedia.org/wiki/Dynamic_array.
Array
Array is one of the most fundamental and widely used data structures. It serves as a building block for more complex structures like heaps, hash tables, and matrices.
1. What is an Array?
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together.
Think of an array like a row of numbered lockers in a hallway.
- Each locker is next to the other (contiguous).
- Each locker is the same size.
- You can find any locker instantly if you know its number (index).
Key Characteristics:
- Fixed Size: In most low-level languages (like C), once you declare the size of an array, it cannot change.
- Same Data Type: You generally cannot store an integer in index 0 and a string in index 1 (in statically typed languages).
- 0-Based Indexing: In most programming languages, the first element is at index
0, the second at1, and so on.
2. How Arrays Work in Memory ?
The “magic” of an array is its speed of access. Because the data is stored side-by-side in memory, the computer can calculate the exact address of any element using a simple formula: Address=Base Address+(Index×Element Size)
Because this is a simple math calculation, the computer can jump directly to index 1000 without looking at the first 999 elements. This is called Random Access.
3. Time Complexity (Big O)
In DSA, we measure efficiency using Big O notation. Here is how arrays perform for common operations:
| Operation | Complexity | Explanation |
| Access (Read/Write) | $O(1)$ | Instant. You know the address directly. |
| Search (Linear) | $O(n)$ | You must check every box one by one to find a value. |
| Insert (at end) | $O(1)$ | Fast (if there is space available). |
| Insert (middle/start) | $O(n)$ | Slow. You must shift all subsequent elements down to make room. |
| Delete (from end) | $O(1)$ | Fast. Just mark the slot as empty. |
| Delete (middle/start) | $O(n)$ | Slow. You must shift all subsequent elements up to fill the gap. |
Note: If the array is sorted, you can use Binary Search, which reduces the search time to $O(logn)$.
Example Code using python.
4. Types of Arrays
- A. One-Dimensional Arrays
- A simple list of items.
- Visual:
[10, 20, 30, 40]
- B. Multi-Dimensional Arrays (2D Arrays/Matrices)
- An “array of arrays.” This is often used to represent grids, tables, or images (pixels).
- Visual: A spreadsheet with rows and columns.
- C. Dynamic Arrays
- Standard arrays have a fixed size. Dynamic arrays (like
ArrayListin Java,vectorin C++, orlistin Python) automatically resize themselves when they get full. - How they work: When full, they create a new, larger array (usually double the size), copy all existing items over, and delete the old array.
https://en.wikipedia.org/wiki/Dynamic_array
- Standard arrays have a fixed size. Dynamic arrays (like
Example of 3D Array:
5. Pros and Cons
Advantages:
- Fast Access: Reading an element is O(1).
- Cache Friendliness: Because memory is contiguous, the CPU can load data into the cache efficiently, making iteration very fast.
- Simple: Easy to implement and understand.
Disadvantages:
- Fixed Size: You must know how much memory you need upfront (for static arrays).
- Costly Insertions/Deletions: Adding or removing items in the middle requires shifting elements, which is expensive for large datasets.
