Data Structure (1) - Array

Data Structure Series

Data Structure Series

Topics

• What is Array?
• Static Array
• Dynamic Array
• Difference between Static Array and Dynamic Array
• Basic Operations
• Applications
• Summary

What is Array?

Before diving into Array, let’s first understand what data structure is. A data structure is a way of organizing and storing data in a computer so that it can be accessed and modified efficiently. Array is one of the most basic data structures that store data in contiguous memory locations.

An array is a collection of elements, each identified by at least one array index. The simplest data structure is a linear array, also known as one-dimensional array. A person can store different types of data in an array, such as integers, floating-point numbers, characters, strings, and even objects.

There are two types of arrays: static array and dynamic array. Which will be explained in the following sections.

Static Array

Now that we have a basic understanding of what array is, let’s take a look at what static array is. A static array is a type of array that has a fixed size. Meaning that once the array is created, its size cannot be changed. Here are some examples of static array in different programming languages:

Python

Technically, Python does not have a built-in static array.

arr = [1, 2, 3, 4, 5]

C++

int arr[5] = {1, 2, 3, 4, 5};

C#

int[] arr = {1, 2, 3, 4, 5};

The size of the array is fixed at 5, meaning that we cannot add or remove elements from the array once it is created.

Dynamic Array

Dynamic array is a type of array that has a variable size. Meaning that the size of the array can be changed during the execution of the program. Here are some examples of dynamic array in different programming languages:

Python

arr = [1, 2, 3, 4, 5]

C++

std::vector<int> arr = {1, 2, 3, 4, 5};

C#

List<int> arr = new List<int> {1, 2, 3, 4, 5};

Difference between Static Array and Dynamic Array

The key difference between static array and dynamic array is the size of the array. Static array has a fixed size, while dynamic array has a variable size. Here is a table that goes in depth to summarize the difference between static array and dynamic array:

Feature	Static Array	Dynamic Array
Memory Allocation	Occurs at compile time	Occurs at runtime
Resizability	Fixed size remains constant	Resizable, can grow or shrink dynamically
Ease of Use	Simpler to use	More flexible, but requires manual management in low-level languages
Performance	Faster access time and manipulation	Slower in resizing scenarios

Basic Operations

There are several basic operations that can be performed on an array. Here are some of them:

• Accessing an element: Accessing an element in an array is a constant time operation, meaning that it takes $O(1)$ time to access an element in an array.
• Searching an element: Searching an element in an array is a linear time operation, meaning that it takes $O(n)$ time to search an element in an array.
• Insertion: Inserting an element in an array is a linear time operation, meaning that it takes $O(n)$ time to insert an element in an array.
• Deletion: Deleting an element in an array is a linear time operation, meaning that it takes $O(n)$ time to delete an element in an array.

Here are some examples of how to perform these operations in different programming languages:

Python

# Example array
arr = [1, 2, 3, 4, 5]

# Accessing an element          
# This operation returns the first element of the array
print(arr[0]) 

# Searching for the element 3  
# This operation returns the index of the first occurrence of the element 3 in the array
print(arr.index(3)) 

# Inserting the element 6      
# This operation appends the element 6 to the end of the array
arr.append(6) 

# Deleting the element 4       
# This operation removes the first occurrence of the element 4 in the array
arr.remove(4) 

C++

#include <iostream>
#include <vector>

int main() {
    // Example array                        
    std::vector<int> arr = {1, 2, 3, 4, 5};

    // Accessing an element                
    std::cout << arr[0] << std::endl;

    // Searching for the element 3         
    std::cout << std::find(arr.begin(), arr.end(), 3) - arr.begin() << std::endl;

    // Inserting the element 6             
    arr.push_back(6);

    // Deleting the element 4              
    arr.erase(std::remove(arr.begin(), arr.end(), 4), arr.end());
}

C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        // Example array                      
        List<int> arr = new List<int> {1, 2, 3, 4, 5};

        // Accessing an element              
        Console.WriteLine(arr[0]);

        // Searching for the element 3       
        Console.WriteLine(arr.IndexOf(3));

        // Inserting the element 6           
        arr.Add(6);

        // Deleting the element 4            
        arr.Remove(4);
    }
}

Applications

There are many applications of array in real world. Here are some of them:

• Storing data: Array is a basic data structure that is used to store data in a contiguous memory location.
• Sorting: Array is used in sorting algorithms, such as bubble sort, selection sort, insertion sort, and merge sort.
• Searching: Array is used in searching algorithms, such as linear search and binary search.
• Graphs: Array is used in representing graphs, such as adjacency matrix and adjacency list.
• Dynamic Programming: Array is used in dynamic programming problems, such as the longest increasing subsequence and the longest common subsequence.

We can also use array to implement other data structures, such as stack, queue, and hash table.

Summary

Array is a basic data structure that is used to store data. It is a very important data structure that is used to store data and be used in many algorithms and problems.