LinkedList

// 10 --> 5 --> 16
// let myLinkedList = {
//     head: {
//         value: 10,
//         next: {
//             value: 5,
//             next: {
//                 value: 16,
//                 next: null
//             }
//         }
//     }
// }

class LinkedList {
    constructor(value) {
        this.head = new Node(value);
        this.tail = this.head;
        this.length = 1;
    }
    
    // Append the value to the end of the list. 
    // O(1)
    append(value) {
        const newNode = new Node(value);
        
        // currently, this.tail is a pointer to this.head, so making this
        // change, will actually update the previous item for us. 
        this.tail.next = newNode;
        
        // This has to be done after the above so we don't overwrite the 
        // pointer to the previous item before we set the next value. 
        this.tail = newNode;
        
        this.length++;
        return this.printList();
    }
    
    // Add the value to the beginning of the list. 
    // O(1)
    prepend(value) {
        const newNode = new Node(value);
        
        newNode.next = this.head;
        this.head = newNode;
        
        this.length++;
        return this.printList();
    }
    
    // Insert the value at the index provided. 
    // O(n)
    insert(index, value) {
        // If index higher than length, just append.
        if (index > this.length) {
            this.append(value);
            return this;
        }
        
        // If index less than 0, just prepend
        if (index < 0) {
            this.prepend(value);
            return this;
        }
        
        const leader = this.traverseToIndex(index - 1);
        const newNode = new Node(value);
        newNode.next = leader.next;
        leader.next = newNode;
        
        this.length++;
        return this.printList();
    }
    
    
    // Remove an item at the index provided.
    // O(n)
    remove(index) {
        // Get a reference to the node before the node we want to delete
        const leader = this.traverseToIndex(index - 1);
        
        // If leader is the last item in the list, then we just do nothing.
        if (leader === null || leader.next === null) {
            console.log("Index is outside list bounds so nothing to remove.")
            return this.printList();
        }
        
        const deleteMe = leader.next;
        leader.next = deleteMe.next;
        
        this.length--;
        return this.printList();
    }
    
    // Returns the item at the index provided. 
    // If the index is outside the bounds of the list, return null. 
    // O(n)
    traverseToIndex(index) {
        // If the index is less than 0, then just return the first item
        if (index < 0) {
            return null;
        }
        
        let counter = 0;
        let currentNode = this.head;
        
        // We check if currentNode is null just in case the index is higher
        // than the length of the list. If it is, then we'll just return null
        // because currentNode would be null. 
        while (counter !== index && currentNode !== null) {
            currentNode = currentNode.next;
            counter++;
        }
        return currentNode;
    }
    
    // Reverse the nodes in the linked list by changing their
    // pointers. 
    reverse() {
        // If there is only one node, just return it
        if (!this.head.next) {
            return this.head;
        }
        
        let first = this.head;
        let second = first.next;
        while (second) {
            const temp = second.next;
            second.next = first;
            first = second;
            second = temp;
        }
        this.head.next = null;
        this.head = first;
        
        return this.printList();
    }
    
    
    // Nicely print out the array of items and the length of the list. 
    // O(n)
    printList() {
        const array = [];
        let currentNode = this.head;
        
        while (currentNode !== null) {
            array.push(currentNode.value);
            currentNode = currentNode.next;
        }
        
        console.log("My list:", array, "length:", this.length);
    }
}

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

const myLinkedList = new LinkedList(10);

myLinkedList.append(5);
myLinkedList.append(16);
myLinkedList.prepend(1);

// myLinkedList.insert(2, 41);

// // Should insert the item at the beginning of the list
// myLinkedList.insert(-1, 50);

// // Should insert the item at the end of the list
// myLinkedList.insert(400, 900);

// myLinkedList.remove(2);

// // Should do nothing
// myLinkedList.remove(2900);
// myLinkedList.remove(-2);

// myLinkedList.remove(3);

myLinkedList.reverse();