Time Complexity Analysis of Common JavaScript Array & Object Methods

Time Complexity Analysis of Common JavaScript Array & Object Methods

The plethora of built-in methods available on JavaScript objects and arrays prototypes promises
developers less bugs and more readable code in their applications. These methods provide a variety
of operations on arrays and objects, including: addition, retrieval, removal and many others.

However, it is wise to know and understand not only what is happening “under the hood” when
such methods are implemented, but to also be aware of their time complexity. This post will help
lift the veil on the methods to show what their implementation looks like.

Objects

Objects are data types that consist of unordered key:value pairs. Keys must be strings, while
values may consist of any type (strings, numbers, booleans, objects, etc)

Object.keys( someObject )

• This method takes in an object and returns an array contain the object’s keys

• Time complexity: O(n). Under the hood, JS is iterating through the whole object, and adding each key of the object to array

Object.values( someObject )

• This method takes in an object and returns an array contain the object’s keys

• Time complexity: O(n). Like the Object.keys() method, JS is iterating through the whole object, and outputting all values from the object in an array.

Object.hasOwnProperty( key )

• This method takes in a key from the object and returns true if the key exists in the object, false if it doesn’t (additionally, returns false in the key has been inherited from another object)

• Time complexity: O(1). Under the hood, this method is doing a search operation in the carInfo object. All search operations in an object are O(1)

Arrays

Arrays in JavaScript are data structures that consist of ordered value or values. Values in JS arrays can contain any data type (numbers, strings, booleans, etc)

Array.prototype.push( someValue )

• This methods takes in a value and add the value to the end of the array, incrementing the array’s length by one.

• Time complexity: O(1). Since all this method is only adding to the end of the array, there is no iteration going on.

Array.prototype.pop()

• This method removes the last element from the array, decrementing the length by 1

• Time complexity: O(1). Similar to push, since this method operates on the last element of the array, it does not require iteration

Array.prototype.shift()

• This method removes the first element from the array

• Time complexity: O(n). Since arrays are ordered, when an element is removed from the array (with the exception of the last element in the array), the array needs to update the indexes for each element in the array, which will be dependent on the number of elements in the array

Array.prototype.unshift( valueToAdd)

• This method add an element to the beginning of the array (value becomes index position 0)

• Time complexity: O(n). Since arrays are ordered, when an element is added to the array, the array needs to update the indexes for each element in the array, which will be dependent on the number of elements in the array

Array.prototype.concat(arrayToCombine)

• This method takes in an array, and combines it with another array, returning a new array. The array passed in add to the end of the array that the method is operating on

• Time complexity: O(n). Since the result of this method returns a new array, each element from both arrays are added to the new array, which is done so iteratively.

Singly Linked List Implementation in JavaScript

A linked list is a type of data structure that is composed of nodes that hold references that point
to the next and/or previous node. Each node itself contains some value, along with a
pointer to the next node. Each time a node is added to the linked list, each node is
responsible for remembering the next element.

Though there are various types of linked lists, however, this post will cover the implementation of
a singly linked list in JavaScript. This type of linked list is unidirectional - each node has a pointer only to the next node.

The main methods for singly linked list are:

• Append: adding elements to the linked list
• Remove: removing elements from the linked list
• Search: finds, if possible, the element of the list

To start, we will create the Linked List class and Node helper class:

The Linked List class is defined with a length of 0 and head initially set to null.
When a node is created, it will be created through the Node class, and contain a value,
in addition to a next and previous property, which is initially set to null

Next, we will define each of our methods within the Linked List class.

Append method: The append method is responsible for adding elements to the linkedlist. The method takes in a value, which is the value of the node. We need to make sure that the linked list is not empty, so we’ll check to see if there exists a value for the head. If there is a value, we will enter a loop, which will run only during the condition of that the node which is being pointed to contains a value. While in the loop, we will set the head’s value to it’s pointed node’s value, in order to continue to move through the list. Once there exists no value for the head’s next value, we will set the node’s pointed node value to to the current head.

Remove method: The remove method removes a node from the linkedlist. We initially check the starting Node’s next value to see if it exists. If it  doesn’t, we set the starting node’s next value to the head. The remove method returns the node that.

Search method: The search method looks for a given value and returns that value if the node exists in the list. If the node doesn’t exist in the list, a false boolean value.