Linear Data Structures in JavaScript
Data structures provide us with tools and techniques to store, organize, and manipulate data. Data structures make it easier for the programmer to access and modify data.
JavaScript has primitive and nonprimitive data structures. Primitive data structures and data types are native to the programming language. Nonprimitive data structures are those that are not defined by the programming language but rather by the programmer.
Primitive JavaScript data structures
 Arrays
 Objects
 Sets
 Maps
Nonprimitive JavaScript data structures
 Stacks
 Queues
 Linked lists
 Trees
 Graphs
First, we'll take a look at the primitive JavaScript data structures and their time complexities. Then, we'll take a look at the nonprimitive JavaScript data structures and their time complexities.
When it comes to the nonprimitive data structures, we'll only cover the linear ones in this article. Linear Data Structures are ones where data is stored sequentially. The linear ones are stacks, queues, and linked lists.
Primitive JavaScript data structures
Arrays
An array is a linear data structure that stores a collection of elements. JavaScript arrays can hold elements of different types and can dynamically resize. You can perform operations like adding or removing elements, accessing elements by index, and iterating over the array.
const colors = ['red', 'green', 'blue'];
colors.push('yellow'); // Add an element to the end
colors.pop(); // Remove the last element
console.log(colors[colors.length  1]); // Access the last element
console.log(colors[0]); // Access the first element
Big O time complexity of arrays

Accessing an element by index: O(1).
Accessing an element in an array by its index takes constant time. Arrays provide direct access to elements based on their indices via
array[index]
. 
Inserting or removing an element at the end of the array: O(1).
Adding or removing an element at the end of the array has a constant time complexity. JavaScript arrays are dynamically resizable, so adding or removing elements at the end does not require shifting or resizing the entire array.
JavaScript provides the
push
andpop
methods to insert or remove an element at the end of the array. 
Inserting or removing an element at the beginning or middle of the array: O(n).
Inserting an element at the beginning or middle of the array requires shifting elements to make room and to adjust the array indices of existing array elements. Removing an element at the beginning or middle of the array requires shifting elements to fill the gap that was made by the removal.
Both operations have a linear time complexity. This means that the operation time will increase linearly as the size of the input increases (represented by
n
).The JavaScript array methods used for these operations are
unshift
,shift
, andsplice
. 
Searching for an element: O(n).
Searching for an element in an array requires iterating over the array and comparing each element until a match is found or the end of the array is reached. In the worst case scenario, where the element is not present, or where the element is at the end of the array, it has a linear time complexity of
O(n)
.The JavaScript array methods used for this operation are
indexOf
,includes
,find
, andfindIndex
. 
Sorting an array: O(n log n).
The builtin
sort
method in JavaScript uses an optimized version of the Quicksort algorithm. To sort an array ofn
elements, it has an average time complexity ofO(n log n)
.
Objects
JavaScript objects are keyvalue pairs where the keys are strings and the values can be of any type. Objects provide a way to store and retrieve data using descriptive keys.
const gray = {
name: 'gray',
hexCode: '#808080',
webSafe: '#999999',
rgb: '128, 128, 128',
};
console.log(gray.name); // 'gray'
gray.hexCode = '#666666'; // Modify a property
Sets
A JavaScript Set is a collection of unique elements. Values of any type can be stored in a Set. A Set has methods for adding, removing, and checking the existence of elements. Sets automatically remove duplicate items.
const colorsSet = new Set();
colorsSet.add('red');
colorsSet.add('green');
colorsSet.add('green'); // Duplicates are automatically removed
console.log(colorsSet.size); // 2
colorsSet.delete('green'); // Remove an element
console.log(colorsSet.has('red')); // true
Big O time complexity of Sets

Adding an element: O(1).
Adding an element to a Set using the
add
method has a constant time complexity. 
Checking the existence of an element:: O(1).
Checking if an element exists in a Set using the
has
method results in a constant time complexity. 
Removing an element: O(1).
Removing an element from a Set using the
delete
method has a constant time complexity
Maps
A JavaScript Map is a collection of keyvalue pairs. A Map is similar to an object. The difference that Maps have from objects is that they allow any type of key, not just strings. Maps preserve the insertion order of elements, meaning that the order in which elements are added to the Map is maintained. A Map provides methods to add, remove, and retrieve elements.
Keys in a Map are unique, meaning that each key can only exist once within the Map. However, values do not have to be unique. Different keys can be associated with the same value.
const gray = new Map();
gray.set('name', 'gray');
gray.set('hexCode', '#808080');
console.log(gray.get('name')); // 'gray'
gray.delete('hexCode'); // Remove a keyvalue pair
console.log(gray.has('hexCode')); // false
Big O time complexity of Maps

