## DEV Community is a community of 557,365 amazing developers

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

# Data Structures & Algorithms in JavaScript(Sorted linked list)

Swarup Das Updated on ・2 min read

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

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