Arrays
An array is a collection of similar data elements stored at contiguous memory locations.
Fundamental Concepts
Types of Arrays
A static array has a fixed size defined at creation and cannot grow or shrink during runtime.
A dynamic array can resize automatically as elements are added or removed, allowing flexible storage.
An indexed array stores elements that are accessed using numerical indices like 0, 1, 2.
An associative array stores data as key–value pairs, where elements are accessed using keys instead of indices.
A 1D array is a linear collection of elements stored in a single row.
A 2D array stores elements in rows and columns like a table or matrix.
A 3D array stores elements in multiple layers, where a 2×2×2 array has 2 layers each containing a 2×2 grid.
Layer 0
Layer 1
Arrays can be structured in multiple ways to store data.
Traversal
Traversal means visiting each element one by one, and its time complexity is O(n).
Access
Access means retrieving an element by index, and its time complexity is O(1).
Insertion
Insertion means adding an element at a position, and its time complexity is O(n) due to shifting elements.
Deletion
Deletion means removing an element, and its time complexity is O(n) due to shifting elements.
Update
Update means modifying the value at a specific index, and its time complexity is O(1).
Search
Linear search checks elements sequentially until the target is found, with time complexity O(n).
Binary search repeatedly divides a sorted array to find a target efficiently, with time complexity O(log n).
Search means finding a value in the array, and its time complexity is O(n) in general.
Sorting (Bubble Sort)
Bubble sort repeatedly swaps adjacent elements until the array is sorted, with time complexity O(n²).
Merge
Merge combines two sorted arrays into a single sorted array, typically taking O(n + m) time.
Time Complexity Comparison
| Operation | Static Array | Dynamic Array | Indexed Array (1D/2D/3D) | Associative Array |
|---|---|---|---|---|
| Access | O(1) | O(1) | O(1) | O(1) avg |
| Traversal | O(n) | O(n) | O(n) | O(n) |
| Search | O(n) | O(n) | O(n) | O(1) avg |
| Insert (middle) | O(n) | O(n) | O(n) | O(1) avg |
| Delete | O(n) | O(n) | O(n) | O(1) avg |