Singly & Doubly Linked Lists - Stacks and Quoes

Sorting Algorithms Animations

These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates. Show that there is no best sorting algorithm. Show the advantages and disadvantages of each algorithm. Show that worse-case asymptotic behavior is not always the deciding factor in choosing an algorithm.

https://www.toptal.com/developers/sorting-algorithms

In the end, you can understand the following image

// Singly linked list:
class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}


class SinglyLinkedList{
    constructor() {
        this.head = null
        this.tail = null
        this.length = 0
    }

    push(val) {
        const newNode = new Node(val)
        // { head: null, tail: null, length: 0 }
        if(!this.head) {
            this.head = newNode
            this.tail = this.head
            /*
            {
                head: Node { val: 'hello', next: null },
                tail: Node { val: 'hello', next: null },
                length: 1
            }
            */
        } else {
            this.tail.next = newNode
            this.tail = newNode
            /*
            {
                head: Node {
                    val: 'hello',
                    next: Node {
                        val: 'goodby',
                        next: null
                    }
                },
                tail: Node { val: 'goodby', next: null },
                length: 2
            }
            */
        }
        // (hello) -> (goodmay)
        this.length++
        return this
    }

    pop(){
        if(!this.head) return undefined

        let current = this.head
        let newTail = current
        while(current.next) {
            newTail = current
            current = current.next
        }
        this.tail = newTail
        this.tail.next = null
        this.length--

        if(this.length === 0) {
            this.head = null
            this.tail = null
        }

        return current
    }

    shift(){
        if(!this.head) return undefined

        let current = this.head
        this.head = current.next
        this.length--

        if(this.length === 0) {
            this.tail = null
        }

        return current
    }

    unshift(val){
        const newNode = new Node(val)
        if(!this.head) {
            this.head = newNode
            this.tail = this.head
        } else {
            newNode.next = this.head
            this.head = newNode
        }

        this.length++

        return this
    }

    get(index) {
        if(index < 0 || index >= this.length) return null

        let counter = 0
        let current = this.head
        while(counter !== index) {
            current = current.next
            counter++
        }

        return current
    }

    set(index, value) {
        const foundNode = this.get(index)
        if(foundNode) {
            foundNode.val = value
            return true
        }
    }

    insertInto(index, value) {
        if(index < 0 || index > this.length) return false
        if(index === this.length) {
            this.push(value)
            return true
        }
        if(index === 0) {
            this.unshift(val)
            return true
        }

        const newNode = new Node(value)
        const foundNodeHead = this.get(index - 1)
        const temp = foundNodeHead.next
        foundNodeHead.next = newNode
        newNode.next = temp

        this.length++
        return true
    }

    remove(index) {
        if(index < 0 || index >= this.length) return false
        if(index === this.length - 1) {
            this.pop()
            return true
        }
        if(index === 0) {
            this.unshift(val)
            return true
        }

        const previousNode = this.get(index - 1)
        const removed = previousNode.next
        previousNode.next = removed.next

        this.length--
        return true
    }

    reverse() {
        let node = this.head
        this.head = this.tail
        this.tail = node

        let next
        let prev = null
        for(let i = 0; i < this.length; i++) {
            next = node.next
            node.next = prev
            prev = node
            node = next
        }

        return this
    }

}

const list = new SinglyLinkedList()
list.push('hello')
list.push('jo')
list.push('goodby')
list.reverse()
console.log(list)

// I recommend to use Snippets from chrome
class Node {
    constructor(val) {
        this.val = val
        this.next = null
        this.prev = null
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null
        this.tail = null
        this.length = 0
    }

    push(val) {
        const newNode = new Node(val)
        // { head: null, tail: null, length: 0 }
        if (!this.length) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        }
        this.length++
        return this
    }

    pop() {
        if (!this.head) return undefined
        const poppedNode = this.tail
        if (this.length === 1) {
            this.head = null
            this.tail = null
        } else {
            this.tail = poppedNode.prev
            this.tail.next = null
            poppedNode.prev = null
        }

        this.length--
        return poppedNode
    }


    shift() {
        if (!this.head) return undefined

        let current = this.head

        if (this.length === 1) {
            this.head = null
            this.tail = null
        } else {
            this.head = current.next
            this.head.prev = null
            current.next = null
        }

        this.length--
        return current
    }

    unshift(val) {
        const newNode = new Node(val)
        if (!this.head) {
            this.head = newNode
            this.tail = this.head
        } else {
            this.head.prev = newNode
            newNode.next = this.head
            this.head = newNode
        }

        this.length++

        return this
    }


    get(index) {
        if (index < 0 || index >= this.length) return null
        let count, current

        if (index <= this.length / 2) {
            count = 0
            current = this.head
            while (count !== index) {
                current = current.next
                count++
            }
        } else {
            count = this.length - 1
            current = this.tail
            while (count !== index) {
                current = current.prev
                count--
            }
        }
        return current
    }

    set(index, val) {
        let current = this.get(index)
        if (current !== null) {
            current.val = val
            return true
        }
        return false
    }

    insert(index, val) {
        if (index < 0 || index > this.length) return false
        if (index === 0) return this.unshift(val)

        let newNode = new Node(val)
        let beforeNode = this.get(index - 1)
        let afterNode = beforeNode.next
        beforeNode.next = newNode
        newNode.prev = beforeNode
        newNode.next = afterNode
        afterNode.prev = newNode

        this.length++
        return true
    }

    remove(index) {
        if (index < 0 || index > this.length) return false
        if (index === 0) return this.shift(val)
        if (index + 1 === this.length) return this.pop()

        let removeNode = this.get(index)
        removeNode.prev.next = removeNode.next
        removeNode.next.prev = removeNode.prev

        removeNode.next = null
        removeNode.prev = null

        this.length--
        return removeNode
    }
}

const list = new DoublyLinkedList()
list.push('hello')
list.push('world')
list.insert(1, 'joao')
list.remove(2)
console.log(list)