// 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;
}
// 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);
