class Node {
    constructor(data, next) {
        this.data = data
        this.next = next
    }
}

class LinkedList {
    constructor() {
        this.head = null
        this.length = 0
    }
    validIndex(index) {
        if (index < 0 || index > this.length) return false
        else return true
    }
    unshift(data) {
        const node = new Node(data, this.head)
        this.head = node
        this.length++
    }
    getFirst() {
        return this.head
    }
    getLast() {
        if (this.head) {
            let node = this.head
            while (node.next) node = node.next
            return node
        }
    }
    clear() {
        this.head = null
        this.length = 0
    }
    shift() {
        if (this.head) {
            const node = this.head
            this.head = this.head.next
            this.length--
            return node
        }
    }
    pop() {
        if (this.head) {
            if (this.length === 0) return
            if (this.length === 1) return this.shift()
            const last = this.getLast()
            let node = this.head
            while (node !== last) node = node.next
            node.next = null
            this.length--
            return last
        }
    }
    push(data) {
        if (!this.head) return this.unshift(data)
        else this.getLast().next = new Node(data)
        this.length++
    }
    get(index) {
        if (this.validIndex(index)) {
            let node = this.head
            for (let i = 0; i < index; i++) {
                node = node.next
            }
            return node
        }
    }
    set(index, data) {
        if (this.validIndex(index)) {
            const node = this.get(index)
            node.data = data
            return true
        }
    }
    remove(index) {
        if (this.validIndex(index)) {
            if (index === 0) return this.shift()

            const node = this.get(index)
            const prevNode = this.get(index - 1)

            prevNode.next = node.next
            this.length--
            if (this.length === 0) this.head = null
            return node
        }
    }
    insert(index, data) {
        if (this.validIndex(index)) {
            if (index !== 0) {
                const node = this.get(index - 1)
                node.next = new Node(data, node.next)
            } else this.head = new Node(data, this.head)
            this.length++
            return true
        } else return false
    }
}