Array (Sequential Storage)

When we talk about "arrays," the meaning can be different because each programming language offers different types of arrays and APIs. So first, let's make the concept clear for this article.

We can think of "arrays" as two main types: "static arrays" and "dynamic arrays."

A static array is just a block of continuous memory. We can use an index to access elements in this memory. This is the original form of an array.

A "dynamic array" is something provided by programming languages to make things easier for us. It is based on static arrays but provides extra APIs like push, insert, remove, etc. These APIs help us work with array elements more easily. We don’t need to write extra code for these operations.

In this chapter, we will use only basic static arrays to build our own dynamic array. We will implement common APIs such as add, delete, search, and update. After learning this, you will understand how library data structures work inside.

With dynamic arrays, you can later understand and build queues, stacks, hash tables, and other complex data structures.

Static Array

When you create a static array, you must decide its element type and length in advance. Only languages like C++, Java, and Golang provide true static arrays. Languages like Python and Javascript do not.

Static arrays are very basic. In real-world software development, we hardly use them. For algorithm problems, there’s usually no need to use static arrays—we use dynamic arrays directly. However, it's still worth learning for basic understanding.

Here is how you define a static array:

// define a static array of size 10
int[] arr = new int[10];

// assign values using indices
arr[0] = 1;
arr[1] = 2;

// retrieve values using indices
int a = arr[0];

// define a static array of size 10
int arr[10];

// initialize the array values to 0 using memset function
memset(arr, 0, sizeof(arr));

// assign values using index
arr[0] = 1;
arr[1] = 2;

// retrieve values using index
int a = arr[0];

# Seriously, Python does not have a way to define static arrays
# We can use lists to simulate static arrays for now

# define a static array of size 10
arr = [0] * 10

# assign values using index
arr[0] = 1
arr[1] = 2

# retrieve values using index
a = arr[0]

// define a static array of size 10
var arr [10]int

// assign values using index
arr[0] = 1
arr[1] = 2

// retrieve values using index
a := arr[0]

// Seriously, JavaScript does not have a way to define static arrays
// We can use arrays to simulate static arrays for now

// define a static array of size 10
let arr = new Array(10);

// assign values using index
arr[0] = 1;
arr[1] = 2;

// retrieve values using index
let a = arr[0];

That's it. No more special operations.

Let’s use C++ as an example. What happens when you write int arr[10]? Mainly two things:

1. The system creates a continuous memory block in memory. The size is 10 * sizeof(int) bytes. If an int takes 4 bytes, the total is 40 bytes.

2. A variable arr is created, which points to the start of this memory block.

Now, what happens when you write arr[1] = 2? Mainly:

1. The program calculates the address: start of arr plus 1 * sizeof(int) (which is 4 bytes), to find the starting address of the second element.

2. It writes the integer 2 into the 4 bytes starting from this address.

Add, Delete, Search, Update

The main job of a data structure is to add, delete, search, and update elements. There is nothing else.

Earlier, when explaining the basics of arrays, we mainly talked about "search" and "update." That is, accessing and changing values by index. Now, let’s look at how to "add" and "delete" elements in arrays.

Add

Adding elements to a fixed-size array can be a bit tricky. There are several situations to consider.

For example, I have an array of size 10 with 4 elements in it. Now I want to add another element at the end. What should I do?

It’s very simple—just assign a value to the next index. Here is the basic code logic:

// An array of size 10 already contains 4 elements
int[] arr = new int[10];
for (int i = 0; i < 4; i++) {
    arr[i] = i;
}

// Now want to append an element 4 at the end of the array
arr[4] = 4;

// Then append an element 5 at the end of the array
arr[5] = 5;

// And so on
// ...

// An array of size 10 already has 4 elements
int arr[10];
for (int i = 0; i < 4; i++) {
    arr[i] = i;
}

// Now I want to add an element 4 at the end of the array
arr[4] = 4;

// Then add an element 5 at the end of the array
arr[5] = 5;

// And so on
// ...

# An array of size 10 already has 4 elements
arr = [0] * 10
for i in range(4):
    arr[i] = i

# Now we want to append an element 4 to the end of the array
arr[4] = 4

# Then append an element 5 to the end of the array
arr[5] = 5

# And so on
# ...

