LinkedList

LinkedList is another list type. It use next property as a pointer to reference the the next stored data. The benefit of this data structure is when insert or delete data is a little efficient than ArrayList, because we just need to find the target element and change the next pointer. There is no need to iterate through the rest of the data and shift them to left or right, but if we need to search the certain data, we have to go through it from the head element which will cause O(n) complexity.

Implementation

class Node {
    constructor(valu, next){
        this.value = value ? value : null
        this.next = next ? next : null
    }
}

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

    push(value){
        const node = new Node(value)

        if (!this.head){
            this.head = node
        } else {
            this.tail.next = node
        }
        
        this.length++
        this.tail = node
    }

    pop(){
        if (!this.head){
            return null
        }


        if (this.head === this.tail){
            const value = this.head.value

            this.head = null
            this.tail = null

            return value
        }

        // find 
        const previousNode = this._find(this.length - 2)
        const value = previousNode.next.value
        
        previousNode.next = null
        this.tail = previousNode
        this.length--

        return value
    }

    get(index){
        const node = this._find(index)
        if (!node){
            return null
        }

        return node.value
    }

    delete(index){
        if (index === 0){
            const prevHead = this.head
            if (prevHead){
                this.head = prevHead.next
                this.length--
                return prevHead.value
            }
        }

        const targetPrev = _find(index - 1)
        
        if (!targetPrev){
            return null
        }

        const target = targetPrev.next
        
        if (!target){
            return null
        }

        targetPrev.next = target.next

        if (!targetPrev.next.next){
            this.tail = targetPrev.next
        }

        this.length--
        return target.value
    
        
    }


    _find(index){
        let current = this.head
        
        if (!index){
            return current
        }

        let count = index

        while(count){
            current = current.next
            count--
        }

        return current
    }
}