Deciding which data structure to use during software development can be challenging. This blog seeks to help you make a decision when it comes to the built-in data structures in JavaScript, objects and arrays. Their performance will be analysed by taking a close look at how common interactions like data access, insertion, removal and search are done with each of them.
Table Of Contents
Prerequisites
- Basic knowledge of JavaScript
- Theoretical Knowledge of Big O Notation (6 mins read)
Objectives
- Understand how objects and arrays work through the lens of Big O Notation.
- Explain why adding elements to the beginning of an array is an expensive operation with respects to space and time.
- Compare and contrast the runtime for arrays and objects, as well as their built-in methods.
Objects
Objects in JavaScript are unordered data structures of key-value pairs. This means that there's no beginning or end of an object. When data is added to an object, the data is placed anywhere within it.
const person = {
name: 'Kwame',
age: 30,
height: 182,
hobbies: ['reading', 'drawing', 'running']
}
Objects are most valuable when order is not needed but quick data access, insertion and removal are of priority.
Data Access, Insertion and Removal
Through the lens of Big O Notation, data access which involves retrieving or modifying data stored in an object is done in constant time O(1). This is also true for the insertion and removal of data.
- insertion - O(1)
- removal - O(1)
- access - O(1)
Searching in Objects
Searching within objects, on the other hand, is linear time O(n). Searching here does not refer to looking for a key like age in our example object above. It refers to checking through all values of the object to see if a provided search query exists. For example, checking to see if any of person object values include the word run.
Object Methods
Accessing all the keys of an object through Object.keys() is O(n) because it's runtime is directly proportional to the number of keys the object has. The same applies to the instance of accessing an object's values with Object.values(). It's technically more work but its notation can be approximated toO(n).
Retrieving all entries of an object with Object.entries() technically involves a lot more computation than accessing keys and values because it has to compile keys and values in an array. However, its complexity can be rounded up to O(n).
Finally, in checking to see if an object has a property or not with in-built method hasOwnProperty() is constant time O(1). This is because it just checks for the existence of a property and returns a boolean.
- Object.keys - O(n)
- Object.values - O(n)
- Object.entries - O(n)
- hasOwnProperty - O(1)
Arrays
Out of the box, arrays are ordered lists. Each element in an array is assigned an index (a numerical value that corresponds to the elements storage location in memory). The ordered feature of arrays come at a cost of performance optimization so arrays should be used when the order of the data you are storing in them is important.
Data Access
Operations that involve access (retrieving or updating data) are fast, they have a big O of constant time O(1). This is as a result of the indexing feature of arrays. Accessing an element in an array with an index of 0 takes the same time to access an element with an index of 1000.
Searching in Arrays
Searching, on the other hand, is linear O(n). If I wanted to find out if orange is an element of an array of fruits, I would have to check potentially every single element. Hence the time it will take me to do that is directly proportional to the number of elements in the array.
However, you can achieve a big O of O(log(n)) when searching through an array. To achieve this, two things will have to happen. The first condition is that the array has to be sorted. Secondly, you would have to employ a binary algorithm in searching through the sorted array. This is because in using a binary search algorithm, the number of things to search through is halved in every iteration until the element you are looking for is found.
Unsorted arrays, on the other hand, can only be searched using a linear search method hence will maintain a runtime of O(n) also known as linear time.
Insertion & Removal of data
When it comes to insertion and removal, it depends on where the data is being inserted or removed. This is a result of the ordered nature of arrays.
Inserting elements at the end of an array using the push() method has a big of Constant time O(1). This is because javascript looks at the index of the last element and adds the new element with an index equivalent to the numerical value of the last index plus 1. On the other hand, inserting an element at the beginning of the array is linear time O(n). This is because all the existing elements in the array will have to be re-indexed. The same principles apply in removing elements from an array.
In summary, using push and pop is always faster than using shift and unshift.
Array Methods
The big O of a few of the standard built-in methods of arrays have already been discussed in the above paragraphs (push, pop, shift and unshift).
- push:
O(1). - pop:
O(1). - shift:
O(n). - unshift:
O(n)
Other methods are concat, slice, splice and all the higher-order functions. (forEach, map, filter, reduce, etc). Below are their respective performance analysis based on big O.
- concat:
O(n). (adding or merging two arrays) - slice:
O(n). (returns a copy of part or all of an array) - splice:
O(n). (remove or add elements anywhere in an array) - forEach / map / filter / reduce / etc.:
O(n).
For more information on how each of these work, you can refer to MDN web docs.
Conclusion
- Objects are faster at pretty much everything but have no order.
- Arrays are good when you need ordered data.
- In working with arrays, unless absolutely necessary, avoid adding and removing elements to/from the beginning of an array.
Cover image by Adi Goldstein on Unsplash
Top comments (4)
Great piece. How do things change for arrays when they are sorted vs not sorted?
Are there scenarios where one might achieve O(log(n)) when searching or traversing arrays?
Thank you, Charles. In response to your question, yes you can achieve a big O of O(log(n)) when searching through an array. However, two things will have to happen before a search operation on an array can achieve a big O of O(log(n)). The first condition is that the array has to be sorted. The second is, the method of search has to be binary instead of linear. This is because the number of things to search through is halved in every iteration until the element you are looking for is found.
Unsorted arrays on the other hand can only be searched using a linear search method hence will maintain a runtime of O(n) aka linear time.
This is a great question. I'll update my post to include this information. Although judging from the way it's coined I'm tempted to believe you already know the answer. Once again thank you so much for your question.
Great response and you are correct about me already knowing ... I just wanted to prompt you, in case you need to update your already nice article.
If you have a sorted array and implement your own search/find method (lets say you implement your own bianary search algorithm) you can definitely achieve better results for the searching scenario, about the traversing it will fall under the : forEach, map, reduce case (that are mentioned in the article) for both the ordered and unordered arrays.