Arrays

Definition and Structure

What is an Array?

Array: collection of elements of identical type stored contiguously. Purpose: enable indexed access. Structure: linear data structure. Use case: store fixed-size sequential data.

Element Uniformity

All elements share data type: integer, float, object, etc. Ensures uniform memory size and type safety. Facilitates efficient access and manipulation.

Sequential Layout

Elements stored in contiguous memory locations. Allows constant-time access via offset calculation. Enhances cache locality and performance.

Fixed Size

Array size defined at creation. Static arrays: size fixed during compile or runtime. Limits flexibility but improves predictability and speed.

Types of Arrays

One-Dimensional Arrays

Linear sequence of elements. Access via single index. Examples: list of integers, sequence of characters.

Multidimensional Arrays

Arrays of arrays. Commonly 2D or 3D. Used for matrices, grids, tensors. Access via multiple indices.

Jagged Arrays

Arrays with subarrays of variable lengths. Non-rectangular shape. Useful for irregular data structures.

Associative Arrays

Also called maps or dictionaries. Key-value pairs instead of integer indexing. Implemented differently, not contiguous arrays.

Memory Allocation and Layout

Contiguous Allocation

Memory block allocated in continuous addresses. Enables direct offset calculation. Reduces fragmentation and overhead.

Static vs Dynamic Allocation

Static arrays: fixed size at compile-time or runtime. Dynamic arrays: allocated during execution, size adjustable.

Row-major and Column-major Order

Multidimensional arrays stored in linear memory. Row-major: rows contiguous. Column-major: columns contiguous. Language-dependent.

Memory Overhead

Minimal overhead beyond element storage. No pointer indirection in static arrays. Dynamic arrays may incur overhead for resizing.

Cache Locality

Sequential layout improves CPU cache performance. Prefetching and reduced cache misses enhance speed.

Basic Operations

Traversal

Visiting each element sequentially. Used in printing, searching, modification.

Insertion

Static arrays: requires shifting elements to make space. Dynamic arrays: amortized efficient insertion at end.

Deletion

Requires shifting elements to fill space. Static arrays: costly, O(n) time. Dynamic arrays: resizing may be required.

Searching

Linear search: O(n), unsorted arrays. Binary search: O(log n), requires sorted arrays.

Sorting

Organizing elements in order. Algorithms: quicksort, mergesort, heapsort, bubble sort (inefficient).

Indexing and Access

Index Calculation

Access element at index i: base_address + i * element_size. Constant time complexity O(1).

Bounds Checking

Ensures index within valid range. Prevents memory corruption. Some languages enforce; others rely on programmer.

Zero-based vs One-based Indexing

Zero-based: first element at index 0 (C, Java). One-based: first element at 1 (MATLAB, Fortran).

Negative Indexing

Supported in some languages (Python). Allows accessing elements from end backward.

Multidimensional Arrays

Definition

Array where each element is itself an array. Dimensions specify depth and complexity.

Access Patterns

Elements accessed via multiple indices: A[i][j] for 2D. Nested loops typical for traversal.

Storage Order

Row-major: rows stored contiguously. Column-major: columns contiguous. Affects performance and interfacing.

Use Cases

Matrices, images, game boards, scientific computations.

Dynamic Arrays

Definition

Arrays that can grow or shrink during program execution. Implemented with resizing.

Resizing Mechanism

When full, allocate larger array, copy elements, free old array. Amortized insertion time O(1).

Common Implementations

Vectors in C++, ArrayList in Java, lists in Python (dynamic array under the hood).

Trade-offs

Flexibility vs overhead of resizing and copying. Memory fragmentation possible.

Algorithms on Arrays

Sorting Algorithms

Quicksort: average O(n log n), divide and conquer. Mergesort: stable, O(n log n). Bubble sort: O(n²), simple but inefficient.

Searching Algorithms

Linear search: O(n). Binary search: O(log n), requires sorted array.

Traversal Algorithms

Iterative loops. Recursive algorithms for specific problems (e.g., divide and conquer).

Partitioning

Used in quicksort and selection algorithms. Rearranges array based on pivot element.

Dynamic Programming

Arrays used for memoization and tabulation in optimization problems.

Time and Space Complexity

Access

Direct indexing: O(1) time. Major advantage over linked structures.

Search

Unsorted arrays: O(n) linear search. Sorted arrays: O(log n) binary search.

Insertion and Deletion

Static arrays: O(n) due to shifting. Dynamic arrays: amortized O(1) at end, O(n) in worst case.

Space Usage

Contiguous block of memory. No overhead per element. Dynamic arrays may over-allocate for growth.

Cache Efficiency

High due to locality of reference. Improves runtime performance.

Applications of Arrays

Data Storage

Storing fixed collections of related data, e.g., sensor readings, database rows.

Algorithm Implementation

Foundations for sorting, searching, dynamic programming, and graph algorithms.

Matrix and Image Processing

Multidimensional arrays represent matrices, images, voxel data for processing.

Buffer Management

Used in IO buffering, audio/video streaming, communication protocols.

Lookup Tables

Precomputed values stored for constant-time retrieval, e.g., sine tables, hash tables.

Advantages and Disadvantages

Advantages

Fast access via indexing. Simple structure. Low memory overhead. Cache friendly.

Disadvantages

Fixed size limits flexibility. Expensive insertions/deletions in middle. Contiguous memory may cause fragmentation.

Static vs Dynamic Trade-offs

Static: predictable, fast. Dynamic: flexible, overhead incurred.

Alternatives Needed for Sparse Data

Arrays inefficient for sparse or irregular datasets. Linked lists or hash tables preferred.

Comparison with Other Data Structures

Arrays vs Linked Lists

Arrays: O(1) access, costly insertion/deletion. Linked lists: O(n) access, cheap insertion/deletion.

Arrays vs Trees

Trees: hierarchical data, dynamic size, complex traversal. Arrays: linear, simpler usage.

Arrays vs Hash Tables

Arrays: fixed keys (indices), ordered. Hash tables: key-value, unordered, average O(1) access.

Arrays vs Stacks and Queues

Stacks/queues are abstract data types, often implemented with arrays. Arrays provide underlying storage.

When to Use Arrays

When fixed-size, fast access, and memory efficiency are priorities.

References

• Aho, A.V., Hopcroft, J.E., Ullman, J.D., "Data Structures and Algorithms," Addison-Wesley, 1983, pp. 45-72.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., "Introduction to Algorithms," MIT Press, 3rd ed., 2009, pp. 97-134.
• Sedgewick, R., Wayne, K., "Algorithms," Addison-Wesley, 4th ed., 2011, pp. 56-89.
• Kernighan, B.W., Ritchie, D.M., "The C Programming Language," Prentice Hall, 2nd ed., 1988, pp. 105-120.
• Knuth, D.E., "The Art of Computer Programming, Volume 1: Fundamental Algorithms," Addison-Wesley, 3rd ed., 1997, pp. 200-245.

Code Examples

Index Calculation Formula

address = base_address + (i * element_size)

Dynamic Array Resizing Algorithm

function append(element): if size == capacity: new_capacity = capacity * 2 allocate new array with new_capacity copy old elements to new array free old array capacity = new_capacity array[size] = element size += 1

Summary Tables

Array Types and Characteristics

Operations Time Complexity

Introduction

Arrays are the most fundamental data structure in computer science, providing a means to store multiple elements in a contiguous block of memory with indexed access. They form the basis for more complex data structures and algorithms, enabling efficient data manipulation and retrieval.

"The array is the simplest data structure, yet it forms the foundation of efficient algorithm design." -- Donald Knuth