Array Data Structure

Published on
🕒 4 min read
Authors

Introduction

An array is a linear data structure consisting of a collection of elements, each identified by at least one array index or key. It is one of the simplest and most widely used data structures, providing efficient access to elements based on their index.

Operations

Arrays support various operations, including:

  • Access: Accessing elements by index in constant time.
  • Insertion: Inserting elements at a specific index or appending them to the end of the array.
  • Deletion: Removing elements from a specific index or from the end of the array.
  • Search: Searching for elements in the array, which may require linear time in the worst-case scenario.
  • Traversal: Iterating over all elements of the array to perform certain operations.

Example

Consider an array representing the scores of students in a class:

[85, 92, 78, 95, 88]

Access: We can access the score of the third student (index 2) directly:

const scores = [85, 92, 78, 95, 88];
scores[2]
console.log(scores); // Output: 78

Insertion: If a new student scored 90 and needs to be added to the array, we can insert the score at the end:

const scores = [85, 92, 78, 95, 88];
scores.push(90);
console.log(scores); // Output: [85, 92, 78, 95, 88, 90]

Deletion: If the score of the second student needs to be removed, we can delete it from the array:

const scores = [85, 92, 78, 95, 88];
scores.splice(1, 1);
console.log(scores); // Output: [85, 78, 95, 88]

Search: To find if a score of 88 exists in the array, we can search for it: Found at index:

const scores = [85, 92, 78, 95, 88];
const index = scores.indexOf(88);
console.log(scores); // Output: 4

Traversal: We can iterate over all scores in the array to calculate the average:

const scores = [85, 92, 78, 95, 88];
let sum = 0;
for (let i = 0; i < scores.length; i++) {
    sum += scores[i];
}
const average = sum / scores.length;
console.log(average); // Output: 53

Advantages

  • Random Access: Arrays provide constant-time access to elements based on their index, making them suitable for applications where quick access is crucial.
  • Memory Efficiency: Arrays store elements in contiguous memory locations, optimizing memory usage and cache performance.
  • Versatility: Arrays can store elements of the same data type or different data types, making them versatile for various applications.

Disadvantages

  • Fixed Size: In many programming languages, arrays have a fixed size determined at the time of declaration, making it difficult to resize them dynamically.
  • Costly Insertions and Deletions: Insertions and deletions in the middle of an array require shifting elements, resulting in a higher time complexity.
  • Sparse Data: Arrays may waste memory space when storing sparse data, as memory is allocated for all indices regardless of whether they contain elements.

Application

Arrays are used in a wide range of applications, including:

  • Algorithm Implementations: Arrays are fundamental in implementing various algorithms, such as sorting algorithms (e.g., quick sort, merge sort) and searching algorithms (e.g., binary search).
  • Data Storage: Arrays are used to store data in databases, file systems, and memory structures.
  • Matrices and Vectors: Arrays are commonly used to represent matrices and vectors in mathematical computations, machine learning, and computer graphics.
  • Dynamic Programming: Arrays play a crucial role in dynamic programming algorithms, where they are used to store intermediate results and optimize recursive computations.

JavaScript Implementation

Arrays are a built-in data structure in JavaScript, and they can be instantiated and manipulated using the following syntax:

// Create an empty array
let myArray = [];

// Insert elements into the array
myArray.push(5);
myArray.push(10);
myArray.push(15);

// Access elements by index
console.log(myArray[0]); // Output: 5

// Delete elements from the array
myArray.pop(); // Remove the last element

// Search for elements in the array
console.log(myArray.indexOf(10)); // Output: 1 (index of element 10)

// Iterate over all elements of the array
for (let i = 0; i < myArray.length; i++) {
    console.log(myArray[i]);
}
Discuss on Twitter