Data Structures: Arrays
In this post, we will be learning the theory behind Arrays as well as how to implement them in JavaScript.
Arrays are simple and intuitive types of data structures. They represent a list of elements of any type grouped together in a central location of memory. The elements are ordered so that they can be accessed with a numerical index. This characteristic helps us to efficiently read and insert data into an array.
Arrays in JS are dynamic , meaning that they automatically adjust their size (increase or decrease) when adding or removing an element. This property guarantees a better performance by executing costly operations only when necessary. Some operations that can be performed on arrays include inserting an item, removing an item, updating an item, finding an item, sorting, reversing or looping over an array, and copying part or an entire array.
Time complexities of operations on array
Constant Time Complexity O(1): Because elements are sequentially ordered in array, it allows for fast lookups (accessing and updating an element using index) and fast adding and removing elements at the end of the array.
Linear Time Complexity O(n): removing, inserting, or searching a random element in an array is done in linear-time. Removing a given element (if not at the end of the array) requires shifting all elements coming after the removed item over by one to fill the gap; inserting a new element requires reindexing all element coming after the inserted element; and finding a value in an unsorted list requires iterating over the entire array in the worst case scenario.
Logarithmic Time Complexity O(log n): searching an element in a sorted array can be done using binary search. Binary search algorithm works by initially checking the value present in the center of the list. If the value of the element it is looking for is lower than the one found, it repeats the process on the left half of the set. If it’s bigger, it checks the right half. This process is repeated until the element is found.
Log-Linear Time Complexity O(n log n): sorting an array falls into this category.
Below are the common methods to perform the above operations on an array in JavaScript :
Here is a summary of the time complexity of Arrays’ operations:
Final Note
Arrays are great for fast retrieval of data in an ordered list with fast indexing. Adding and removing the last item is also fast. However, if you need to search items in an unsorted list, or frequently remove and insert elements in a list, an array might not be the most efficient data structure to use.
I hope you find this a helpful summary. Let’s take sometimes to digest it…
Until next time,
Happy learning / coding!!
Originally published at https://vanessuniq.github.io on January 31, 2021.
