Data Structures & Algorithms in JavaScript(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 same as the single linked list .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

   • Called Parent Insert Method and set the index to zero.

2. SortedLinkedList is Not Empty

   • Get the Next Sorted Position/Index using the getNextSortIndex method.
   • Called Parent Insert Method 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 here

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