Array
An array is a linear data structure that stores a collection of elements, all of the same data type, in contiguous memory locations.
Understanding Arrays in Data Structures
An array is a linear data structure that stores elements of the same data type in contiguous memory locations. Each element can be accessed directly using an index, making it one of the most efficient data structures for element retrieval.
Visualizing Arrays
To better understand arrays, let’s visualize them:
Core Concepts
Memory Allocation
Arrays use contiguous memory blocks, meaning all elements are stored next to each other in memory.
Indexing
Each element is assigned a unique index (usually starting from 0) that can be used for direct access.
Homogeneous Elements
All elements in an array must be of the same data type (int, string, etc.) to maintain memory consistency.
Array Operations Implementation
1. Array Creation and Access
// Array creation
int arr[5] = {1, 2, 3, 4, 5};
// Accessing elements
cout << arr[0]; // First element
cout << arr[4]; // Last element
# Array creation
arr = [1, 2, 3, 4, 5]
# Accessing elements
print(arr[0]) # First element
print(arr[-1]) # Last element
// Array creation
let arr = [1, 2, 3, 4, 5];
// Accessing elements
console.log(arr[0]); // First element
console.log(arr[arr.length - 1]); // Last element
2. Array Traversal
// Using for loop
for(int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
// Using range-based for loop
for(int element : arr) {
cout << element << " ";
}
# Using for loop
for i in range(len(arr)):
print(arr[i], end=" ")
# Using for-each loop
for element in arr:
print(element, end=" ")
// Using for loop
for(let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
// Using forEach
arr.forEach(element => console.log(element));
3. Insertion and Deletion
// Using vector for dynamic arrays in C++
vector<int> arr = {1, 2, 3, 4};
// Insertion
arr.insert(arr.begin() + 2, 99); // Insert 99 at index 2
// Deletion
arr.erase(arr.begin() + 2); // Remove element at index 2
arr = [1, 2, 3, 4]
# Insertion
arr.insert(2, 99) # Insert 99 at index 2
# Or append at the end
arr.append(99)
# Deletion
del arr[2] # Remove element at index 2
# Or remove by value
arr.remove(99)
let arr = [1, 2, 3, 4];
// Insertion
arr.splice(2, 0, 99); // Insert 99 at index 2
// Or push at the end
arr.push(99);
// Deletion
arr.splice(2, 1); // Remove element at index 2
Time Complexity Analysis
Performance Characteristics
Common array operations have the following time complexities:
- Access: O(1)
- Search: O(n) for linear search, O(log n) for binary search (sorted arrays)
- Insertion: O(n) in worst case
- Deletion: O(n) in worst case
Array Types and Variations
1. One-Dimensional Arrays
The basic array type we've discussed above.
2. Multi-Dimensional Arrays
Arrays with multiple dimensions, like 2D arrays (matrices).
// 2D array
int arr[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
# 2D array
arr = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
// 2D array
let arr = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
3. Dynamic Arrays
Arrays that can grow or shrink in size.
- Use dynamic arrays (like vectors in C++ or Lists in Python) when size is unknown
- Consider using binary search for sorted arrays
- Use array indices carefully to avoid out-of-bounds errors
- Consider memory constraints for large arrays
Common Applications
Use Cases
Arrays are commonly used in:
- Implementing other data structures (stacks, queues)
- Sorting algorithms
- Matrix operations
- Buffer pools
- Lookup tables
Common Pitfalls:
- Array index out of bounds
- Not considering the cost of resizing
- Using arrays for frequent insertions/deletions
- Not initializing array elements
- Inefficient searching in unsorted arrays
How is this guide?