Introduction to Linear Data Structures: Arrays

Definition

An array is a linear data structure that stores a collection of elements of the same data type in contiguous memory locations, and each element can be accessed directly using an index.

Example

If an array stores five integers:

A = [10, 20, 30, 40, 50]

Then:

A[0] = 10
A[1] = 20
A[2] = 30
A[3] = 40
A[4] = 50

Here, the elements are stored one after another in memory, and indexing helps us identify each element quickly.

Main Content

1. Characteristics of Arrays

Homogeneous elements

Arrays store elements of the same type only. For example, an integer array can store integers, a character array can store characters, and so on. This uniformity makes arrays simple to process and efficient in memory usage.

Contiguous memory allocation

All elements of an array are stored in adjacent memory locations. This means if one element starts at a certain address, the next element is stored immediately after it according to the size of the data type. Because of this, arrays allow fast direct access to any element.

Fixed size in many languages

In basic array implementation, the size is decided at the time of creation and usually cannot be changed easily. This makes arrays suitable when the amount of data is known beforehand, but less flexible when data size changes frequently.

Example of memory arrangement

Suppose an integer array has 5 elements and each integer occupies 4 bytes:

Index:     0      1      2      3      4
Value:    15     25     35     45     55
Address: 1000   1004   1008   1012   1016

This contiguous placement is what makes array access very fast.

2. Indexing and Accessing Elements

Index-based access

Every element in an array is identified by an index. In most programming languages, indexing starts from 0, so the first element is at index 0, the second at index 1, and so on. This allows direct access to any element without traversing the whole array.

Random access feature

Arrays support random access, meaning any element can be accessed in constant time O(1) if the index is known. This is one of the biggest advantages of arrays compared to sequential structures like linked lists.

Address calculation

The address of any array element can be calculated using a formula:
Address of A[i] = Base Address + (i × Size of each element)
This is possible because elements are stored contiguously.

Example

If:

Base address of array = 2000
Size of each integer = 4 bytes
Index = 3

Then address of A[3] is:

2000 + (3 × 4) = 2012

So the element at index 3 is quickly reached without scanning earlier elements.

3. Types, Operations, and Limitations of Arrays

Types of arrays

Arrays can be one-dimensional, two-dimensional, or multidimensional.

1D array: Used for linear list-like data, such as marks of students.
2D array: Used for tables or matrices, such as a timetable or spreadsheet.
Multidimensional array: Used for more complex structured data.

Common operations on arrays

Traversal: Visiting each element one by one.
Insertion: Adding an element at a given position.
Deletion: Removing an element from a given position.
Searching: Finding a particular value.
Updating: Changing an element’s value.
Sorting: Arranging elements in ascending or descending order.

Limitations of arrays

Size is often fixed, so memory may be wasted if the array is larger than needed.
Inserting or deleting in the middle is costly because elements must be shifted.
Arrays store only similar data types, so they are not suitable for mixed-type collections in basic form.

Example of insertion shift

If the array is:

[10, 20, 30, 40]

and we insert 25 at index 2, the elements must shift:

[10, 20, 25, 30, 40]

This shifting makes insertion expensive compared to access.

2D Array Example

A matrix can be represented as:

This is useful in applications like image processing, scientific computation, and tabular data storage.

Working / Process

1. Declare the array and allocate memory

First, the array is created with a specific size. The memory is reserved in contiguous blocks so that all elements can be stored next to each other. For example, an array of 5 integers reserves space for exactly 5 integer values.

2. Store elements in the reserved positions

Each value is placed into the array at a particular index. The first value goes to index 0, the second to index 1, and so on. The programmer or system uses indexing to manage where each item is stored.

3. Access, modify, or process elements using indices

Once stored, elements can be accessed directly using their index. Operations like searching, updating, printing, summing, or sorting are performed by moving through the array or using a specific index. Since the positions are known, accessing an element is fast and efficient.

Advantages / Applications

Fast access to elements

Arrays provide direct access to any element by index, making reading and updating data very quick.

Simple and easy to implement

Arrays are one of the easiest data structures to understand and use, which makes them an ideal starting point for learning data structures and algorithms.

Widely used in real-world applications

Arrays are used in storing exam marks, sensor readings, image pixels, lookup tables, matrices, game boards, and many other forms of structured data.

Summary

Arrays are linear data structures used to store same-type elements in contiguous memory.
They allow direct access through indexing, which makes them efficient for retrieval and processing.
Arrays are useful for many basic and advanced programming tasks, especially where data size is known.