Recap of Data Structures with Javascript Part 1

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.

Comments

[Norbert Braun]

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.

<!DOCTYPE html>
<html>
<head>
</head>
<body>
    <script src="./index.js"></script>
</body>
</html>

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

module.exports = {
 BinarySearchTree: BinarySearchTree,
 Node: Node
}

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:

{
    "presets": ["env"]
}

step3: run your index.js with the following command:
./node_modules/.bin/babel-node index.js

[chenge]

Cool, I use parcel, thanks Braun really.

[Nicolas Mesa]

Really cool! Thanks for sharing.

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

if(isKeyExists){
    //key already exists, overwrite the previous value

    // here, you're overriding the whole array. If there were any collisions, all of them would be deleted.
    this.storage[index] = [[key, value]] 
}else{
    ...
}

[chenge]

Could you tell me how to run? Node version?

[Norbert Braun]

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