All about Arrays
One of the first data structures we learn about in computer science is an array. Simply put, an array is a collection of elements stored next to each other.
In general, the elements in an array are of the same data type. An array is both a primitive data type and a data structure commonly used to implement other data structures such as stacks and queues. To understand the time complexity of array operations, we need to remember that an array requires contiguous space in memory.
Let’s picture this.
Think of a movie theater as your computer’s memory; the seats in the movie theater as unique cells in memory; the seat numbers as the address of the cells; and the group of friends who sit together at the movie theater as elements of an array in memory.
Let’s say it’s year 2019. You and your best friend are at a movie theater to see Little Women. Since this movie theater is first-come-first-serve, you two arrive early to pick out the best adjacent seats in the middle row; C14 and C15. (aka you have reserved two cells in memory for the array)
During the trailers, two other close friends show up unexpectedly. (aka we want to insert additional elements onto the existing array) The four of you now want to sit together but there’s no empty seat on either sides of your current seats. However, there is an empty row towards the back that have four adjacent seats available. So the two of you decide to get up from your current seats to move to the back so all four of you can be seated next to each other like in an array.
Array Operations
Each element in an array has an index. The first element of an array is indexed by 0, and the index increments by 1 for each of the following elements in the array. You can perform basic operations to modify and access elements in an array using its indices. Some of the operations supported by an array are:
- Insert − Adding an element at a given index.
- Delete − Deleting an element at a given index.
- Access − Accessing an element at a given index.
- Update − Updating an element at a given index.
- Traverse − Traversing the array element by element
Strengths
Access and Update —Since you can retrieve the value of an element in an array using its index, it takes constant O(1) time to access and update an element in an array regardless of its length.
Weaknesses
Insert and Delete — Once you declare an array, you can’t change its size due to the fixed space in memory allocated to it. Adding an element to an array could mean that you have to shift each following element to make space or that you have to copy the entire array onto a new space. Therefore, inserting elements onto an array has the worst-case time complexity of O(n). Same goes for deletion.
More Resources
Watch this video by CS Dojo in 1.5x speed for one of the best explanations of arrays and memory.
Bookmark this article by Mandeep Kaur for a list of built-in JavaScript array methods.
Check out this page by Guru99 for an overview of how to declare and perform operations on an array in Python, C++ and Java.
