Concept

An array is a data structure that stores items of the same data type at contiguous memory locations.

• Also known as a collection of variables of same memory size.
• Items that are next to each other are stored in memory right beside each other.

Each item is indexable, meaning that it can be referred to as a number. An item is also called an “element,” as shown in the following example of one-dimensional array.

    
    arr = ['t', 'h', 'i', 's', 'i', 's', 't', 'e', 's', 't']
    
    |  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |    i
    |---------+---+---+---+---+---+---+---+---+---+---|
    | Element | t | h | i | s | i | s | t | e | s | t |  arr[i]
    

For a multi-dimensional array, elements in the one-dimensional array are accessible with the first index. Also, each of them is an array which is accessible with the second index. In case of two-dimensional arrays, an element accessible with the second index is an actual item we have stored.

    
    arr = [
        ['h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd'],
        ['t', 'h', 'i', 's', 'i', 's', 't', 'e', 's', 't'],
        ['g', 'o', 'o', 'd', 'a', 'r', 'r', 'a', 'y', '!'],
    ]
    
    Index i := first index
    Index j := second index
    
    | i \ j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
    |-------+---+---+---+---+---+---+---+---+---+---|
    |   0   | h | e | l | l | o | w | o | r | l | d |
    |-------+---+---+---+---+---+---+---+---+---+---|
    |   1   | t | h | i | s | i | s | t | e | s | t |
    |-------+---+---+---+---+---+---+---+---+---+---|
    |   2   | g | o | o | d | a | r | r | a | y | ! |
    
    E.g., arr[i][j] = arr[0][2] = 'l'
    

Notice that a program throws an exception if it looks up arrays using any index outside the boundary.

There are two types of arrays.

• Static Array is a fixed length of array.
• Dynamic Array is an array that can grow and shrink in size.
  • Its boundary is defined as its capacity.

Static Array

A fixed size means no change in size. In other words, it is not allowed to do insertion, deletion, and addition.

Dynamic Array

A dynamic array is constructed using static arrays.

1. Create a fixed-size array with the initial capacity that is the upper bound of its size.
2. Fill this array with elements, keeping track of the number of elements.
3. If appending a new element exceeds the capacity, build a new static array with twice the capacity and copy the original elements into the new array.

It is possible to insert or delete an element in an array’s middle and even append it to the very end.

When to use

1. Storing and accessing sequential data
2. Temporarily storing objects
3. Used by IO routines as buffers
4. Lookup tables and inverse lookup tables
5. Returning multiple values from a function
6. Used in dynamic programming to cache answers to subproblems

Complexity

• $n$ is the size of an array.
• It takes linear time to search for a specific element in both arrays since iterating through an array is necessary to find the desired element.

Implementation

Python provides array module supporting a dynamic array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from array import array

""" 'u' means to use unicode characters. """
arr1 = array('u', 'this is an array')
print(arr1.index('s'))  # 3
print(arr1[0])          # 't'
print(arr1.count('a'))  # 3
arr1.reverse()
print(arr)              # array('u', 'yarra na si siht')

""" Delete at or append to the very end of an array. """
arr1.pop()              # 'y'
print(arr1)             # array('u', 'this is an arra')
arr1.append('y')
print(arr1)             # array('u', 'this is an array')

""" Delete at or append to the front of an array. """
arr1.remove('i')
print(arr1)             # array('u', 'ths is an array')
arr1.insert(2, 'i')
print(arr1)             # array('u', 'this is an array')

""" Integer array """
arr2 = array('l', [1, 2, 3])
""" Number array """
arr3 = array('d', [1.0, 2.0, 3.0])

Application

Leetcode

• See my list.