# Recap of Data Structures with Javascript Part 1

### Norbert Braun Oct 17

I decided to write an article about implementing common data structures. The focus is mainly on coding in javascript rather than on theoretical explanations.

# Linkedlists

A linked list is a linear data structure that consists of nodes. Depending on the type of a linked list, nodes have different attributes.

- Singly linked list: 2 attributes, the data and a pointer to the next node
- Doubly linked list: 3 attributes, the data, a pointer to the next node, and another pointer to the previous one.

In order to loop through the list, we only need access to the starting node (head).

### Tasks

*Task 1: Create a simple linked list*

```
//LinkedList.js
const Node = (value) => ({
value,
next: null
})
const LinkedList = (head = null) =>({
length: 0,
set head(node){
head = node
},
get head(){ return head }
})
export default LinkedList
```

Initially, the head is null and the length equals 0. Let's append nodes to the list.

*Task 2: add function*

```
//LinkedList.js
...
add(value){
if(!this.head){
this.head = Node(value)
this.length++
return this
}
let current = this.head
while(current.next){
current = current.next
}
current.next = Node(value)
this.length++
return this
},
...
```

First, we check if the head is null. If it is, we set the head to be the new node. If it's not null, we start to loop until we reach the last node in the list. After the `while`

loop, `current`

will point to the last node. Finally, we add the new node to the end of the list. I like to return `this`

because that way I can chain function calls like this: `list.add(5).add(6)`

.

If you want some additional practice, you could implement an `addTo`

function which takes a value and position parameters and puts the node to that position.

*Task 3: remove function*

```
//LinkedList.js
...
remove(value){
let current = this.head
let previous = null
//deleting the head
if(current.value === value){
this.head = current.next
this.length--
return this
}
//delete from the middle
while(current){
if(current.value === value){
previous.next = current.next
this.length--
return this
}
previous = current
current = current.next
}
return this
},
...
```

As you can see, we have 2 scenarios. If we want to delete the head itself we just have to change the head pointer and decrease the length. If we need to remove something from the middle or end of the list, we need to loop until we get the value. The trick is that in every iteration, we store the previous node as well.

`previous.next = current.next`

is the key here. If we want to remove `2`

from a list like this:

`1 -> 2 -> 3`

Once the control flow jumps into the if statement, the variable `previous`

will be `1`

, `current`

will be `2`

and `current.next`

will be `3`

. So all we need to do is to "connect" `1`

with `3`

instead of `2`

.

*Task 4: Find out if the list contains an element or not*

```
//LinkedList.js
...
contains(value){
let current = this.head
while(current){
if(current.value === value){
return true
}
current = current.next
}
return false
}
...
```

Pretty straightforward. We loop through the list, and return true if we get a value that equals to the `value`

parameter.

### Test

I wanted to use mocha & chai to test the implementation of these functions but I am not sure how long this article will be, so I rather save space instead. I created an `index.js`

file to check whether these functions work properly.

```
//index.js
import LinkedList from "./LinkedList"
const myList = LinkedList()
myList.add(1).add(2).add(3)
console.log(JSON.stringify(myList))
myList.remove(1)
myList.remove(2)
myList.remove(3)
console.log(JSON.stringify(myList))
console.log(myList.contains(1))
console.log(myList.contains(0))
```

# Trees

A tree is a recursive data structure that consists of nodes just like a linked list. However, trees are much different. In this case, the starting node is called root. Every tree has at least one root node and every root has zero or more child nodes.

There are several types of trees out there, in this article I'll focus on binary trees.

### Binary Tree

The binary tree is a special type of tree in which every node has zero, 1, or 2 children(left, right).

### Binary Search Tree - BST

Okay, so another "sub-class". A binary search tree is a binary tree, but its nodes are ordered in the following way:

- Every left node must be < than the current node.
- Every right node must be > than the current node.

### Tasks

*Task 1: Create a simple Binary tree*

```
//BinarySearchTree.js
export const Node = (value) => ({
value,
right: null,
left: null
})
export const SimpleBinTree = (root = null) => ({
get root() {return root},
set root(node){ root = node},
})
//That's it. Our dummy binary tree is ready to use.
//index.js
import {SimpleBinTree, Node} from "./BinarySearchTree"
const root = Node(5)
root.left = Node(3)
root.right = Node(10)
const tree = SimpleBinTree(root)
```

