Arrays
A collection of elements stored in contiguous memory locations.
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.
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
Traversal
Time Complexity: O(n)
Access
Time Complexity: O(1)
Insertion
Time Complexity: O(n) due to shifting elements.
Deletion
Time Complexity: O(n) due to shifting elements.
Update
Time Complexity: O(1)
Search
Checks elements sequentially until the target is found.
Repeatedly divides a sorted array to find a target efficiently.
When to Use Arrays
- When you need fast random access to elements using an index (O(1)).
- For storing a collection of elements of the same data type, ensuring memory efficiency.
- Arrays are commonly used to implement other data structures like stacks, queues, and heaps due to efficient indexed memory access.
Time Complexity Summary
| Operation | Time Complexity | Notes |
|---|---|---|
| Access | O(1) | |
| Update | O(1) | |
| Traversal | O(n) | Visit every element |
| Search | O(n) / O(log n) | Linear scan / Binary search (if sorted) |
| Insertion | O(n) | Requires shifting elements |
| Deletion | O(n) | Requires shifting elements |