Here is a code of implementing a Singly Link List:
class LinkedList {
constructor(value) {
this.head = {
value: value,
next: null,
};
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = {
value: value,
next: null,
};
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) {
const newNode = {
value: value,
next: null,
};
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
printList() {
let array = [];
let currentNode = this.head;
while (currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.next;
}
return array;
}
insert(index, value) {
if (index >= this.length) return this.append(value);
if (index === 0) return this.prepend(value);
const newNode = {
value: value,
next: null,
};
const leader = this.traverseToIndex(index - 1);
const holdingPointer = leader.next;
leader.next = newNode;
newNode.next = holdingPointer;
this.length++;
return this.printList();
}
traverseToIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
remove(index) {
if (index >= this.length) return this.printList();
if (index === 0) {
// Special case for removing the head node
this.head = this.head.next;
if (this.length === 1) {
// If the list had only one node, update the tail as well
this.tail = null;
}
} else {
const leader = this.traverseToIndex(index - 1);
const unwantedNode = leader.next;
leader.next = unwantedNode.next;
if (index === this.length - 1) {
// If we're removing the tail node, update the tail
this.tail = leader;
}
}
this.length--;
return this.printList();
}
reverse() {
if (!this.head.next) {
return this.head;
}
let first = this.head;
this.tail = this.head;
let second = first.next;
while (second) {
const temp = second.next; //third
second.next = first;
first = second;
second = temp;
}
this.head.next = null;
this.head = first;
return this.printList();
}
}
// Usage example
let myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
console.log(myLinkedList.printList()); // [10, 5, 16]
console.log("----------------------");
myLinkedList.prepend(1);
console.log(myLinkedList.printList()); // [1, 10, 5, 16]
console.log("----------------------");
myLinkedList.insert(2, 99);
myLinkedList.insert(100, 567);
console.log(myLinkedList.printList()); // [1, 10, 99, 5, 16, 567]
console.log("----------------------");
// myLinkedList.remove(0);
// console.log(myLinkedList.printList()); // [10, 99, 5, 16, 567]
// myLinkedList.remove(2);
// console.log(myLinkedList.printList()); // [10, 99, 16, 567]
// myLinkedList.remove(2);
// console.log(myLinkedList.printList()); // [10, 99, 567]
// myLinkedList.remove(2);
// console.log(myLinkedList.printList()); // [10, 99]
// myLinkedList.remove(1);
// console.log(myLinkedList.printList()); // [10]
// myLinkedList.remove(0);
// console.log(myLinkedList.printList()); // []
console.log(myLinkedList.reverse());
console.log(myLinkedList);
I need someone to help me in understanding this reverse() function:
reverse() {
if (!this.head.next) {
return this.head;
}
let first = this.head;
this.tail = this.head;
let second = first.next;
while (second) {
const temp = second.next; //third
second.next = first;
first = second;
second = temp;
}
this.head.next = null;
this.head = first;
return this.printList();
}
I tried to understand it alot of times, also i tried with chatGBT haha.
if there was an eaier way but without changing the Big O of the function.
**The reverse() function big O is O(n). **
New contributor
AbdelrahmanMurad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.