So, `tree`

looks like this:

*Task 2: Travel through the tree and visit every node*

```
//BinarySearchTree.js
//add these functions
//to the SimpleBinTree object under the
//getter and setter
inOrder (node) {
if(node){
this.inOrder(node.left)
console.log(node)
this.inOrder(node.right)
}
},
preOrder (node) {
if(node){
console.log(node)
this.preOrder(node.left)
this.preOrder(node.right)
}
},
postOrder (node) {
if(node){
this.postOrder(node.left)
this.postOrder(node.right)
console.log(node)
}
}
```

There are 3 different ways to traverse a tree recursively. The `inOrder`

approach first visits the left side of the tree, then the root and finally the right side. `preOrder`

and `postOrder`

should be straightforward, they are pretty much the same but they visit nodes in a different order.

```
//you can call these functions like this
//index.js
tree.inOrder(tree.root) // output should be 3,5,10 (left, root, right)
```

*Task 3: Create a Binary Search Tree*

Okay, let's create a more specific tree than the previous one. Let's call it `BST`

. Since `SimpleBinTree`

already has several functions that I do not want to implement again I'll make sure that my `BST`

will "inherit" every function from `SimpleBinTree`

.

```
//BinarySearchTree.js
export const BST = (root = null) => Object.assign(SimpleBinTree(root),{
//binary search tree specific functions
})
```

First, we need the `add`

functionality to populate the tree.

```
//BinarySearchTree.js
...
add(val){
if(!this.root){
this.root = Node(val)
}else{
searchTreeToAdd(val, this.root)
}
},
...
//this function is not part of the object.
const searchTreeToAdd = (val, node) => {
if(val <= node.value){
//add to the left side
node.left ? searchTreeToAdd(val, node.left) : node.left = Node(val)
}else{
//add to the right side
node.right ? searchTreeToAdd(val, node.right) : node.right = Node(val)
}
}
```

First, we check if the root exists. If its `null`

, our new node will be the root.

If there is already a root, then we need to check the value of the new node. If it's less than the current node, that means we need to put it to the left side of the tree. If the value of the node is bigger than the current, we place it somewhere to the right side.

Now, let's determine the minimum of the tree.

```
//BinarySearchTree.js
...
getMin(node = this.root){
while(node.left){
node = node.left
}
return node
},
...
```

It's a very easy function to implement, we iterate on the left side of the tree to find the minimum value.

Here comes the hard part. Removing a node from the tree.

```
//BinarySearchTree.js
...
remove(value){
this.root = this.removeNode(value, this.root)
},
removeNode(value, node){
if(node.value === value){
if(!node.right && !node.left){
//node got 0 child
return null
}else if(!node.left){
//node doesn't have a left child so link the right to its parent
return node.right
}else if(!node.right){
//node doesn't have a right child so link the left to its parent
return node.left
}else{
//node has 2 children
//get the minimum value on the right side
const minNode = this.getMin(node.right)
node.value = minNode.value
node.right = this.removeNode(node.value, node.right)
return node
}
}else if(value < node.value){
//value is smaller, we search on the left side recursively
node.left = this.removeNode(value, node.left)
return node
}else if(value > node.value){
//value is bigger, we search on the right side recursively
node.right = this.removeNode(value, node.right)
return node
}
}
...
```

First, we look for the value that we want to delete. If we got the value (`node.value === value`

), then we need to check the number of children on that node. If it has 0 children, we just remove it. If it has a left or right child, we connect it to its parent. If the node has 2 children, we need to search for the smallest element on the right side, so we can replace the current node with that.

### Test

Create an index.js file and import your Binary Search Tree.

```
//index.js
import {BST} from "./BinarySearchTree"
const myBST = BST()
myBST.add(10)
myBST.add(9)
myBST.add(16)
console.log(myBST.remove(10))
console.log(myBST.root)
console.log(myBST.getMin())
```

# Hashtables

A hashtable is a very powerful key-value data structure. People mostly use it because of its highly efficient lookups. Let me show you a picture for better understanding.

You provide a key, which goes through a hash function that returns an index for that key. After that, you can look up the value in constant time in the array since you know its index.

