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 node = new Node(val);
        if (!this.head) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        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) {
            this.head = null;
            this.tail = null;
        }

        return current;
    }

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

        const oldHead = this.head;
        this.head = oldHead.next;
        this.length --;

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

        return oldHead;
    }

    unshift (val) {
        const node = new Node(val);
        if (!this.head) {
            this.head = node;
            this.tail = node;
        } else {
            node.next = this.head;
            this.head = node;
        }
        this.length ++;

        return this;
    }

    // O(N)
    get (idx) {
        if (idx < 0 || idx >= this.length) {
            return null;
        }

        let node = this.head;

        for (let i = 0; i < idx; i ++) {
            node = node.next;
        }

        return node;
    }

    set (idx, val) {
        const node = this.get(idx);
        if (node) {
            node.val = val;
            return true;
        }
        return false;
    }

    // O(1)
    insert (idx, val) {
        if (idx < 0 || idx > this.length) {
            return false;
        }

        if (idx === 0) {
            return !!this.unshift(val);
        }

        if (idx === this.length) {
            return !!this.push(val);
        }

        const previous = this.get(idx - 1);
        const newNode = new Node(val);
        const temp = previous.next;
        previous.next = newNode;
        newNode.next = temp;
        this.length ++;

        return true;
    }

    // O(1) at the beginning or O(N)
    remove (idx) {
        if (idx < 0 || idx >= this.length) {
            return undefined;
        }

        if (idx === 0) {
            return this.shift();
        }

        if (idx === this.length - 1) {
            return this.pop();
        }

        const previous = this.get(idx - 1);
        const removed = previous.next;
        previous.next = removed.next;
        this.length --;

        return removed;
    }

    reverse () {
        if (this.length === 0 || this.length === 1) {
            return this;
        }

        let current = this.head;
        this.head = this.tail;
        this.tail = current;
        let previous = null;
        let next = null;

        for (let i = 0; i < this.length; i++) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }

        return this;
    }
}

const list = new SinglyLinkedList();

list.push('5');
list.push('55');
list.push('555');
list.push('5555');
list.reverse();