In this article, we will be talking about the most popular data structure: arrays. You will learn what an array is, how it’s stored in your computer’s memory, the complexity of array operations. This will help you to be successful when using arrays in code interviews.

What is an array?

An array, also known as a list, is a collection of items stored in contiguous space in memory. The items of an array are organized sequentially in memory.

This image gives a visual of how arrays are stored in memory. Each array element has a value, memory address, and an index. The index is the integer (0-n) that corresponds to the element’s order position in the array. The first element has an index of 0 and the last element in the array has an of n-1 where n is the length of the array.

Array Operations

Operation	Complexity
lookup	O(1)
push	O(1)
insert	O(n)
delete	O(n)
search	O(n)

The lookup operation takes O(1) time, or constant time because, since each array item is allocated to an equal-size memory space and each memory space is indexed by contiguous integers, your computer is able to immediately jump to the correct memory address using the array index.

The insert operation takes O(n) time, or linear time, because if the item is not at the very end of the list, the other items in the last after the index of the insertion have to be shifted down in memory to make space for the new item. This requires looping through each of the items to copy and move the contents of the memory address to a different memory address.

The push operation also has a complexity of O(1) because since you are adding the item at the last array index, you don’t have to loop through each array element to shift them. This operation has different names in different languages. For example, in Python it’s called append. There is also the pop operation in which the last array item is removed from the array. This also takes constant time.

The delete operation takes O(n) time for the same reason as the insertion operation. When an item is deleted from the array, all of the items after that time must be shifted forward.

The search operation takes O(n) time because you must look at each item in the array in order to see if it is the item you are looking for. This can be quick if it’s one of the first items in the array, but if it’s at the end of the array it will take longer.

Pros & Cons of Arrays

Pros of arrays:

• Fast lookups
• Fast push/pop
• Ordered (sorting)

Cons of arrays:

• Slow inserts
• Slow deletes
• Fixed size (if using static arrays)

Static vs Dynamic Array

Static arrays are a fixed in size. You specify the number of items your array will hold ahead of time.

Dynamic arrays allow us to copy and rebuild an array at a new location with more space in memory.