Cấu trúc dữ liệu và giải thuật là một trong những kiến thức nền tảng mà mỗi lập trình viên từ khi bắt đầu mới bước chân vào nghề cho tới người nhiều năm kinh nghiệm nên nắm bắt thành thạo để có thể vận dụng được vào bài toán cụ thể cần giải quyết. Với sự phát triển khá mạnh mẽ của javascript trong thời gian gần đây việc ra đời hàng loạt framework, thư viện từ fontend tới backend, đã biến javascript thành một trong những ngôn ngữ được sử dụng nhiều nhất, tuy nhiên đa số lập trình viên tập trung vào học ngôn ngữ để phát triển ứng dụng mà ít quan tâm tới cấu trúc dữ liệu và giải thuật, trong series này mình sẽ giới thiệu, cài đặt một số cấu trúc dữ liệu thông dụng bằng ngôn ngữ javascript, triển khai các ứng dụng thực tiễn từ các cấu trúc này.
- Nội dung bài viết:
- Giới thiệu về Big-O Notation (kí hiệu O)
- Giới thiệu và phân loại về Linked lists
- Cách triển khai Linked lists trong ngôn ngữ javascript
Big-O notation:
Trước khi tìm hiểu làm thế nào để cài đặt các thuật toán, bạn nên hiểu làm thế nào để phân tích độ hiệu quả của chúng. Phần này sẽ tập trung vào khái niệm Big-O notation (kí hiệu O lớn) cho việc phân tích độ phức tạp về thời gian và không gian của thuật toán, cuối phần này bạn sẽ hiểu làm thế nào để phân tích cài đặt của một thuật toán với cả hai khiá cạnh thời gian (thời gian thực hiện) và không gian (việc sử dụng bộ nhớ).
Cơ bản về Big-O:
Ký hiệu big-O đo trường hợp xấu nhất độ phức tạp của thuật toán. Trong big-O, n đại diện cho số inputs (đầu vào). Câu hỏi được đặt ra với big-O đó là: “Điều gì sẽ xảy ra khi n tiến tới vô cùng”.
Khi bạn triển khai một thuật toán, big-O là quan trọng bởi vì nó nói cho bạn độ hiểu quả của thuật toán là như thế nào. Hình 1 chỉ ra một vài big-O cơ bản:
Các phần sau sẽ minh họa những độ phức tạp về thời gian phổ biến này với một vài ví dụ.
Các ví dụ.
O(1) không thay đổi với khía cạnh đầu vào không gian. Do đó, O(1) được nói tới là thời gian hằng số. Một ví dụ của thuật toán có độ phức tạp O(1) là việc lấy item trong một mảng bằng chỉ số. O(n) là thời gian tuyến tính (linear time) và áp dụng tới những thuật toán mà phải làm n thao tác trong trường hợp xấu nhất.
Một ví dụ của thuật toán có độ phức tạp O(n) là in số từ 0 tới n – 1:function exampleLinear(n) {
for (var i = 0 ; i < n; i++ ) {
console.log(i);
}
}
Tương tự, O(n2) là bình phương thời gian, O(n3 ) là lập phương thời gian. Ví dụ:
function exampleQuadratic(n) {
for (var i = 0 ; i < n; i++ ) {
console.log(i);
for (var j = i; j < n; j++ ) {
console.log(j);
}
}
}
function exampleCubic(n) {
for (var i = 0 ; i < n; i++ ) {
console.log(i);
for (var j = i; j < n; j++ ) {
console.log(j);
for (var k = j;j < n; j++ ) {
console.log(k);
}
}
}
}
Cuối cùng, một ví dụ thuật toán về độ phức tạp logarit là in các phần tử mũ 2 giữa 2 và n. Ví dụ, exampleLogarithmic(10) cho kết quả như sau: 
Hiệu quả của độ phức tạp thời gian logarit xuất hiện với số lượng đầu vào lớn như hàng triệu items. Cho dù n là một triệu, exampleLogarithmic sẽ in chỉ 19 items bởi vì log2(1,000,000) = 19.9315686 . Code triển khai:function exampleLogarithmic(n) {
for (var i = 2 ; i <= n; i= i*2 ) {
console.log(i);
}
}
Đại diện độ phức tạp của một thuật toán là f(n). n đại diện cho số lượng đầu vào, f(n)time đại diện cho thời gian cần thực hiện, f(n)space đại diện cho không gian (bộ nhớ) cần cho thuật toán. Mục đích của việc phân tích một thuật toán để hiểu độ hiệu quả của thuật toán bằng tính toán f(n). Tuy nhiên tính f(n) có thể là thử thách. Big-O cung cấp một vài quy tắc cơ bản giúp developers tính toán f(n).
– Quy tắc hệ số: nếu f(n) là O(g(n)) khi đó kf(n) là O(g(n)) cho bất kỳ hằng số k > 0. Quy tắc đầu tiên là quy tắc hệ số mà ở đó loại bỏ hệ số không liên quan tới kích thước đầu vào, n. Điều này bởi vì khi n tiến tới vô cùng, hệ số khác trở nên không đáng kể.
– Quy tắc tổng: nếu f(n) là O(h(n)) và g(n) là O(p(n)) khi đó f(n) + g(n) là O(h(n) + p(n)).
– Quy tắc nhân: nếu f(n) là O(h(n)) và g(n) là O(p(n)) khi đó f(n)g(n) là O(h(n)p(n))
– Quy tắc bắc cầu: nếu f(n) là O(n) và g(n) là O(h(n)) khi đó f(n) là O(h(n))
– Quy tắc đa thức: nếu f(n) là một đa thức bậc k, khi đó f(n) là O(n^k)
– Quy tắc mũ loga: log(nk) là O(log(n)) cho bất kì hằng số k > 0. Với quy tắc này, hắng số trong hàm log cũng bị loại bỏ trong big-O.
Quy tắc hằng số:
Đầu tiên xem lại quy tắc hằng số, quy tắc này là quy tắc dễ nhất để hiểu. Nó đơn giản yêu cầu bạn loại bỏ bất kỳ hằng số không liên quan tới kích thước đầu vào. Hằng số trong big-O không đáng kể với kích thước đầu vào lớn. Do đó, đây là quy tắc quan trọng nhất của Big-O.
Điều này có nghĩa là cả 5f(n) và f(n)có cùng big-O là O(f(n)). Ví dụ với độ phức tạp thời gian O(n):
function a(n){
var count =0;
for (var i=0;i < n; i++){
count += 1;
}
return count;
}
Đoạn mã này có f(n) = n, bởi vì nó cộng count n lần. Do đó hàm này là O(n) về độ phức tạp thời gian.function a(n){
var count =0;
for (var i=0;i<5*n;i++){
count += 1;
}
return count;
}
đoạn mã này có f(n) = 5n, bởi vì nó chạy từ 0 tới 5n, tuy nhiên cả hai ví dụ này đều có big-O là O(n). Đơn giản bởi vì nếu n tiến tới vô cùng hoặc một số đủ lớn, hệ số không còn ý nghĩa. Nó sẽ thực hiện n lần, bất kì hằng số sẽ không còn đáng kể trong big-O, khối mã sau sẽ giải thích hàm với độ phức tạp thời gian tuyến tính:function a(n){
var count =0;
for (var i=0;i <n; i++){
count += 1;
}
count += 3;
return count;
}
đoạn mã này có độ phức tạp f(n) = n + 1, do +1 từ count += 3, vẫn có độ phức tạp là O(n). Điều này bởi vì 1 không dựa vào đầu vào n. Khi n tiến tới vô cùng nó trở nên không đáng kể.
Quy tắc tổng:
Quy tắc tổng trực quan để hiểu, độ phức tạp thời gian có thể được cộng. Tưởng tượng một thuật toán chính gọi hai thuật toán khác, big-O của thuật toán chính đơn giản là tổng của hai thuật toán khác.
Nếu f(n) là O(h(n)) và g(n) là O(p(n)) khi đó f(n) + g(n) là O(h(n) + p(n)).
Nó là quan trọng để nhớ áp dụng quy tắc hệ số sau khi áp dụng quy tắc này.
Đoạn mã sau giải thích một hàm với hai vòng lặp:function a(n){
var count = 0;
for (var i = 0; i < n; i++){
count += 1;
}
for (var i = 0; i < 5 * n; i++){
count += 1;
}
return count;
}
trong ví dụ này: vòng lặp đầu có f(n) = n, và vòng lặp thứ 2 f(n) = 5n. Kết quả là 6n, tuy nhiên khi áp dụng quy tắc hệ số, kết quả cuối cùng là O(n) = n.
Quy tắc nhân:
nếu f(n) là O(h(n)) và g(n) là O(p(n)) khi đó f(n)g(n) là O(h(n)p(n)).
Đoạn mã sau giải thích một hàm với hai vòng for lồng nhau:function (n){
var count = 0;
for (var i =0; i<n;i++){
count += 1;
for (var i =0; i < 5 * n; i++){
count += 1;
}
}
return count;
}
trong ví dụ này, f(n) = 5n*n cho tổng số lần lặp n. Áp dụng quy tắc hệ số O(n) = n^2
Quy tắc đa giác:
nếu f(n) là đa giác bậc k, khi đó f(n) là O(n^k)
Đoạn mã sau chỉ có 1 vòng for với độ phức tạp bậc 2:function a(n){
var count = 0;
for (var i = 0; i< n * n; i++){
count += 1;
}
return count;
}
trong ví dụ này, f(n) = n ^2 bởi vì trả về n*n lần lặp.
Big-O là quan trọng cho việc phân tích và so sánh độ hiệu quả của thuật toán. Phân tích big-O bắt đầu bằng việc nhìn xem đoạn mã và áp dụng quy tắc tới big-O.
2.LINKED LIST
Tại sao mình chọn linked list để giới thiệu trước các cấu trúc dữ liệu khác, bởi vì cấu trúc này là cấu trúc nều tảng cho rất nhiều cấu trúc khác có ứng dụng quan trọng trong thực tiễn ví dụ: caching, trees, heaps, graps…
Linked list là một cấu trúc dữ liệu mà ở đó mỗi node trỏ tới một node khác. Không giống mảng, kích thức bị cố định, một linked list là một cấu trúc dữ liệu động mà có thể cấp phát và giải phóng bộ nhớ vào lúc chạy.
Có hai kiểu linked list: singly và doubly linked list (danh sách liên kết đơn và đôi).
Singly linked lists:
Cấu trúc dữ liệu linked list là môt loại mà ở đó mỗi node(phần tử) có tham chiếu tới node kế tiếp.
Một node trong một single linked list có các thuộc tính sau: data và next.data là giá trị cho linked list node, next là con trỏ tới thể hiện khác của SinglyLinkedListNode.function SinglyLinkedListNode(data) {
this.data = data;
this.next = null;
}
đoạn mã sau là cơ bản cho singly linked list.function SinglyLinkedList(){
this.head = null;
this.size = 0;
}
SinglyLinkedList.prototype.isEmpty = function(){
return this.size == 0;
}
bắt đầu của linked list được gọi là head, thuộc tính này mặc định là null, trước khi chèn bất kì phần tử nào vào trong linked list.
Insertion:
Đoạn mã sau chỉ ra việc là sao để chèn một node vào singly linked list. Nếu head của linked list là empty, head được set tới node mới. Ngược lại, head cũ được lưu vào temp và head mới trở trành node mới được thêm vào. Cuối cùng, trỏ next của head mới tới temp.SinglyLinkedList.prototype.insert = function(value) {
if (this.head === null) { //If first node
this.head = new SinglyLinkedListNode(value);
} else {
var temp = this.head;
this.head = new SinglyLinkedListNode(value);
this.head.next = temp;
}
this.size++;
}
var sll1 = new SinglyLinkedList();
sll1.insert(1); // linked list is now: 1 -> null
sll1.insert(12); // linked list is now: 12 -> 1 -> null
sll1.insert(20); // linked list is now: 20 -> 12 -> 1 -> null
Độ phức tạp thời gian: O(1)
Xóa Node:
việc xóa của một node trong single linked list được cài đặt bằng xóa tham chiếu của node, nếu node ở giữa linked list, trỏ next của node tới bản thân nó:
Nếu node ở cuối linked list, khi đó phần tử gần cuối thứ hai sẽ được set tham chiếu tới null,SinglyLinkedList.prototype.remove = function(value) {
var currentHead = this.head;
if (currentHead.data == value) {
// just shift the head over. Head is now this new value
this.head = currentHead.next;
this.size--;
} else {
var prev = currentHead;
while (currentHead.next) {
if (currentHead.data == value) {
// remove by skipping
prev.next = currentHead.next;
prev = currentHead;
currentHead = currentHead.next;
break; // break out of the loop
}
prev = currentHead;
currentHead = currentHead.next;
}
//if wasn't found in the middle or head, must be tail
if (currentHead.data == value) {
prev.next = null;
}
this.size--;
}
}
var sll1 = new SinglyLinkedList();
sll1.insert(1); // linked list is now: 1 -> null
sll1.insert(12); // linked list is now: 12 -> 1 -> null
sll1.insert(20); // linked list is now: 20 -> 12 -> 1 -> null
sll1.remove(12); // linked list is now: 20 -> 1 -> null
sll1.remove(20); // linked list is now: 1 -> null
độ phức tạp O(n)
Xóa tại head:
Xóa một phần tử tại head của linked list là có thể trong O(1). Khi một node được xóa khỏi head, nó không yêu cầu việc duyệt. Việc cài đặt của xóa được biểu diễn trong đoạn mã bên dưới, điều này cho phép linked list được triển khai như một stack, phần tử cuối cùng được thêm có thể được xóa với O(1):DoublyLinkedList.prototype.deleteAtHead = function() {
var toReturn = null;
if (this.head !== null) {
toReturn = this.head.data;
if (this.tail === this.head) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
}
this.size--;
return toReturn;
}
var sll1 = new SinglyLinkedList();
sll1.insert(1); // linked list is now: 1 -> null
sll1.insert(12); // linked list is now: 12 -> 1 -> null
sll1.insert(20); // linked list is now: 20 -> 12 -> 1 -> null
sll1.deleteAtHead(); // linked list is now: 12 -> 1 -> null
Tìm kiếm:
Tìm một giá trị mà ở đó tồn tại trong một singly linked list, đơn giản lặp qua tất cả con trỏ next:SinglyLinkedList.prototype.find = function(value) {
var currentHead = this.head;
while (currentHead.next) {
if (currentHead.data == value) {
return true;
}
currentHead = currentHead.next;
}
return false;
}
Độ phức tạp O(n).
Doubly linked lists:
một doubly linked list có thể được coi như singly linked list hai chiều, mỗi node trong double linked list có cả con trỏ next và con trỏ prev. Đoạn code sau cài đạt doubly linked list node:function DoublyLinkedListNode(data) {
this.data = data;
this.next = null;
this.prev = null;
}
thêm vào đó một doubly linked list có một con trỏ head cũng như con trỏ tail. Head là điểm bắt đầu của doubly linked list, và đuôi nói tới cuối của double linked list, helper function kiểm tra doubly linked list là rỗng:function DoublyLinkedList (){
this.head = null;
this.tail = null;
this.size = 0;
}
DoublyLinkedList.prototype.isEmpty = function(){
return this.size == 0;
}
mỗi node trong doubly linked list có thuộc tính next và prev. Xóa, chèn và tìm kiếm được cài đặt trong doubly linked list là giống với singly liked list, tuy nhiên cho cả chèn và xóa, next và prev phải được cập nhật. Doubly linked list với 5 node:
Chèn vào head:
chèn vào head của doubly linked list giống chèn vào singly linked list ngoại trừ nó phải cập nhật con trỏ prev nữa. Đoạn mã sau chỉ ra việc làm sao để chèn vào doubly linked list, nếu head của linked list là rỗng, head và tail được set tới node mới. Điều này bởi vì ở đó chỉ có một phần tử, phần tử đó có cả head và tail. Ngược lại, biến temp được sử dụng để lưu trữ node mới. Con trỏ next của node mới trỏ tới node hiện tại và khi đó con trot prev của head hiện tại được trỏ tới node mới, cuối cùng con trỏ head được cập nhật tới node mới.DoublyLinkedList.prototype.addAtFront = function(value) {
if (this.head === null) { //If first node
this.head = new DoublyLinkedListNode(value);
this.tail = this.head;
} else {
var temp = new DoublyLinkedListNode(value);
temp.next = this.head;
this.head.prev = temp;
this.head = temp;
}
this.size++;
}
var dll1 = new DoublyLinkedList();
dll1.insertAtHead(10); // ddl1's structure: tail: 10 head: 10
dll1.insertAtHead(12); // ddl1's structure: tail: 10 head: 12
dll1.insertAtHead(20); // ddl1's structure: tail: 10 head: 20
Chèn vào tail:
tương tự, một node mới có thể được thêm vào đuôi của doubly linked list, như được cài đặt như sau:DoublyLinkedList.prototype.insertAtTail = function(value) {
if (this.tail === null) { //If first node
this.tail = new DoublyLinkedListNode(value);
this.head = this.tail;
} else {
var temp = new DoublyLinkedListNode(value);
temp.prev = this.tail;
this.tail.next = temp;
this.tail = temp; 10 }
this.size++;
}
var dll1 = new DoublyLinkedList();
dll1.insertAtHead(10); // ddl1's structure: tail: 10 head: 10
dll1.insertAtHead(12); // ddl1's structure: tail: 10 head: 12
dll1.insertAtHead(20); // ddl1's structure: tail: 10 head: 20
dll1.insertAtTail(30); // ddl1's structure: tail: 30 head: 20
Độ phức tạp O(1)
Xóa tại head:
xóa phần tử tại node head khỏi doubly linked list có thẻ được hoàn thành với O(1). Nếu chỉ có một phần tử trong trường hợp head và tail là giống nhau, cả head và tail được set tới null, ngược lại, head được set tứi con trỏ next của head. Cuối cùng, prev của head mới được set tới null để remove tham chiếu của head cũ, điều này sẽ được triển khai trong đoạn code sau:DoublyLinkedList.prototype.deleteAtHead = function() {
var toReturn = null;
if (this.head !== null) {
toReturn = this.head.data;
if (this.tail === this.head) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
}
this.size--;
return toReturn;
}
độ phức tạp về thời gian là O(1)
Xóa tại tail:
Tương tự với xóa node khỏi head, node đuôi có thể được xóa và được trả về với O(1) về thời gian, như được chỉ trong đoạn code sau, bằng việc có khả năng xóa tại cuối nữa, douly linked list cũng có thể được suy nghĩ như cấu trúc dữ liệu hàng hai chiều. Mộ hàng đợi có thể dequeue phần tử đầu tiên được thêm vào, nhưng doubly linked list có thể được dequeue cả phần tử cuối hoặc đầu với độ phức tạp O(1) về thời gian (queue với mảng sẽ có O(n)).DoublyLinkedList.prototype.deleteAtTail = function() {
var toReturn = null;
if (this.tail !== null) {
toReturn = this.tail.data;
if (this.tail === this.head) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
}
}
this.size--;
return toReturn;
}
var dll1 = new DoublyLinkedList();
dll1.insertAtHead(10); // ddl1's structure: tail: 10 head: 10
dll1.insertAtHead(12); // ddl1's structure: tail: 10 head: 12
dll1.insertAtHead(20); // ddl1's structure: tail: 10 head: 20
dll1.insertAtTail(30); // ddl1's structure: tail: 30 head: 20
dll1.deleteAtTail();
// ddl1's structure: tail: 10 head: 20
Tìm kiếm:
Để tìm xem ở đó một giá trị tồn tại trong doubly linked list, có thể bắt đầu tại head và sử dụng con trỏ next hoặc start tại đuôi và sử dụng con trỏ prev, đoạn code sau được cài đặt giống single linked list, bắt đầu tại head và tìm kiếm item:DoublyLinkedList.prototype.findStartingHead = function(value) {
var currentHead = this.head;
while(currentHead.next){
if(currentHead.data == value){
return true;
}
currentHead = currentHead.next;
}
return false;
}
var dll1 = new DoublyLinkedList();
dll1.insertAtHead(10); // ddl1's structure: tail: 10 head: 10
dll1.insertAtHead(12); // ddl1's structure: tail: 10 head: 12
dll1.insertAtHead(20); // ddl1's structure: tail: 10 head: 20
dll1.insertAtTail(30); // ddl1's structure: tail: 30 head: 20
dll1.findStartingHead(10); // true
dll1.findStartingHead(100); // false
Độ phức tạp O(n).
Đoạn code sau duyệt doubly linked list bắt đầu với tail sử dụng con trỏ prev:DoublyLinkedList.prototype.findStartingTail = function(value) {
var currentTail = this.tail;
while (currentTail.prev){
if(currentTail.data == value){
return true;
}
currentTail = currentTail.prev;
}
return false;
}
var dll1 = new DoublyLinkedList();
dll1.insertAtHead(10); // ddl1's structure: tail: 10 head: 10
dll1.insertAtHead(12); // ddl1's structure: tail: 10 head: 12
dll1.insertAtHead(20); // ddl1's structure: tail: 10 head: 20
dll1.insertAtTail(30); // ddl1's structure: tail: 30 head: 20 dll1.findStartingTail(10); // true
dll1.findStartingTail(100); // false
Độ phức tạp O(n).
Cho dù độ phức tạp về thời gian cho tìm kiếm giống như singly linked list, chỉ doubly linked list có thể được tìm kiếm hai chiều (dùng prev hoặc next), điều đó có nghĩa là nếu cho một tham chiếu tới doubly linked list node, doubly linked list có thể thực hiện đầy đủ việc tìm kiếm, nhưng một singly linked list bị giới hạn tới chỉ con trỏ next.
Cấu trúc dữ liệu linked list làm việc bởi mỗi node có một con trỏ next tới node khác, việc chèn cho cả singly và doubly linked list có độ phức tạp về thời gian là hằng số O(1), độ phức tạp về xóa khỏi head của singly linked list và doubly linked list là O(1). Tuy nhiên, tìm kiếm chomotj item trong cả singly và doubly linked list có độ phức tạp về thời gian là O(n). Doubly linked list nên được sử dụng hơn là singly linked list khi duyệt, tìm kiếm hai chiều được yêu cầu, xa hơn, doubly linked list cho phép bạn lấy tail hoặc head của linked list với độ phức tạp O(1).
Trong các bài viết tiếp theo mình sẽ hướng dẫn các bạn về cài đặt và tính độ phức tạp của các loại cấu trúc khác đặc biệt sử dụng linked list và ứng dụng trong thực tiễn, ví dụ cài đặt đồ thị đa điểm và tìm đường đi ngắn nhấn tới một điểm bất kì…