Introduction to Arrays
What is an Array?
An array is a linear data structure that collects elements of the same data type and stores them in contiguous and adjacent memory locations. Arrays use a zero-based index to randomly access elements in the array.
Arrays are among the oldest and most important data structures and are used by almost every program. They are also used to implement many other data structures like stacks, queues, heaps, hash tables, etc.
Key Characteristics of Arrays:
- Elements are stored in contiguous memory locations
- Elements can be accessed using index values (zero-based indexing in most languages)
- Arrays have a fixed size in many languages (static arrays)
- All elements must be of the same data type (in statically typed languages)
- Provides O(1) constant time access to any element by index
Real-World Analogy
Think of an array as a row of mailboxes, each with a unique number (index). You can directly access any mailbox by its number, just like you can access any array element by its index.
Types of Arrays
1. One-Dimensional Arrays
A one-dimensional array is a linear array where elements are arranged in a single row. It's the simplest form of an array.
2. Multi-Dimensional Arrays
Multi-dimensional arrays store elements in a tabular form with multiple rows and columns.
Array Representation in Memory
In memory, an array is represented as a contiguous block. For a one-dimensional array of size n, if the base address is B and the size of each element is S, then:
- Address of first element (index 0): B
- Address of second element (index 1): B + S
- Address of third element (index 2): B + 2S
- Address of ith element (index i): B + i*S
Advantages of Arrays
- Random access to elements using index
- Easy to traverse and iterate
- Memory locality improves cache performance
- Used to implement other data structures
Disadvantages of Arrays
- Fixed size (static arrays) – cannot grow or shrink dynamically
- Insertion and deletion are costly (O(n)) except at the end
- Wastage of memory if array size is overestimated
- All elements must be of the same data type
Interactive Array Visualization
Experiment with the array visualization below to understand how arrays store and access elements:
Array Visualization
Add Element
Access Element
Animation Speed
Theory and Key Terminology
As we progress through this tutorial, we will encounter various theoretical concepts and technical terms essential for understanding data structures and algorithms.
- Algorithm: A step-by-step procedure or set of rules designed to solve a specific problem.
- Data Structure: A structured way of organizing and storing data.
- Time Complexity: A measure of how long an algorithm takes to execute.
- Space Complexity: A measure of memory usage by an algorithm.
- Big O Notation: Expresses an algorithm’s efficiency in worst-case scenarios.
- Recursion: A function calling itself to solve a problem.
- Divide and Conquer: Breaking a problem into smaller subproblems.
- Brute Force: A straightforward problem-solving approach.
Why Learn Data Structures?
Data Structures and Algorithms are fundamental to Computer Science. They enhance programming skills and efficiency.
Objectives of Data Structures
- Correctness: Ensures accurate operation for all valid inputs.
- Efficiency: Optimizes performance while minimizing resource usage.
Key Features of Data Structures
- Robustness: Ensures correct execution across platforms.
- Adaptability: Supports long-term software evolution.
- Reusability: Enables cost-effective software development.