Arrays

Understanding arrays as a data structure.

What are Arrays?

An array is one of the simplest and most commonly used data structures in programming. I like to think of it as a collection of items (like numbers or strings) stored in a fixed-size container. What makes arrays special is that all the elements are stored in a contiguous block of memory. This means that all the elements are laid out side by side in memory, making it easy and fast to access any element using its index.

For example, if I want to get the 3rd element, I can directly go to its memory address by adding an offset to the start of the array. That’s why accessing elements in an array takes constant time, or O(1).

Types of Arrays

1. One-Dimensional Arrays

This is the most basic type of array where elements are arranged in a straight line. Think of it like a list of items.

2. Two-Dimensional Arrays

This is essentially a matrix, where data is stored in rows and columns. It's often used for grid-based problems like games or spreadsheets.

3. Multi-Dimensional Arrays

If you go beyond 2D, you enter the world of 3D or even higher dimensions. These are less common but can be useful in scenarios like 3D modeling.

Memory Storage in Arrays

Arrays are stored in contiguous memory, meaning all elements are stored one after another in a single block of memory. For example, if the first element is stored at memory location 1000, and each element takes 4 bytes, the second element will be at 1004, the third at 1008, and so on. This is why arrays are so efficient for random access. However, this also means that you can't dynamically resize them without creating a new array.

Common Array Operations

  • Access Operations

    • Get element at index: O(1)
    • Set element at index: O(1)
    • Get array length: O(1)

  • Search Operations

    • Linear Search: O(n)
    • Binary Search (sorted array): O(log n)
    • Find minimum/maximum: O(n)

  • Modification Operations

    • Insert at end: O(1)
    • Insert at beginning/middle: O(n)
    • Delete from end: O(1)
    • Delete from beginning/middle: O(n)
    • Reverse array: O(n)
    • Rotate array: O(n)

Code Examples

Here’s how you can define and use arrays in C++, Python, and Java. I've kept the examples simple, showing how to create, initialize, and access arrays.

# One-dimensional array
arr = [10, 20, 30, 40, 50]

# Accessing elements
print("First element:", arr[0])

# Two-dimensional array
matrix = [[1, 2], [3, 4]]
print("Element at [1][0]:", matrix[1][0])

Problems to Solve

Important Problems on Arrays

Resources