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:

- If the singly linked list is empty, we now point head and tail to the new item.

```
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:

- If the singly linked list is empty, we error.
- If the singly linked list
*becomes*empty due to popping, we point head and tail to`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:

- If the singly linked list is empty, we now point head and tail to the new item.

```
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:

- If the singly linked list is empty, we error.
- If the singly linked list
*becomes*empty due to shifting, we point tail to`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:

- If the index is out of bounds, we error.

```
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:

- If the insertion index is out of bounds, we error.
- If the insertion is
*after*the last item, we`push()`

. - If the insertion is before the first item, we
`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:

- If the deletion index is out of bounds, we error.
- If the deletion is of the last item, we
`pop()`

. - If the deletion is of the first item, we
`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:

- If the singly linked list is empty, we error.

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:

- If the index is out of bounds, we error.

```
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

- is unidirectional, so we can only calculate an address from a key - we cannot derive a key from an address,
- is deterministic, so it always produces the same address for a given key, and
- can cause collisions, i.e. two or more key-value pairs receiving the same address.

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:

**Adjacency matrix**: A matrix where the Y axis denotes origins and the X axis denotes targets. In each cell of the matrix, we store a`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.**Adjacency list**: An object where the keys are the origins and the values are arrays containing all the targets for each origin.

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:

- Adding a vertex to the adjacency matrix is
`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. - Adding an edge to
*both*is`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. - Removing an edge from an adjacency matrix is
`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. - Removing a vertex from an adjacency matrix is
`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;
}
}
```