LinkedList
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
// 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();
JavaScript
INFO