Array (data structure)

Introduction

An array is a fundamental data structure used in computer science and programming. It is a collection of elements, each identified by at least one index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula. The simplicity and efficiency of direct access make arrays a practical choice for many programming tasks.

Characteristics

Arrays are characterized by the number of dimensions and the size of each dimension. The total number of elements in an array is the product of the sizes of all its dimensions, and the maximum number of dimensions an array can have depends on the language. Some languages may impose a limit of 32 or 64 dimensions, while others may allow unlimited dimensions.

An image of a 3-dimensional array represented in a grid format.

Types of Arrays

There are several types of arrays, including:

One-dimensional Arrays

A one-dimensional array (also known as a single-dimensional array, 1-D array, vector, or simply an array) has exactly one dimension and a linear sequence of elements. For example, "int numbers[5]" declares an array that can hold five integers.

Multi-dimensional Arrays

A multi-dimensional array is an array of arrays. A two-dimensional array is the simplest form of a multi-dimensional array. For example, "int numbers[5][4]" declares a two-dimensional array that can hold twenty integers.

Dynamic Arrays

A dynamic array (also known as a resizable array, dynamic table, mutable array, or array list) is a random access, variable-size list data structure that allows elements to be added or removed.

Associative Arrays

An associative array (also known as a map, symbol table, or dictionary) is an abstract data type composed of a collection of pairs, such that each pair contains a unique key and value.

Operations

Common operations performed on arrays include:

Initialization: Setting up the array with default or user-defined values.
Traversal: Visiting each element in the array, usually to perform some operation on it.
Insertion: Adding an element at a given index.
Deletion: Removing an element at a given index.
Search: Finding the location of an element with a given value.
Update: Changing the value of an element.

Applications

Arrays are used in various fields of computer science and programming. Some of the applications include:

Implementing other data structures: Many data structures, such as heaps, hash tables, and binary trees, can be implemented using arrays.
Database systems: Arrays are used in database systems to store data.
Computer graphics: Arrays are used to store pixels in an image, vertices in a mesh, or colors in a palette.
Scientific computing: Arrays are used to represent vectors and matrices in scientific computing.

Advantages and Disadvantages

Advantages of arrays include:

Random access: Arrays allow random access to elements, which makes accessing elements by their index fast.
Ease of use: Arrays are simple and easy to use.

Disadvantages of arrays include:

Fixed size: The size of an array is fixed at the time of creation and cannot be changed.
Wastage of memory: If the elements of an array are not fully utilized, it leads to wastage of memory.