// The array of size 10 already has 4 elements
var arr [10]int
for i := 0; i < 4; i++ {
    arr[i] = i
}

// Now we want to append an element 4 at the end of the array
arr[4] = 4

// Then append an element 5 at the end of the array
arr[5] = 5

// And so on
// ...

// An array of size 10 already contains 4 elements
var arr = new Array(10);
for (var i = 0; i < 4; i++) {
    arr[i] = i;
}

// Now want to add an element 4 to the end of the array
arr[4] = 4;

// Then add an element 5 to the end of the array
arr[5] = 5;

// And so on
// ...

Since we are just assigning a value to the index, appending an element to the end of an array takes $O(1)$ time.

Now, suppose I have an array arr of size 10, with elements in the first 4 indexes. I want to insert a new element at the 3rd position (arr[2]). What should I do?

This requires "moving data." We need to make space for the new element by shifting existing elements, then insert the new element. Here’s the logic:

// An array of size 10 already has 4 elements
int[] arr = new int[10];
for (int i = 0; i < 4; i++) {
    arr[i] = i;
}

// Insert element 666 at the index 2
// Need to move the elements from the index 2 and onwards one step back
// Note that we should traverse the array backwards to avoid
// overwriting existing elements, refer to the visual panel below if unclear
for (int i = 4; i > 2; i--) {
    arr[i] = arr[i - 1];
}

// Now the 3rd position is open, and we can insert the new element
arr[2] = 666;

// An array of size 10 already has 4 elements
int arr[10];
for (int i = 0; i < 4; i++) {
    arr[i] = i;
}

// Insert element 666 at the index 2
// Need to move the elements from the index 2 and onwards one step back
// Note that we should traverse the existing elements in the array backwards
// to avoid overwriting, refer to the visualization panel below if unclear
for (int i = 4; i > 2; i--) {
    arr[i] = arr[i - 1];
}

// Now the 3rd position is vacant, we can insert the new element
arr[2] = 666;

# An array of size 10 has already been filled with 4 elements
arr = [0] * 10
for i in range(4):
    arr[i] = i

# Insert element 666 at the index 2
# Need to move the elements from the index 2 and onwards one step back
# Note that we should traverse the array in reverse order to avoid
# overwriting, see the visualization panel below if you don't understand
for i in range(4, 2, -1):
    arr[i] = arr[i - 1]

# Now the 3rd position is empty, we can insert the new element
arr[2] = 666

import "fmt"

func main() {
    // The array of size 10 already contains 4 elements
    var arr [10]int
    for i := 0; i < 4; i++ {
        arr[i] = i
    }

    // Insert element 666 at the index 2
    // Need to move the elements from the index 2 and onwards one step back
    // Be sure to traverse the existing elements of the array backwards to
    // avoid overwriting, if you don't understand, see the visual panel below
    for i := 4; i > 2; i-- {
        arr[i] = arr[i-1]
    }

    // Now the 3rd position is empty, and the new element can be inserted
    arr[2] = 666

    // Print the array result
    fmt.Println(arr)
}

// An array of size 10 already has 4 elements
var arr = new Array(10);
for (var i = 0; i < 4; i++) {
    arr[i] = i;
}

// Insert element 666 at the index 2
// Need to move the elements from the index 2 and onwards one step back
// Note that you should iterate the array backwards to avoid
// overwriting existing elements, refer to the visual panel below if unclear
for (var i = 4; i > 2; i--) {
    arr[i] = arr[i - 1];
}

// Now the 3rd position is free, you can insert the new element
arr[2] = 666;

So, inserting an element in the middle of an array takes $O(N)$ time because data has to be moved to make space.

When a fixed-size array is created, its size must be set. For example, if I create an array int arr[10] (which is a continuous 40 bytes of memory), and I store 10 elements in it, what if I want to add one more element? Whether I want to append at the end or insert in the middle, there is no space left for new elements.

Some readers might say: Why not just add another 4 bytes at the end to store the new element?

That won’t work. Continuous memory must be allocated all at once. Once it’s set, you can’t easily add more. The memory after your array may already be used by other programs, so you can't just take it.

So, what should we do? We have to apply for a bigger piece of memory, copy all the old data to it, and then insert the new element. This is called "array expansion."

