DEV Community is a community of 787,688 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Binary Search on Linked List in Javascript.

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

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

// ...

/**
*/
constructor() {
this.tail = null;
// to make sure of the valuethis.compare = (a, b) => a === b;
}

/**
*
* @param {*} value
* @returns
*/
append(value) {
const newNode = new Node(value);

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) {
return null;
}

let deletedNode = null;

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

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

add the above line to import LinkList into your playground. More lets set up for binary search.

const init = () => {

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:

Now let's write our binary Search Function inside our index.js

// index.js

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

return null;
};

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

/**
*
* @description Binary Search
* @param {*} value
* @returns
*/
const binarySearch = (head, value) => {
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.