Binary Search on Linked List in Javascript.

Abhishek Mittal — Tue, 13 Nov 2018 10:54:29 +0000

Possibilities we get with javascript, algorithms like Binary Search, Heap Sort, BFS, DFS etc been a crucial part of our academia. What if we can achieve the same with javascript.

Recently I've been studying in depth of JS and the best of javascript, I end up with is implementing all the algorithms with javascript. How helpful will it be if we can work with them in node environment.

Let's see an example related to how we can implement a simple Binary Search in a singly linked list.

All we need to do is create a file linkedList.js

mkdir link-list-bs
cd link-list-bs
touch linkList.js index.js
Inside our linkList.js add the following snippet:

class Node {
    constructor(value, next = null) {
        this.value = value;
        this.next = next;
    }
}

In above code it seems pretty similar to the struct in C or class in Java or Python, well we do the same here creating a class which creates a single instance of a Node in your linked list, every time we add a new one to it.

Now Let's add this code to see how we handle our linked list

// linkedList.js
// ...

module.exports = class LinkedList {
    /**
     *Creates an instance of LinkedList.
     */
    constructor() {
        this.head = null;
        this.tail = null;
        // to make sure of the valuethis.compare = (a, b) => a === b;
    }

    /**
     * @description add a new node to the linked list
     *
     * @param {*} value
     * @returns
     */
    append(value) {
        const newNode = new Node(value);

        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            return this;
        }

        this.tail.next = newNode;
        this.tail = newNode;
        return this;
    }

    /**
     * @description delete a node from the linked list
     *
     * @param {*} value
     * @returns
     */
    delete(value) {
        if (!this.head) {
            return null;
        }

        let deletedNode = null;

        // if the value is in the first nodewhile (this.head && this.compare(this.head.value, value)) {
            deletedNode = this.head;
            this.head = this.head.next;
        }

        let currentNode = this.head;

        // if current node is not null travel through the linked list// to find the node with the value and replace the next with the current nodeif (currentNode !== null) {while (currentNode.next) {
                if (this.compare(currentNode.next.value, value)) {
                    deletedNode = currentNode.next;
                    currentNode.next = currentNode.next.next;
                } else {
                    currentNode = currentNode.next;
                }
            }
        }

        // two nodes in the list remainsif (this.compare(this.tail.value, value)) {this.tail = currentNode;
        }

        return deletedNode;
    }
};

here now we create another class which we export so that we can create an instance for every time we create a new linked list.

In class LinkedList we have to member functions:

append(value) : append function create a new node which sets the head for this instance of class and tail points to the last value of the linked list.
delete(value): delete function deletes the node from the linked list.
Let's get back to our index.js

const LinkList = require('./linkedList');
add the above line to import LinkList into your playground. More lets set up for binary search.


const init = () => {
    const ll = new LinkList();

    // adding few elements already sorted
    try {
        ll.append(10);
        ll.append(20);
        ll.append(30);
        ll.append(40);
        ll.append(50);
        ll.append(60);
    } catch (error) {
        console.log(error);
    }
};
init();

Great!, we are all set. Now we have a linked list of these elements. Now if you wanna see what's going on you can have a peek by consoling:

console.log('My Linked List: ', JSON.stringify(ll));
Now let's write our binary Search Function inside our index.js

// index.js

const binarySearch = (head, value) => {
    let start = head;
    let last = null;

    return null;
};

well this doesn't seem right, we need to add the real method here

/**
 *
 * @description Binary Search
 * @param {*} head
 * @param {*} value
 * @returns
 */
const binarySearch = (head, value) => {
    let start = head;
    let last = null;
    let mid;
    do {
        if (start === last && last && last.value != value) return null;
        mid = middle(start, last);

        if (!mid) return null;

        if (mid.value === value) return mid;
        else {
            mid.value < value ? (start = mid.next) : (last = mid);
        }
    } while (last != null || last === start);

    return null;
};

Now our binarySearch function looks like this. But it won't work until the mid value lets add that :

/**
 *
 * @description Middle Function
 * @param {*} start
 * @param {*} last
 * @returns
 */
const middle = (start, last) => {
    if (start === null) {
        return null;
    }

    let slow = start;
    let fast = start.next;

    while (fast != last) {

        fast = fast.next;
        if (fast != last) {
            slow = slow.next;
            fast = fast.next;
        }
    }

    return slow;
};

here we are finding the middle node and that's what helps us find out the value lastly.

All Set, just a final addition to our init function:

// find the value 10 in the linked list
console.log('LL: ', binarySearch(ll.head, 10) ? 'found' : 'does not exist');

now, let's run this.

node index.js
// output 
LL:  found

So we see, javascript can be used anywhere.

Try other things with js.

Forem: Abhishek Mittal

Binary Search on Linked List in Javascript.