Array Data Structure

Basics of Array Data Structure
🔗
Pointers and arrays
🔗
Overview of Arrays and Memory
🔗
Data Structures and Arrays
🔗
Click here to suggest a better video
Click here to view videos suggested by visitors

An array is a very basic data structure used to efficiently store and manage a collection of elements by using a continuous block of computer memory. This memory used by an array is divided into a series of sequential compartments, or slots and each slot can store a single item of information. The items stored within the array can be accessed or modified instantly by using their unique identifiers, known as indices or slot numbers.

Key Features of an Array Data Structure:

  1. Contiguous Memory: Arrays allocate a block of memory that is contiguous, meaning the elements are stored in adjacent memory locations. This property enables quick access to individual elements using their index numbers.
  2. Fixed Size: Arrays have a predetermined size defined at the time of creation. Once the size is set, it remains constant throughout the program execution. This fixed size ensures predictable memory allocation and efficient memory management.
  3. Random Access: Arrays support direct access to elements based on their index. By specifying the index value, we can instantly retrieve or modify the object stored in the corresponding slot. This feature allows for quick and efficient data retrieval.

Structure of an Array

Below is how the structure of an array looks like:

A continuous section of memory space (the area highlighted in blue) is allocated for Array a. This continuous memory space is further divided into 6 slots and each slot can store an element inside it. Here the allocated size of the array becomes 6 (Since the memory is allocated to store a maximum of 6 items). However the actual size of all elements stored in the array is 4, since only the first 4 locations are used for storage.

Typically, all the slots in the arrays are fully used without any vacancies. In case if the array needs to be partially used, there has to be a variable which stores the total number of slots which are currently in use. This allows us to know from which index empty slots start from. For example a variable maxLength can store the maximum number of elements the array can store and length variable to store the actual number of elements stored in the array.

Each slot in the array is numbered starting from 0. So the first slot is identified by number 0, the second slot by number 1, the third slot by number 2 etc. So in order to access the third item stored in the array, we can use the corresponding slot’s number like this: a[2]. The number used to identify a slot is termed as the index of that slot. So for the second slot/item, the index is 1, for the third slot/item, the index is 2 etc.

Example situations when an Array Necessary

Any program running on a computer requires storing and accessing of data temporarily. For example, if we write a program to add two numbers, we need to take input the two numbers to add and store them temporarily before adding them and displaying the result.

If the operation we need to do is simple and requires only a few variables, we can store the values in separate variables and perform the operation. For example, if we wish to add two numbers, we can initialize two numbers a and b and create a formula a+b to add the numbers.

But what if we need to add 10 numbers? sure we can initialize 10 variables with names as a1, a2, a3 .. to a10, store all numbers in those variables and add them up using the expression result = a1 + a2 + a3 + ... a10. But what if the number of numbers to add change dynamically? or if the number of numbers to add is very large? This is where an array is really useful.

We can initialize an array to store any number of items we desire and then we can iterate / go through each slot in the array and access the item. For example, if we wish to store 100 items, we can initialize an array like items[100] and start filling each item starting from index 0. So we fill items[0] first, items[1] next and finally items[99]. After filling all the items, we can go through each item and perform required operation like addition, finding the maximum element etc.

TODO: Add practical example using library shelf as memory and books as elements stored in it.

Example of Array Declaration and usage

Below are code examples provided in various programming languages which demonstrate how to create and initialize an array, and how to access/modify individual elements present in the array.


#include <stdio.h>

int main() {
    // Declare and initialize an integer array
    int numbers[] = {1, 2, 3, 4, 5};

    // Access individual elements by index
    printf("Element at index 2: %d\n", numbers[2]);
    // Element at index 2 is 3

    // Update an element by index
    numbers[2] = 10;

    // Print the updated element
    printf("Updated element at index 2: %d\n", numbers[2]);
    // After the update, element at index 2 is 10

    return 0;
}

Basic Operations on an Array Data Structure

Following are the basic operations supported by an array:

  • Access/Update an element at a given index
  • Traversal: Go/Iterate through all elements in the array one by one. For example, if we wish to add up all elements in the array, we traverse through the array and keep adding each element we visit to a common sum.
  • Insertion: Adds an element at the given index.
  • Removal/Deletion: Delete an element at the given index.
  • Search: Search for an element for a value and get the index if the value exists.

In the next section we discuss all the operations in detail along with code.

References