However, you might have collisions. It means that your hash function returns the same index for different keys. In that case, you have to loop through the array and find the value associated with that key. (This is less efficient takes O(N) where N is the number of collisions for that particular index).

### Tasks

*Task 1: Create a simple hashtable*

```
//HashTable.js
const HashTable = () => ({
storage: [],
storageLen: 4,
})
```

That's it, we have a `HashTable`

with a `storage`

property, where [key, value] pairs will be stored and a `storageLen`

. Right now it has a value of 4 but if you want to avoid collisions you need to assign a bigger number to it.

*Task 2: Create the hash function that returns the index for a key*

```
//HashTable.js
//this function is private. Not part of the HashTable, and I do not export it.
const hashKey = (key, len) => {
const hash = key
.split("")
.reduce( (a, b, index) => a + b.charCodeAt(), "")
return hash % len
}
```

It's a really simple hash function producing a lot of collisions if `len`

is small. The function's `len`

parameter will always be the `storageLen`

attribute of `HashTable`

. So every time we call this function, it will give us an index between 0 and 4 (`return hash % len`

). If you change the `storageLen`

attribute to be 15, then it will give us an index from 0 to 15.

*Task 3: add values to the hashtable*

```
//HashTable.js
...
//place this function inside the HashTable object
add(key, value){
//base case. index is unique, just push the key/value pair to the storage
const index = hashKey(key, this.storageLen)
if(!this.storage[index]){
this.storage[index] = [[key, value]]
return this
}
//index already exists
const isKeyExists = this.storage[index].some(x => key === x[0])
if(isKeyExists){
//key already exists, overwrite the previous value
this.storage[index] = [[key, value]]
}else{
//key doesn't exists, but index is not unique -> we have a collision here
this.storage[index].push([key, value])
}
}
...
```

I tried to comment as much as I can so I hope this function is straightforward.

*Task 4: get function (lookup)*

```
//HashTable.js
...
get(key){
const index = hashKey(key, this.storageLen)
const keyIndex = 0
const valueIndex = 1
const hasCollision = this.storage[index].length > 1
//base scenario: index is unique so we got O(1) lookup
if(!hasCollision){
return this.storage[index][keyIndex][valueIndex]
}
//if we have a collision O(n)
for(const item of this.storage[index]){
if(item[keyIndex] === key){
return item[valueIndex]
}
}
}
...
```

We can pretty easily find out if we have a collision on a particular index `const hasCollision = this.storage[index].length > 1`

. If yes, we need to iterate on that array, and return the item immediately if the keys are the same.

### Tests

To test these functions create an index.js and import our `HashTable`

.

```
import HashTable from "./HashTable"
const hm = HashTable()
hm.add("Goji", "Cica")
hm.add("Pici Bear", 6)
hm.add("Pici Bear", 1)
hm.add("Pici", 8)
console.log(hm.get("Pici Bear"))
console.log(hm)
```

# The End

Thanks for reading. In the second part, I plan to implement data structures like Queues, Graphs, Stacks, Bloom filters :O and other stuff like that.

The easiest way to run the examples is parceljs.

Create an index.html in the same directory. Include your index.js in it like this.

Then install parcel with npm globally ->

`npm i -g parcel-bundler`

After that, you can type "parcel index.html" in the console and it will be available on localhost:1234 and you can check the output in the console of the browser.

Parcel is a zero-configuration web application bundler by the way.

If you want to run it with node, you can do

`node ./index.js`

in the console, but it will fail because of the "import { blabla } from "something" syntax.You can change the export statements to the following (example):

and then import it in your index.js

`const { BinarySearchTree} = require("./BinarySearchTree")`

If you don't want to change the code, you can setup babel with node as well.

(this is babel6, for babel7 please check the official documentation)

step1:

`npm -i babel-cli babel-preset-env`

step2: create a

`.babelrc`

file that looks like this:step3: run your index.js with the following command:

`./node_modules/.bin/babel-node index.js`

Cool, I use parcel, thanks Braun really.

Really cool! Thanks for sharing.

I think there's a bug in the setter of the HashTable:

Could you tell me how to run? Node version?

Hey chenge, please check my comment above. It should help you out.