I tried to implement a Linked list by myself and faced the question: "How I can get Node for O(1) complexity?"
Are there opportunities (or good practices) to improve "get" method? Do I need to add another data structure into Linked List? I read in some articles about using Hash Table into Linked List. Is it normal?
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// O(1)
addToTail(value) {
let newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
// O(n)
get(value) {
let cur = this.head;
while (cur && cur.value !== value) {
cur = cur.next;
}
return cur;
}
// O(n)
remove(value) {
let cur = this.head;
let prev = null;
while (cur && cur.value !== value) {
prev = cur;
cur = cur.next;
}
if (cur) {
// First Node
if (this.head === cur) {
this.head = cur.next;
if (this.head === null) {
this.tail = null;
}
} else {
// Not first Node
prev.next = cur.next;
if (cur.next === null) {
this.tail = prev;
}
}
return true;
}
return false;
}
print() {
let cur = this.head;
while (cur !== null) {
console.log(cur.value);
cur = cur.next;
}
}
}
const cars = ['Audio', 'BMW', 'Mazda', 'Toyota'];
const list = new LinkedList();
for (let i = 0; i < cars.length; i++) {
list.addToTail(cars[i])
}
list.remove('Audio')
list.addToTail('Kia')
list.addToTail('Lexus')
console.log(list.get('Mazda'));