Adding an element: O(1).
Adding an entry to a Map using the
set
method has a constant time complexity. 
Checking the existence of a key:: O(1).
Checking if a key exists in a Map using the
has
method has a constant time complexity. The same is true for accessing a value in a Map by its key using theget
method. 
Removing an element: O(1).
Removing an entry from a Map by its key using the
delete
method has a constant time complexity.
Nonprimitive JavaScript data structures
Stacks
A stack is a linear data structure that follows the LastInFirstOut (LIFO) principle, where the last element added is the first one to be removed.
Common operations performed on a stack are:
 push (add an element to the top).
 pop (remove the top element).
 peek (access the top element without removing it).
 isEmpty (check if the stack is empty).
Here is a basic stack implemented with a JavaScript array. By using the builtin push
and pop
array methods, we can implement the stack behavior on an array.
let stack = [];
stack.push('red');
stack.push('green');
console.log(stack.pop()); // 'green'
console.log(stack.length); // 1
We can also implement a Stack
using a JavaScript class. This class will encapsulate all the logic for the stack data structure. We can reuse this class whenever we need a stack data structure.
class Stack {
constructor() {
this.items = [];
}
getTop() {
if (this.items.length === 0) {
return null;
}
return this.items[this.items.length  1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
push(element) {
this.items.push(element);
}
pop() {
if (this.items.length === 0) {
return null;
}
return this.items.pop();
}
}
We can use the Stack
class by creating an instance of it and calling its methods.
const colorStack = new Stack();
console.log(colorStack.size()); // 0
colorStack.push('red');
colorStack.push('green');
console.log(colorStack.size()); // 2
console.log(colorStack.getTop()); // 'green'
colorStack.pop();
console.log(colorStack.size()); // 1
console.log(colorStack.getTop()); // 'red'
colorStack.pop();
console.log(colorStack.size()); // 0
console.log(colorStack.getTop()); // null
Big O time complexity of Stacks

Accessing an element: O(n).
To reach any specific element, all the elements before (or on top of) the element have to be removed from the stack. The worst case is that
n
elements need to be removed from the stack before being able to access the desired element. 
Insertion and deletion: O(1).
The
push
andpop
methods insert to and remove from the top of the stack in constant time.
Queues
A queue is a data structure that follows the FirstInFirstOut (FIFO) principle. The first element added to the queue is the first one to be removed.
Common operations performed on a queue are:
 enqueue (add an element to the end).
 dequeue (remove the first element).
 peek (access the first element without removing it).
 isEmpty (check if the queue is empty).
Here is a basic queue implemented with a JavaScript array. By using the builtin push
and shift
array methods, we can implement the queue behavior on an array.
let queue = [];
queue.push('red');
queue.push('green');
console.log(queue.shift()); // 'red'
console.log(queue.length); // 1
We can also implement a Queue
using a JavaScript class. This class will encapsulate all the logic for the queue data structure. We can reuse this class whenever we need a queue data structure.
class Queue {
constructor() {
this.items = [];
this.front = null;
this.back = null;
}
isEmpty() {
return this.items.length === 0;
}
getFront() {
if (this.isEmpty()) {
return null;
}
return this.items[0];
}
size() {
return this.items.length;
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
if (this.isEmpty()) {
return null;
}
return this.items.shift();
}
}
We can use the Queue
class by creating an instance of it and calling its methods.
const colorQueue = new Queue();
console.log(colorQueue.size()); // 0
colorQueue.enqueue('red');
colorQueue.enqueue('green');
console.log(colorQueue.size()); // 2
console.log(colorQueue.getFront()); // 'red'
console.log(colorQueue.dequeue()); // 'red'
console.log(colorQueue.size()); // 1
console.log(colorQueue.getFront()); // 'green'
console.log(colorQueue.dequeue()); // 'green'
console.log(colorQueue.size()); // 0
console.log(colorQueue.getFront()); // null
Big O time complexity of Queues

Accessing an element: O(n).
To reach any specific element, all the elements after the element have to be removed from the queue. The worst case is that
n
elements need to be removed from the queue before being able to access the desired element. 
Insertion and deletion: O(1).
Only the front element can be removed from the queue via the
dequeue
operation, using theshift
method, and taking constant time. Insertion happens at the back of the queue via theenqueue
operation, using thepush
method, and also taking constant time.
Linked list
A linked list is a linear data structure where each node in a list of nodes contains a value and a reference to the next node in the list. JavaScript doesn't have its own builtin linked list data structure. However, we can create our own.
First, let's define a class for a node. This class will represent nodes in the linked list and will contain a value and a reference to the next node.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
Next, let's define a class for the linked list data structure in the same file. Let's call this class LinkedList
. It will make use of the Node
class to represent each of the nodes in the list.
The LinkedList
class will contain two classlevel variables, head
and tail
. The head
variable will reference the head, or the starting node, of the linked list. The tail
variable will reference the last node in the linked list.
We will define the following methods in the LinkedList
class.
 append: add a node to the end of the linked list.
 prepend: add a node to the beginning of the linked list.
 insertAfter: add a node after a specific node.
 delete: delete a node containing a specific value.
 search: find a node by its value.
 print: a helper method to allow us to print the entire linked list to the console.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// add node to end of linked list
append(value) {
// create new node with the provided value
const newNode = new Node(value);
if (!this.head) {
// the new node is the only one in the list
this.head = newNode;
this.tail = newNode;
} else {
// point the current last node to the new last node
this.tail.next = newNode;
// the new node is now last in the list
this.tail = newNode;
}
}
// add node to beginning of linked list
prepend(value) {
// create new node with the provided value
const newNode = new Node(value);
if (!this.head) {
// the new node is the only one in the list
this.head = newNode;
this.tail = newNode;
} else {
// point the new head node to the existing head
newNode.next = this.head;
// the new node is now first in the list
this.head = newNode;
}
}
// add new node after the target node
insertAfter(value, target) {
// create new node with the provided value
const newNode = new Node(value);
// search for target node
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === target) {
// node after target node now comes after new node
newNode.next = currentNode.next;
// add new node after target node
currentNode.next = newNode;
// if the target node is the last node
if (currentNode === this.tail) {
// set the tail to the new node
this.tail = newNode;
}
break;
}
// iterate to the next node
currentNode = currentNode.next;
}
}
// delete a node by value
delete(value) {
if (!this.head) {
return;
}
// if the node to delete is the head
if (this.head.value === value) {
// set the new head to the next node
this.head = this.head.next;
// if there is no next node
if (this.head === null) {
// there's only a head and no tail
this.tail = null;
}
return;
}
// if the node to delete is not the head, find it
let currentNode = this.head;
while (currentNode.next) {
if (currentNode.next.value === value) {
// set target node's 'next' to skip over the deleted node
currentNode.next = currentNode.next.next;
// if target node's 'next' is not a node
if (currentNode.next === null) {
// the target node is the tail
this.tail = currentNode;
}
break;
}
// iterate to the next node
currentNode = currentNode.next;
}
}
// find a node by value
search(value) {
// start the search at the head node
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
return currentNode;
}
// iterate to the next node
currentNode = currentNode.next;
}
return null;
}
// print linked list to console
print() {
const values = [];
// start getting node values from the head
let currentNode = this.head;
while (currentNode) {
values.push(currentNode.value);
// iterate to the next node
currentNode = currentNode.next;
}
console.log(values.join(" > "));
}
}
We can use the LinkedList
class by creating an instance of it and calling its methods. Take a look at the sample execution flow and output below.
const linkedList = new LinkedList();
linkedList.append(1);
linkedList.print(); // "1"
linkedList.append(2);
linkedList.print(); // "1 > 2"
linkedList.append(3);
linkedList.print(); // "1 > 2 > 3"
linkedList.prepend(0);
linkedList.print(); // "0 > 1 > 2 > 3"
linkedList.insertAfter(4, 2);
linkedList.print(); // "0 > 1 > 2 > 4 > 3"
linkedList.delete(1);
linkedList.print(); // "0 > 2 > 4 > 3"
console.log(linkedList.search(3)); // { value: 3, next: null }
Big O time complexity of Linked lists

Accessing an element: O(n).
To reach any specific element in a linked list, all the elements occurring before the element have to be traversed. The worst case is that
n
elements need to be traversed before finding and accessing the desired element. 
Insertion and deletion:
Inserting or deleting an element at the head of the linked list can be done in O(1) constant time because we have a direct pointer to the head of the list.
Inserting an element at any other location in the linked list will have a time complexity of O(n). The desired insertion location in the linked list will need to be reached by traversing the linked list.
The worst case is that we would need to traverse the entire
n
elements of the linked list to get to the insertion location. The same time complexity goes for deleting an element from any location in the linked list that is not the head.
Conclusion
This article has been a crash course on data structures in JavaScript, providing you with data structure fundamentals and applying them to JavaScript.
We covered JavaScript's primitive data structures and their time complexities. Then, we learned how to build more complex linear data structures that are not defined by JavaScript. After building our own implementations of a stack, a queue, and a linked list, we looked at the time complexities of each.
What we haven't covered is nonlinear data structures in JavaScript, such as trees, binary trees, and graphs. That'll be a topic for a future blog post.