Revisiting Data Structures in JavaScript
A singly linked list is made up of nodes holding a value and pointing to the next item. It differs from an array in that linked list items are not contiguously stored in memory; and it differs from a doubly linked list in that the singly linked list items point to the next item in sequence, and not also to the previous one.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor(value) {
const newNode = new Node(value);
this.head = newNode;
this.tail = this.head;
this.length = 1;
}
}
push()Adding an item at the end of a singly linked list is O(1), because we simply point the last item to the new item, which becomes the new last item, and move the tail pointer to the new item.
Edge case:
class SinglyLinkedList {
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
}
pop()Removing an item at the end of a singly linked list is O(n), because we need to iterate from the first item to the item before the last, point the item-before-last to null, and move the tail pointer to the item-before-last, which becomes the new last item.
Edge cases:
null.In a singly linked list, we cannot move backward from the tail, only forward from the head, hence the need to iterate to reach the last item.
class SinglyLinkedList {
pop() {
if (!this.head) {
throw new Error('Cannot remove from empty list');
}
let cur = this.head;
let itemBeforeLast = this.head;
while (cur.next) {
itemBeforeLast = cur;
cur = cur.next;
}
this.tail = itemBeforeLast;
this.tail.next = null;
this.length--;
if (!this.length) {
this.head = null;
this.tail = null;
}
return cur;
}
}
unshift()Adding an item at the start of a singly linked list is O(1), because we simply point the new item to the first item and move the head pointer to the new item.
Edge case:
class SinglyLinkedList {
unshift(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
}
shift()Removing an item at the start of a singly linked list is O(1), because we simply point the first item to null and move the head pointer to the formerly second item, which now becomes the first item.
Edge cases:
null. In this case, we need not manually set head to null because it will naturally end up pointing to null.class SinglyLinkedList {
shift() {
if (!this.head) {
throw new Error('Cannot remove from empty list');
}
let itemToShift = this.head;
this.head = this.head.next; // null if this.head was the only item
this.length--;
if (!this.length) {
this.tail = null;
}
itemToShift.next = null;
return itemToShift;
}
}
get()Looking up an item by index in a singly linked list is O(n), because we need to iterate from the first item until the position is reached. In other words, we loop from 0 to the index, i.e. we loop as long as i is less than the index and therefore we stop when i is equal to the index.
A singly linked list does not occupy contiguous space in memory, so indexing to a position in a singly linked list requires step-by-step traversal. By contrast, an array occupies contiguous space in memory, so indexing to a position in an array is a constant-time operation.
Edge case:
class SinglyLinkedList {
get(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
let cur = this.head;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
}
}
Looking up an item by value is also O(n) and follows similar logic as looking up by index, because we need to iterate from the first item until the comparison is true.
class SinglyLinkedList {
find(value) {
if (this.head.value === value) {
return this.head;
}
let cur = this.head;
while (cur.next) {
if (cur.value === value) {
return cur;
}
}
return undefined;
}
}
set()class SinglyLinkedList {
set(index, value) {
let itemAtIndex = this.get(index);
if (itemAtIndex) {
itemAtIndex.value = value;
return true;
}
return false;
}
}
insert()Inserting an item in the middle of singly linked list is O(n), because we need to iterate from the first item to the item before the insertion spot, point the item-before-insertion-spot's to the new item, and point the new item to the item after the insertion spot.
Edge cases:
push().unshift().class SinglyLinkedList {
insert(index, value) {
if (index < 0 || index > this.length) {
throw new Error('Index out of bounds');
}
if (index === this.length) {
return this.push(value);
}
if (index === 0) {
return this.unshift(value);
}
const newNode = new Node(value);
const itemBeforeInsertion = this.get(index - 1);
itemBeforeInsertion.next = newNode;
newNode.next = itemBeforeInsertion.next;
this.length++;
return true;
}
}
remove()Deleting an item in the middle of singly linked list is O(n), because we need to iterate from the first item to the item before the deletion spot, and point the item-before-deletion-spot to the item after the deletion spot, and point the deleted item to null.
Edge cases:
pop().unshift().class SinglyLinkedList {
remove(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
if (index === this.length - 1) {
return this.pop();
}
if (index === 0) {
return this.shift();
}
const itemBeforeDeletion = this.get(index - 1);
const itemToDelete = itemBeforeDeletion.next;
itemBeforeDeletion.next = itemToDelete.next;
itemToDelete.next = null;
this.length--;
return itemToDelete;
}
}
reverse()Reversing a singly linked list is O(n), because we need to iterate over all the items as we flip their direction, and switch the positions of the head and tail pointers.
The key is to flip the positions of the head and tail pointers, and then to create three pointers, each pointing to three consecutive items (previous, center and next), and move them in sync as we reverse the direction of each item.
class SinglyLinkedList {
reverse() {
// create center item pointer, switch head and tail
let cur = this.head;
this.head = this.tail;
this.tail = cur;
// create second and third pointers
let next = cur.next;
let prev = null;
for (let i = 0; i < this.length; i++) {
next = cur.next; // move forward next - no effect at first iteration
cur.next = prev; // flip center item
prev = cur; // move forward prev
cur = next; // move forward cur
}
return this;
}
}
next = cur.next; does nothing at the first iteration — note that it is nearly identical to the line let next = cur.next;. In the last iteration, next = cur.next; sets next to null, prev = cur; sets prev to null, and cur = next; sets cur to null.
A doubly linked list is made up of nodes holding a value and pointing to the previous and next items. It differs from an array in that linked list items are not contiguously stored in memory; and it differs from a singly linked list in that the doubly linked list items point to the previous and next items, not only to the next one.
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor(value) {
const newNode = new Node(value);
this.head = newNode;
this.tail = newNode;
this.length = 1;
}
}
push()Adding an item at the end of a doubly linked list is almost identical to doing so in a singly linked list - the only difference being that we add a connection, i.e. we point the last item to the item that now becomes the item before last.
class DoublyLinkedList {
push(value) {
const newNode = new Node(value);
if (this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail; // only difference to SLL
this.tail = newNode;
}
this.length++;
return this;
}
}
pop()Removing an item at the end of a doubly linked list is O(1), because we simply move the tail pointer to the item before last, and set the two connections to null.
Edge case:
In a doubly linked list, we can move backward from the tail, so popping in a doubly linked list is more efficient operation than in the singly linked list.
class DoublyLinkedList {
pop() {
if (this.length === 0) {
throw new Error('Cannot remove from empty list');
}
let itemToPop = this.tail;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
itemToPop.prev = null;
}
this.length--;
return itemToPop;
}
}
unshift()Adding an item at the start of a doubly linked list is almost identical to doing so in a singly linked list - the only difference being that we add a connection, i.e. we point the item that now becomes the second item to the item that now becomes the first item.
class DoublyLinkedList {
unshift(value) {
const newNode = new Node(value);
if (this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.length++;
return this;
}
}
shift()Removing an item at the start of a doubly linked list is almost identical to doing so in a singly linked list - the only difference being that we sever another connection.
class DoublyLinkedList {
shift() {
if (this.length === 0) {
throw new Error('Cannot remove from empty list');
}
let itemToShift = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
itemToShift.next = null;
}
this.length--;
return itemToShift;
}
}
get()Looking up an item by index in a doubly linked list is O(n), because we need to iterate from the first or last item until the position is reached - we halve the number of iterations by starting to iterate from the side of the list closest to the position.
Edge case:
class DoublyLinkedList {
get(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
let cur;
if (index < this.length / 2) {
let cur = this.head;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
} else {
cur = this.tail;
for (let i = this.length - 1; i > index; i--) {
cur = cur.prev;
}
}
return cur;
}
}
set()class DoublyLinkedList {
set(index, value) {
let itemAtIndex = this.get(index);
if (itemAtIndex) {
itemAtIndex.value = value;
return true;
}
return false;
}
}
insert()Removing an item at the start of a doubly linked list is almost identical to doing so in a singly linked list - the only difference being that we add another connection.
class DoublyLinkedList {
insert(index, value) {
if (index < 0 || index > this.length) {
throw new Error('Index out of bounds');
}
if (index === this.length) {
return this.push(value);
}
if (index === 0) {
return this.unshift(value);
}
const newNode = new Node(value);
const itemBeforeInsertion = this.get(index - 1);
const itemAfterInsertion = itemBeforeInsertion.next;
itemBeforeInsertion.next = newNode;
itemAfterInsertion.prev = newNode;
newNode.prev = itemBeforeInsertion;
newNode.next = itemAfterInsertion;
this.length++;
return true;
}
}
remove()Removing an item at the start of a doubly linked list is almost identical to doing so in a singly linked list - the only difference being that we sever another connection and that we do not need an extra pointer. We refer to the item before the item to remove and point the item-before-removal to the item after the item to remove; and we refer to the item after the item to remove and point the item-after-removal to the item-before removal; and we sever the connections.
class DoublyLinkedList {
remove(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
if (index === 0) {
return this.shift();
}
if (index === this.length - 1) {
return this.pop();
}
const itemToRemove = this.get(index);
itemToRemove.prev.next = itemToRemove.next;
itemToRemove.next.prev = itemToRemove.prev;
itemToRemove.next = null;
itemToRemove.prev = null;
this.length--;
return itemToRemove;
}
}
In a stack, we add and remove from the same side - it can be any side, but ideally from the end that is most efficient to push to and pop from, namely the end in a JavaScript array, since shifting and unshifting require re-indexing. Pushing and popping are terms shared by the stack and the array.
Other than with an array, a stack can be implemented with a singly linked list, using the tail as the side to push to and pop from, i.e. the null-terminated end is at the bottom of the stack. Why? Because adding and removing an item at the start of a singly linked list are both O(1) operations, but adding and removing an item at the end of a singly linked list are O(1) and O(n) operations respectively - working at the start of a singly linked list is therefore more efficient: shift() and unshift() in a singly linked list become push() and pop() in a stack. And instead of head and tail pointers from the singly linked list, we only keep a top pointer for the stack.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Stack {
constructor(value) {
const newNode = new Node(value);
this.top = newNode;
this.length = 1;
}
}
push()class Stack {
push(value) {
const newNode = new Node(value);
if (this.length === 0) {
this.top = newNode;
} else {
newNode.next = this.top;
this.top = newNode;
}
this.length++;
return this;
}
}
pop()class Stack {
pop() {
if (this.length === 0) {
throw new Error('Cannot remove from empty list');
}
let itemToPop = this.top;
this.top = this.top.next;
itemToPop.next = null;
this.length--;
return itemToPop;
}
}
In a queue we add on one side and remove from the other.
To enqueue means to add to a queue on one of its sides. To dequeue means to remove from the queue on the opposite side.
If we implement a queue as an array, we cannot get around the fact that adding to or removing from the start of the array is O(n) and doing so at the end of the array is O(1). This means that, whether we enqueue at the start and dequeue at the end, or enqueue at the end and dequeue at the start, in both cases we will have a combination of O(n) and O(1).
If we implement a queue as a singly linked list, we can choose O(1) options in both cases. Adding to the end of a singly linked list is O(1), removing from the end of a singly linked list is O(n), adding to the start of a singly linked list is O(1), and removing from the start of a singly linked list is O(1). It follows that we should enqueue from the end of a singly linked list and dequeue from the start of a singly linked list - both O(1).
In a queue, instead of head and tail pointers, we use first and last.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor(value) {
const newNode = new Node(value);
this.first = newNode;
this.last = newNode;
this.length = 1;
}
}
enqueue()To enqueue, add an item after the last item in the queue.
class Queue {
enqueue(value) {
const newNode = new Node(value);
if (this.length === 0) {
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
this.length++;
return this;
}
}
dequeue()To dequeue, remove the first item in the queue.
class Queue {
dequeue() {
if (this.length === 0) {
throw new Error('Cannot remove from empty queue');
}
let itemToDequeue;
if (this.length === 1) {
itemToDequeue = this.first;
this.last = null; // becomes the only remaining item
} else {
this.first = this.first.next;
itemToDequeue.next = null;
}
this.length--;
return itemToDequeue;
}
}
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
}
insert()class BinarySearchTree {
insert(value) {
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
return this;
}
let cur = this.root;
while (true) {
if (newNode.value === cur.value) {
throw new Error('No duplicate values allowed in BST');
// but can be worked around with count field in node
}
if (newNode.value < cur.value) {
if (cur.left === null) {
cur.left = newNode;
return this;
}
cur = cur.left;
} else {
if (cur.right === null) {
cur.right = newNode;
return this;
}
cur = cur.right;
}
}
}
}
contains()class BinarySearchTree {
contains(value) {
if (this.root === null) return false;
let cur = this.root;
while (cur) {
if (value < cur.value) {
cur = cur.left;
} else if (value > cur.value) {
cur = cur.right;
} else {
return true;
}
}
return false;
}
}
Think of a hash table as a series of memory addresses for storing key-value pairs. To place items in those addresses, we use a hash function, which receives the key-value pair, calculates an address based on the key, and returns the address for the key-value pair and an array representing the key-value pair, e.g. { apples: 4 } → ['apples', 4]
A hash function
One way of solving collisions is separate chaining with arrays, where we have an array that contains all the addresses (i.e. the address space), and an array at each address, and we push to each inner array whenever a new key-value pair receives that address: [ ['apples', 4], ['oranges', 8] ]. Another option is separate chaining with linked lists, where we have a linked list at each address and push to it whenever a new key-value pair receives that address ['apples', 4] → ['oranges', 8]
Another way is open addressing with linear probing, where we keep one key-value pair per address and, if a new key-value pair needs an address that is already taken, we iterate to the next address until we find an open one.
class HashTable {
constructor(size = 7) {
this.addresses = new Array(size);
}
#hash(key) {
let address = 0; // where key-value pair will be stored
for (let i = 0; i < key.length; i++) {
address = (address + key.charCodeAt(i) * 23) % this.addresses.length;
}
return address;
}
}
set()class HashTable {
set(key, value) {
let index = this._hash(key);
if (!this.addresses[index]) {
this.addresses[index] = [];
}
this.addresses[index].push([key, value]);
return this;
}
}
get()class HashTable {
get(key) {
let index = this._hash(key);
if (this.addresses[index]) {
for (const kvp of this.addresses[index]) {
if (kvp[0] === key) return kvp[1];
}
}
return undefined;
}
}
keys()class HashTable {
keys() {
let allKeys = [];
for (let i = 0; i < this.addresses.length; i++) {
if (this.addresses[i]) {
for (const kvp of this.addresses[index]) {
allKEys.push(kvp[0]);
}
}
}
return allKeys;
}
}
A graph contains vertices (i.e., nodes) and edges (i.e., connections). Each edge can be weighted or unweighted (i.e. having an associated value or not) and can be unidirectional or bidirectional (i.e. pointing from origin to target only, or pointing from origin to target and from target to origin). There is no limit to how many vertices a given vertex may connect to.
There are two main ways to implement a graph:
1 if the origin is connected to the target or 0 otherwise. The matrix will always contain a diagonal of zeroes from top left to bottom right, because an origin cannot be connected to itself. If the edges are weighted, instead of storing 1, we store the weights.In an adjacency matrix we store the edges of each vertex plus the non-connections, represented with 0. Therefore, the adjacency matrix is space-inefficient: O(|V|²). By contrast, an adjacency list is more space-efficient: O(|V| + |E|).
Time efficiency of adjacency matrix vs. adjacency list:
O(|V|²) since we are adding another row and another column to the matrix. Adding a vertex to the adjacency list is O(1) since we are adding another key to the object.O(1) since in the adjacency matrix we only update two values, and in the adjacency list we push a value to the two arrays at the keys for the vertices.O(1) since we only need to change two values to 0. Removing an edge from an adjacency list is O(|E|) since we need to iterate through the arrays at the keys for the vertices that the edge was connecting.O(|V|²) since we are removing a row and a column from the matrix. Removing a vertex from an adjacency list is O(|V| + |E|) since we need to iterate through the arrays at the keys for the vertices that the edge was connecting.class Graph {
constructor() {
this.adjList = {};
}
}
addVertex()class Graph {
addVertex(vertex) {
if (!this.adjList[vertex]) {
this.adjList[vertex] = [];
return true;
}
return false;
}
}
addEdge()class Graph {
addEdge(vertex1, vertex2) {
if (this.adjList[vertex1] && this.adjList[vertex2]) {
this.adjList[vertex1].push(vertex2);
this.adjList[vertex2].push(vertex1);
return true;
}
return false;
}
}
removeEdge()class Graph {
removeEdge(vertex1, vertex2) {
if (this.adjList[vertex1] && this.adjList[vertex2]) {
this.adjList[vertex1] = this.adjList[vertex1].filter(
(v) => v !== vertex2
);
this.adjList[vertex2] = this.adjList[vertex2].filter(
(v) => v !== vertex1
);
return true;
}
return false;
}
}
removeVertex()class Graph {
removeVertex(vertex) {
if (!this.adjList[vertex]) return undefined;
// remove all edges
while (this.adjList[vertex].length) {
let cur = this.adjList[vertex].pop();
this.removeEdge(vertex, cur);
}
// remove vertex
delete this.adjList[vertex];
return this;
}
}