Arrays

Introduction

An array is the simplest linear data structure — a collection of elements of the same type stored in contiguous memory locations, accessed by an integer index. Because all elements live side by side and are the same size, the address of element i can be computed as base + i * size in constant time. This makes index access O(1), which is why arrays are the building block of almost every other data structure.

Declaration and Initialization

int a[5];            // C: uninitialized
int b[5] = {1,2,3};  // C: partially initialized, rest = 0
int[] c = new int[5]; // Java: zero-initialized
int[] d = {1,2,3,4,5}; // Java

Memory Layout

A 1-D array of n elements each of size s occupies n * s bytes. The address of a[i] is &a[0] + i * s. A 2-D array a[m][n] is typically stored in row-major order: row 0 first, then row 1, and so on. The address of a[i][j] is &a[0][0] + (i * n + j) * s.

Operations

Linear Search

int search(int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key) return i;
    return -1;
}

Binary Search

Binary search works only on a sorted array. It repeatedly halves the search range:

int bsearch(int a[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Insertion and Deletion

// Insert x at position p in array a of size n
for (int i = n; i > p; i--) a[i] = a[i-1];
a[p] = x;
// Delete element at position p
for (int i = p; i < n - 1; i++) a[i] = a[i+1];

Both operations shift up to n elements and are O(n).

Two-Dimensional Arrays

A 2-D array is conceptually a matrix. Use nested loops to traverse:

int m[3][3];
for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
        m[i][j] = i * 3 + j;

Dynamic Arrays

Some languages provide dynamic arrays (C++ std::vector, Java ArrayList, Python list). Internally they allocate a fixed-size buffer and double its capacity when full, giving amortized O(1) append.

Advantages and Disadvantages

Advantages: random access in O(1), cache friendly (consecutive elements in memory), simple to implement. Disadvantages: fixed size in C-like arrays, costly insertion and deletion in the middle, wasted space if over-allocated.

Applications

Arrays implement stacks and queues internally, store image pixels and audio samples, back hash tables, and drive matrix/vector computations in linear algebra and graphics.

Summary

Arrays give O(1) random access through index arithmetic. Use them when you know the size in advance or can estimate it, and when random access dominates. Use linked lists when you need frequent insertions or deletions in the middle.

Important Questions

1. What is an array? List its advantages and disadvantages.
2. Derive the address formula for a[i][j] in row-major order.
3. Write an algorithm for linear search and analyze it.
4. Write an algorithm for binary search and analyze it.
5. Explain insertion and deletion in an array with complexity.
6. What is a dynamic array? Why is append amortized O(1)?
7. Differentiate row-major and column-major storage.
8. List three applications of arrays.