JavaScrip Data structure - Sorte

This article will use the knowledge about single linked list, you can click https://www.jianshu.com/p/4aa82e247b52 to learn first.

A sorted linked list is a list that keeps its elements sorted. To keep all elements sorted, instead of applying a sorting algorithm, we will insert the element at its correct position so as to keep the list always sorted.

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
}

function defaultCompare (a, b) {
    if (a === b) return 0;
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

//Sorted linked list
class SortedLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
        //will inherited LinkedList's count,head,and equalsFn
        super(equalsFn);
        this.compareFn = compareFn;
    }
    insert (element) {
        if (this.isEmpty()) {
            return super.insert(element, 0)
        }
        const pos = this.getIndexNextSortedElement(element);
        return super.insert(element, pos);
    }

    getIndexNextSortedElement (element) {
        let current = this.head;
        let i = 0
        for (; i < this.count && current; i++) {
            const comp = this.compareFn(element, current.element);
            if (comp === Compare.LESS_THAN) {
                return i;
            }
            current = current.next;
        }
        return i;
    }
}

const sortedLinkedList = new SortedLinkedList();
sortedLinkedList.insert(10);
sortedLinkedList.insert(6);
sortedLinkedList.insert(8);

sorted-Linked list.png

You can click https://jsfiddle.net/wendy81/oL6p7hdy/25/ to check the preceding code.