Follow by Email

Data Structures & Algorithms in JavaScript(Sorted linked list)

Sorted linked list

Hello Everyone, this is part 8 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover Sorted linked list.

What is Sorted linked list?

A sorted linked list is a list that keeps its elements sorted. To keep all elements sorted, instead of applying a sorting algorithm. — Learning JavaScript Data Structures and Algorithms Third Edition

List Of Operations Available

All methods will the same as the  .we will only overwrite the insert method.

Implementation of Sorted linked list in Javascript

The SortedLinkedList class does not need and additional properties, so we can simply extend the LinkedList Class, only overwrite the required methods.

class SortedLinkedList extends LinkedList {
constructor(func, CompareFun = defaultCompare){
super(func);
this.CompareFun = CompareFun;
}
}

Insert

While Insert an element in SortedLinkedList, There are two scenarios:-

  1. SortedLinkedList is Empty

2. SortedLinkedList is Not Empty

  • Get the Next Sorted Position/Index using the getNextSortIndex method.
  • Called Parent  and set the index to Next Sorted Position.
insert(element, index =0){
if (this.isEmpty()) {
return super.insert(element,index)
}else{
const pos = getNextSortIndex(element);
return super.insert(element,pos);
}
}

GetNextSortIndex

This method returns the sorted index by iteratively comparing the element with the linked list’s nodes or until all nodes have been iterated.

getNextSortIndex(element){
let current = this.head;
let i = 0;
for (; i < current.next != null ; i++) {
if (this.CompareFun(element,current.element) == Compare.LESS_THAN) {
return i;
}
current = current.next;
}
return i;
}

you get the full source 

Conclusion

The complexity of the Sorted Linked List will be the same as Single Linked List.

So, stay tuned for the next blog, in which I will cover another DS SET

Data Structures & Algorithms in JavaScript(Sorted linked list) Data Structures & Algorithms in JavaScript(Sorted linked list) Reviewed by RS Coder on May 31, 2020 Rating: 5

No comments:

Disqus Shortname

banner image
Powered by Blogger.