For example, we can create a new bigger array int arr[20], copy the 10 original elements to it, and then add the new element.

Here is the logic:

// the array of size 10 is already full
int[] arr = new int[10];
for (int i = 0; i < 10; i++) {
    arr[i] = i;
}

// now want to append an element 10 at the end of the array
// need to expand the array first
int[] newArr = new int[20];
// copy the original 10 elements
for (int i = 0; i < 10; i++) {
    newArr[i] = arr[i];
}

// the old array's memory space will be handled by the garbage collector
// ...

// append the new element in the new larger array
newArr[10] = 10;

// The array of size 10 is already filled
int arr[10];
for (int i = 0; i < 10; i++) {
    arr[i] = i;
}

// Now want to append an element 10 to the end of the array
// Need to expand the array first
int newArr[20];
// Copy the original 10 elements over
for (int i = 0; i < 10; i++) {
    newArr[i] = arr[i];
}

// Release the memory space of the old array
// ...

// Append the new element in the new larger array
newArr[10] = 10;

# The array of size 10 is already full
arr = [i for i in range(10)]

# Now want to append an element 10 to the end of the array
# Need to expand the array first
newArr = [0] * 20

# Copy the original 10 elements over
for i in range(10):
    newArr[i] = arr[i]

# Free the memory space of the old array
# ...

# Append the new element in the new large array
newArr[10] = 10

// The array of size 10 is already full
arr := make([]int, 10)
for i := 0; i < 10; i++ {
    arr[i] = i
}

// Now want to append an element 10 to the end of the array
// Need to expand the array first
newArr := make([]int, 20)
// Copy the original 10 elements over
for i := 0; i < 10; i++ {
    newArr[i] = arr[i]
}

// Release the memory space of the old array
// ...

// Append the new element to the new larger array
newArr[10] = 10

// The array of size 10 is already filled
var arr = new Array(10);
for (var i = 0; i < 10; i++) {
    arr[i] = i;
}

// Now we want to append an element 10 at the end of the array
// We need to expand the array first
var newArr = new Array(20);
// Copy the original 10 elements over
for (var i = 0; i < 10; i++) {
    newArr[i] = arr[i];
}

// Release the memory space of the old array
// ...

// Append the new element in the new large array
newArr[10] = 10;

So, expanding an array involves creating a new array and copying data, which takes $O(N)$ time.

Delete

The delete operation is similar to the add operation. It also needs to be discussed in different situations.

Suppose I have an array of size 10 with 5 elements. Now, I want to delete the last element. How do I do it?

This is simple. We can just mark the last element as a special value to indicate it is deleted. Here, let’s use -1 as the special value. Later, when we implement a dynamic array, we’ll use a better way to delete elements. For now, just remember that deleting the last element means random access, which takes $O(1)$ time.

Here is the basic code logic:

// An array of size 10 already contains 5 elements
int[] arr = new int[10];
for (int i = 0; i < 5; i++) {
    arr[i] = i;
}

// Delete the last element, temporarily use -1 to represent the deleted element
arr[4] = -1;

// An array of size 10 already has 5 elements
int arr[10];
for (int i = 0; i < 5; i++) {
    arr[i] = i;
}

// Remove the last element, temporarily use -1 to represent the element has been deleted
arr[4] = -1;

# An array of size 10 already contains 5 elements
arr = [0] * 10
for i in range(5):
    arr[i] = i

# Remove the last element, temporarily use -1 to represent the deleted element
arr[4] = -1

// The array of size 10 already contains 5 elements
var arr [10]int
for i := 0; i < 5; i++ {
    arr[i] = i
}

// Remove the last element, temporarily using -1 to represent the deleted element
arr[4] = -1

// An array of size 10 already contains 5 elements
var arr = new Array(10);
for (var i = 0; i < 5; i++) {
    arr[i] = i;
}

// Remove the last element, temporarily use -1 to represent the deleted element
arr[4] = -1;

Suppose I have an array of size 10 with 5 elements, and I want to delete the second element (arr[1]). What should I do?

Here, too, we need to "move data." Move all elements after the deleted one forward by one to keep everything in order.

Here is the logic:

// An array of size 10 already contains 5 elements
int[] arr = new int[10];
for (int i = 0; i < 5; i++) {
    arr[i] = i;
}

