Linked list là 1 dạng cấu trúc dữ liệu mà mỗi phần tử trong đó sẽ liên kết với phần tử đứng đằng sau nó. Do tính chất của cấu trúc nên việc truy xuất 1 phần tử thông qua index cụ thể sẽ chậm hơn so với mảng vì Linked list phải loop thông qua các phần tử bắt đầu từ begining (head) cho đến khi tìm được phần tử đó
Implement:
B1: Khởi tạo node với 2 thuộc tính là value và next:
B2: Viết hàm push
push(value) {
const node = createNode(value);
if (this.length === 0) {
this.head = node;
this.tail = node;
this.length++;
return node;
}
this.tail.next = node;
this.tail = node;
this.length++;
}
B3: Viết hàm pop
pop() {
if (this.isEmpty()) {
return null;
}
if (this.head === this.tail) {
this.head = null;
this.tail = null;
this.length--;
return null;
}
let current = this.head;
let penultimate;
while (current) {
if (current.next === this.tail) {
penultimate = current;
break;
}
current = current.next;
}
penultimate.next = null;
this.tail = penultimate;
this.length--;
}
B4: Viết hàm get
get(index) {
if (index < 0 || index > this.length) {
return null;
}
if (index === 0) {
return this.head;
}
let current = this.head;
let i = 0;
while (i < index) {
i++;
current = current.next;
}
return current;
}
B5: Viết hàm delete
delete(index) {
if (index < 0 || index > this.length) {
return null;
}
if (index === 0) {
let deleted = this.head;
this.head = deleted.next;
this.length--;
return deleted;
}
let current = this.head;
let previous;
let i = 0;
while (i < index) {
i++;
previous = current;
current = current.next;
}
let deleted = current;
previous.next = current.next;
this.length--;
return deleted;
}
Full code
function createNode(value) {
return {
value,
next: null
};
}
function createLinkedList() {
return {
head: null,
tail: null,
length: 0,
isEmpty() {
return this.length === 0;
},
push(value) {
const node = createNode(value);
if (this.length === 0) {
this.head = node;
this.tail = node;
this.length++;
return node;
}
this.tail.next = node;
this.tail = node;
this.length++;
},
pop() {
if (this.isEmpty()) {
return null;
}
if (this.head === this.tail) {
this.head = null;
this.tail = null;
this.length--;
return null;
}
let current = this.head;
let penultimate;
while (current) {
if (current.next === this.tail) {
penultimate = current;
break;
}
current = current.next;
}
penultimate.next = null;
this.tail = penultimate;
this.length--;
},
get(index) {
if (index < 0 || index > this.length) {
return null;
}
if (index === 0) {
return this.head;
}
let current = this.head;
let i = 0;
while (i < index) {
i++;
current = current.next;
}
return current;
},
delete(index) {
if (index < 0 || index > this.length) {
return null;
}
if (index === 0) {
let deleted = this.head;
this.head = deleted.next;
this.length--;
return deleted;
}
let current = this.head;
let previous;
let i = 0;
while (i < index) { i++; previous = current; current = current.next; } let deleted = current; previous.next = current.next; this.length--; return deleted; }, print() { let arr = []; let current = this.head; while (current) { arr.push(current.value); current = current.next; } return arr.join("=>");
}
};
}
Link tham khảo: https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
