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:

Array Visualization

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

// 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