// delete arr[1]
// need to move all elements after arr[1] one position forward
// note that you should traverse the array forward to avoid
// overwriting, refer to the visualization panel below if you don't understand
for (int i = 1; i < 4; i++) {
    arr[i] = arr[i + 1];
}

// set the last element to -1 to indicate deletion
arr[4] = -1;

// An array of size 10 already contains 5 elements
int arr[10];
for (int i = 0; i < 5; i++) {
    arr[i] = i;
}

// Delete arr[1]
// Elements after arr[1] need to be shifted forward by one position
// Make sure to traverse the existing elements of the array in order to avoid
// overwriting. If unclear, please refer to the visualization panel below.
for (int i = 1; i < 4; i++) {
    arr[i] = arr[i + 1];
}

// Set the last element to -1 to indicate deletion
arr[4] = -1;

# An array of size 10 has already been filled with 5 elements
arr = [0] * 10
for i in range(5):
    arr[i] = i

# Delete arr[1]
# Need to move all elements after arr[1] one position forward
# Note that we should traverse the existing elements in the array forward to
# avoid overwriting, see the visualization panel below if you don't understand
for i in range(1, 4):
    arr[i] = arr[i + 1]

# Set the last element to -1 to indicate deletion
arr[4] = -1

// an array of size 10 already contains 5 elements
var arr [10]int
for i := 0; i < 5; i++ {
    arr[i] = i
}

// delete arr[1]
// need to move all elements after arr[1] one position forward
// be sure to traverse the array of existing elements forward to avoid
// overwriting, if you don't understand, please see the visualization panel below
for i := 1; i < 4; i++ {
    arr[i] = arr[i + 1]
}

// set the last element to -1 to indicate deletion
arr[4] = -1

// An array of size 10 has 5 elements already
var arr = new Array(10);
for (var i = 0; i < 5; i++) {
    arr[i] = i;
}

// delete arr[1]
// need to move the elements after arr[1] one position forward
// note that we should traverse the existing elements of the array from
// left to right to avoid overwriting. If unclear, see the visual panel below
for (var i = 1; i < 4; i++) {
    arr[i] = arr[i + 1];
}

// set the last element to -1 to indicate deletion
arr[4] = -1;

So, deleting an element in the middle of an array takes $O(N)$ time because of the data movement.

Summary

To sum up, the time complexity for the main operations of static arrays is:

• Add:
  • Add an element at the end: $O(1)$
  • Insert an element in the middle (not at the end): $O(N)$
• Delete:
  • Remove the last element: $O(1)$
  • Remove an element from the middle (not the end): $O(N)$
• Access: Get the value at a given index, time complexity is $O(1)$
• Update: Modify the value at a given index, time complexity is $O(1)$

Some readers might ask: didn't we just discuss the array resizing operation? When an array expands, it needs to create a new space and copy data, which takes $O(N)$ time. Why isn't this included in the "add" operation's complexity?

That's a good question. But resizing doesn't happen every time you add an element. We use "amortized time complexity" to explain this. I have explained this in detail in How to Analyze Time and Space Complexity. I won't go further into that here.

Another thing beginners should notice: we say the access and update operations are $O(1)$ complexity, but this is only true when you know the index. If you are given a value and asked to find its index in the array, you have to check the whole array. That takes $O(N)$ time.

So, it is important to understand the principles, not just memorize the concepts. If you understand the principles, you can figure out the concepts by yourself.

Dynamic Arrays

We talked about static arrays and their limitations. Now let's talk about dynamic arrays. A dynamic array is an upgrade of the static array, and it is one of the most commonly used data structures in real software development and algorithm problems.

First, do not think that dynamic arrays can solve the problem of slow insert and delete operations in the middle. That is impossible. The fast random access of an array comes from its continuous memory, which always brings the need for moving data and resizing.

The underlying storage of dynamic arrays is still a static array. Dynamic arrays automatically handle resizing for us, and also wrap the add, delete, access, and update operations for easier use.

Here are some ways to use dynamic arrays in different programming languages:

// create a dynamic array
// no need to explicitly specify array size, it will
// automatically resize based on the number of elements stored
ArrayList<Integer> arr = new ArrayList<>();

for (int i = 0; i < 10; i++) {
    // append elements at the end, time complexity O(1)
    arr.add(i);
}

