What are arrays?

When it comes to programming, arrays are one of the most important and frequently used data structures.

Introduction

What I am going to talk about is …

What are arrays?

Why are they useful? Where are they used?

Give examples of usage. Like to solve problem X or problem Y

How can they be used?

They are the building blocks of other structures such as queues, lists, etc… They are used everywhere

There are mainly two big types: static and dynamic arrays

Static Arrays

Static arrays are a contiguous block of memory with a fixed size.

Arrays are mutable. I can not change their size but I can change the contents.

The memory is allocated at compile time.

In C++ all arrays are references and each value of an array is its address. In C++, arrays also do not know how many elements they have. This has to be controlled by an adjacent variable.

// Declaring arrays in the stack
int a[5];                    // Values contain garbage
int b[5] = {1, 2, 3, 4, 5};  // Values are initialized

// Declaring arrays in the heap
int* c = (int*) calloc(5, sizeof(int));  // Values are initialized to 0
int* d = (int*) malloc(5 * sizeof(int)); // Values contain garbage

// More modern way of creating an array
std::array<int, 5> e = {1, 2, 3, 4, 5};                  // In the stack
std::unique_ptr<int[]> f = std::make_unique<int[]>(5);   // In the heap

In Python, does not support arrays. Instead, it has lists which are dynamic arrays. We will go over them a bit later.

Updating & Fetching

Changing or fetching elements at a specific point in the array can be done in O(1) time complexity. This can be done in O(1) time due to directly querying the value given a memory address.

Example array and how to access elements

In C++, we can update and fetch elements as follows:

// Modifying elements
a[0] = 1;
c[2] = 1;
d[3] = 1;

// Accessing elements (and printing them)
std::cout << "b[1] = " << b[1] << std::endl;
std::cout << "c[1] = " << c[1] << std::endl;
std::cout << "e[1] = " << e[1] << std::endl;

Searching

Finding if a given element exists in an array might require us to loop over all elements present in it. As such, it has a time complexity of O(n).

How to find elements in an array

In C++, we can search for elements as follows:

// Checking if an element exists in the array. It loops over all elements
if (std::find(std::begin(b), std::end(b), 3) != std::end(b)) {
  std::cout << "3 is in the array" << std::endl;
} else {
  std::cout << "3 is not in the array" << std::endl;
}

Insertion & Deletion

We can’t add more elements or delete elements from this array because it has a fixed size. Even though this is a bit limiting, this emulates very closely how computer memory actually works.

If we want it to be more flexible, we need to use a dynamic array.

Dynamic Arrays (Lists)

Dynamic arrays, most commonly refered to as Lists, do not have a fixed size. They can grow or shrink as needed.

This behaviour is implemented using static arrays. When we need to insert and the array is full, a new array is created with a larger size and the contents of the old array are copied to the new one. Afterwards, the new element is inserted and the old array is deleted. This has an O(n) time complexity.

This creates the illusion of a dynamic array whose size can change.

In Python, this is done automatically and is usually called a list:

# Declaring a list
l1 = []                             # Empty list
l2 = [1, 'hello', 3.14, True, 'd']  # List with elements

When a Python list has to be increased in size, the new size is usually double the old size. This is done to ammortize the cost of copying elements to the new array, thus making this operation O(1) on average.

As for C++, the most common and recommended way to use dynamic arrays in modern C++ is with std::vector, which provides automatic memory management, bounds checking, and many helpful member functions for working with arrays:

// Declaring dynamic arrays
std::vector<int> a;        // Create an empty vector
std::vector<int> b(5);     // Create a vector with 5 elements
std::vector<int> c(5, 1);  // Create a vector with 5 elements initialized to 1

Updating & Fetching

This is the same as static arrays. We can access and update existing elements in O(1) time complexity.

In Python, we can update and fetch elements as follows:

# Modifying elements
l1[0] = 1
l2[2] = 3.14

# Accessing elements (and printing them)
print(l1[0])
print(l2[2])

In C++, we can update and fetch elements as follows:

// Modifying elements
a[0] = 1;
b[2] = 1;
c[3] = 2;

// Accessing elements (and printing them))
std::cout << "b[2] = " << b[2] << std::endl;
std::cout << "c[3] = " << c[3] << std::endl;

Searching

Also the same as static arrays. We can find elements in O(n) time complexity.

In Python, we can search for elements as follows:

# Searching for an element (loops over all elements)
print('hello' in l2)  # True
print(1 in l1)        # False

In C++, we can search for elements as follows:

// Searching for an element
if (std::find(a.begin(), a.end(), 3) != a.end()) {
  std::cout << "3 is in the array" << std::endl;
} else {
  std::cout << "3 is not in the array" << std::endl;
}

Insertion

Inserting elements in a dynamic array is a bit more complex.

For inserting at the end of the array (right side of the array), we need to consider two scenarios:

1. Array is not full: We can simply insert the new element at the end of the array at the next available index. This has a time complexity of O(1).
2. Array is full: We need to create a new array with a larger size, copy the contents of the old array to the new one, and then insert the new element. This means that inserting elements at the end of the array has a time complexity of O(n).

