AlgoDocs

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

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.

  1. Use dynamic arrays (like vectors in C++ or Lists in Python) when size is unknown
  2. Consider using binary search for sorted arrays
  3. Use array indices carefully to avoid out-of-bounds errors
  4. 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:

  1. Array index out of bounds
  2. Not considering the cost of resizing
  3. Using arrays for frequent insertions/deletions
  4. Not initializing array elements
  5. Inefficient searching in unsorted arrays

How is this guide?