// insert elements in the middle, time complexity O(N)
// insert element 666 at index 2
arr.add(2, 666);

// insert elements at the beginning, time complexity O(N)
arr.add(0, -1);

// remove the last element, time complexity O(1)
arr.remove(arr.size() - 1);

// remove elements in the middle, time complexity O(N)
// remove element at index 2
arr.remove(2);

// query element by index, time complexity O(1)
int a = arr.get(0);

// modify element by index, time complexity O(1)
arr.set(0, 100);

// find index by element value, time complexity O(N)
int index = arr.indexOf(666);

// create a dynamic array
// no need to specify the size explicitly, it will
// automatically resize based on the number of stored elements
vector<int> arr;

for (int i = 0; i < 10; i++) {
    // append elements at the end, time complexity O(1)
    arr.push_back(i);
}

// insert elements in the middle, time complexity O(N)
// insert element 666 at index 2
arr.insert(arr.begin() + 2, 666);

// insert elements at the beginning, time complexity O(N)
arr.insert(arr.begin(), -1);

// remove elements from the end, time complexity O(1)
arr.pop_back();

// remove elements from the middle, time complexity O(N)
// remove the element at index 2
arr.erase(arr.begin() + 2);

// query elements by index, time complexity O(1)
int a = arr[0];

// modify elements by index, time complexity O(1)
arr[0] = 100;

// find index by element value, time complexity O(N)
int index = find(arr.begin(), arr.end(), 666) - arr.begin();

# create a dynamic array
# no need to explicitly specify the array size, it will
# automatically expand and shrink based on the actual number of stored elements
arr = []

for i in range(10):
    # append elements to the end, time complexity O(1)
    arr.append(i)

# insert elements in the middle, time complexity O(N)
# insert element 666 at index 2
arr.insert(2, 666)

# insert elements at the beginning, time complexity O(N)
arr.insert(0, -1)

# delete the last element, time complexity O(1)
arr.pop()

# delete elements in the middle, time complexity O(N)
# delete the element at index 2
arr.pop(2)

# query elements by index, time complexity O(1)
a = arr[0]

# modify elements by index, time complexity O(1)
arr[0] = 100

# find index by element value, time complexity O(N)
index = arr.index(666)

import (
	"fmt"
)

func main() {
	// create a dynamic array
	// no need to explicitly specify array size, it will auto
// expand/contract based on the actual number of elements
	arr := make([]int, 0)

	for i := 0; i < 10; i++ {
		// append elements to the end, time complexity O(1)
		arr = append(arr, i)
	}

	// insert elements in the middle, time complexity O(N)
	// insert element 666 at index 2
	arr = append(arr[:2], append([]int{666}, arr[2:]...)...)

	// insert elements at the beginning, time complexity O(N)
	arr = append([]int{-1}, arr...)

	// delete the last element, time complexity O(1)
	arr = arr[:len(arr)-1]

	// delete elements in the middle, time complexity O(N)
	// delete the element at index 2
	arr = append(arr[:2], arr[3:]...)

	// query element by index, time complexity O(1)
	a := arr[0]

	// modify element by index, time complexity O(1)
	arr[0] = 100

	// find index by element value, time complexity O(N)
	index := -1
	for i, v := range arr {
		if v == 666 {
			index = i
			break
		}
	}
}

// create a dynamic array
// No need to explicitly specify the array size, it will
// automatically resize based on the number of elements stored
var arr = [];

for (var i = 0; i < 10; i++) {
    // Append elements to the end, time complexity O(1)
    arr.push(i);
}

// Insert elements in the middle, time complexity O(N)
// Insert element 666 at index 2
arr.splice(2, 0, 666);

// Insert elements at the beginning, time complexity O(N)
arr.unshift(-1);

// Remove the last element, time complexity O(1)
arr.pop();

// Remove elements in the middle, time complexity O(N)
// Remove the element at index 2
arr.splice(2, 1);

// Query elements by index, time complexity O(1)
var a = arr[0];

// Modify elements by index, time complexity O(1)
arr[0] = 100;

// Find index by element value, time complexity O(N)
var index = arr.indexOf(666);

In the following chapters, I will teach you step by step how to implement a dynamic array, so you can understand its internal workings better.