Overall, this means that inserting elements at the end of the array has a time complexity of O(n).

However, insertion at the end of dynamic array, in practice, is usually O(1). As mentioned above, the new array is created with a size that is double the old array. This trick amortizes the time complexity of inserting elements at the end of the array and makes it O(1) on average.

When inserting elements at the start of the array (left side of the array) or in the middle, we need to shift all elements to the right to make space for the new element. This has a time complexity of O(n). In this case, if the array is full, we would also need to create a new array with a larger size.

How to mimic inserting elements in a dynamic array

In Python, we can insert elements as follows:

# Inserting elements
l1.append(2)           # Insert at the end
l2.insert(1, 'world')  # Insert at the start

In C++, we can insert elements as follows:

// Inserting elements
a.push_back(1);              // Append 1 at the end
a.insert(a.begin() + 1, 2);  // Insert 2 at the beginning

Deletion

Deleting can also be a bit tricky.

For deleting elements at the end of the array, we can simply remove the last element in O(1) time complexity.

For deleting elements at the start or the middle of the array, we need to shift all elements to the left to fill the gap created by the deleted element. This has a time complexity of O(n).

How to delete elements in a dynamic array

In Python, we can delete elements as follows:

# Removing elements
l1.pop()               # Remove last element
l2.remove('hello')     # Remove by value
l2.pop(1)              # Remove by index

In C++, we can delete elements as follows:

// Removing elements
a.pop_back();                // Remove the last element
a.erase(a.begin());          // Remove the first element
a.erase(a.begin() + 1);      // Remove the second element

Summary

Arrays are fundamental structures that allow efficient data storage and access. While static arrays offer fast access and fixed size, dynamic arrays give the flexibility of resizing.

Sources

• Video on YouTube by Greg Hogg
• University of Washington: Arrays
• Detailed Python list implementation

Full Code

#include <stdlib.h>
#include <iostream>
#include <array>

int main() {

// Declaring arrays in the program stack
int a[5]; // Values contain garbage
int b[5] = {1, 2, 3, 4, 5}; // Values are initialized

// Declaring arrays in the heap
int* c = (int*) calloc(5, sizeof(int)); // Values are initialized to 0
int* d = (int*) malloc(5 \* sizeof(int)); // Values contain garbage

// More modern way of creating an array
std::array<int, 5> e = {1, 2, 3, 4, 5}; // In the stack
std::unique_ptr<int[]> f = std::make_unique<int[]>(5); // In the heap

// Modifying elements
a[0] = 1;
c[2] = 1;
d[3] = 1;

// Accessing elements
std::cout << "b[1] = " << b[1] << std::endl;
std::cout << "c[1] = " << c[1] << std::endl;
std::cout << "e[1] = " << e[1] << std::endl;

// Checking if an element exists in the array. It loops over all elements
if (std::find(std::begin(b), std::end(b), 3) != std::end(b)) {
std::cout << "3 is in the array" << std::endl;
} else {
std::cout << "3 is not in the array" << std::endl;
}

// Freeing memory
free(c);
free(d);
return 0;
}

#include <stdlib.h>
#include <iostream>
#include <vector>

int main() {

  // Declaring dynamic arrays
  std::vector<int> a;        // Create an empty vector
  std::vector<int> b(5);     // Create a vector with 5 elements
  std::vector<int> c(5, 1);  // Create a vector with 5 elements initialized to 1

  // Appends elements at the end
  a.push_back(1);
  a.push_back(2);
  a.push_back(3);

  // Modifying elements
  a[0] = 1;
  b[2] = 1;
  c[3] = 2;

  // Accessing elements
  std::cout << "b[2] = " << b[2] << std::endl;
  std::cout << "c[3] = " << c[3] << std::endl;

  // Searching for an element
  if (std::find(a.begin(), a.end(), 3) != a.end()) {
    std::cout << "3 is in the array" << std::endl;
  } else {
    std::cout << "3 is not in the array" << std::endl;
  }

  // Inserting elements
  a.push_back(1);              // Append 1 at the end
  a.insert(a.begin() + 1, 2);  // Insert 2 at the beginning

  // Removing elements
  a.pop_back();                // Remove the last element
  a.erase(a.begin());          // Remove the first element
  a.erase(a.begin() + 1);      // Remove the second element

  return 0;
}

# Declaring a list
l1 = []                             # Empty list
l2 = [1, 'hello', 3.14, True, 'd']  # List with elements

# Modifying elements

l1[0] = 1
l2[2] = 3.14

# Accessing elements

print(l1[0])
print(l2[2])

# Searching for an element

print('hello' in l2) # True
print(1 in l1) # False

# Inserting elements

l1.append(2) # Insert at the end
l2.insert(1, 'world') # Insert at the start

# Removing elements

l1.pop() # Remove last element
l2.remove('hello') # Remove by value
l2.pop(1) # Remove by index