Cấu trúc dữ liệu Danh sách liên kết

Kiến thức cần biết

Khái niệm Cấu trúc dữ liệu
Kiểu dữ liệu trừu tượng
Khái niệm Giải thuật
Biết Lập trình bằng ngôn ngữ C:
- Biết lập trình với mảng
- Biết lập trình hàm
- Biết đến khái niệm con trỏ
- Sử dụng được kiểu dữ liệu do người dùng định nghĩa (struct)

Giới thiệu Danh sách liên kết

Trong khoa học máy tính, danh sách liên kết là một tập hợp tuyến tính của các phần tử dữ liệu mà thứ tự của chúng không phụ thuộc vào vị trí vật lý của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử trỏ đến phần tiếp theo. Nó là một cấu trúc dữ liệu bao gồm một tập hợp các nút cùng đại diện cho một chuỗi tuần tự. Ở dạng cơ bản nhất của nó, mỗi nút chứa: dữ liệu và một tham chiếu (nói cách khác, một liên kết) đến nút tiếp theo trong chuỗi tuần tự. Cấu trúc này cho phép chèn hoặc loại bỏ hiệu quả các phần tử khỏi bất kỳ vị trí nào trong chuỗi trong quá trình lặp lại. Các biến thể phức tạp hơn thêm các liên kết bổ sung, cho phép chèn hoặc loại bỏ các nút hiệu quả hơn ở các vị trí tùy ý. Một hạn chế của danh sách được liên kết là thời gian truy cập là tuyến tính (và khó chuyển tiếp). Truy cập nhanh hơn, chẳng hạn như truy cập ngẫu nhiên, là không khả thi. Mảng có vị trí bộ nhớ cache tốt hơn so với danh sách được liên kết.

Danh sách được liên kết là một trong những cấu trúc dữ liệu đơn giản và phổ biến nhất. Chúng có thể được sử dụng để triển khai một số kiểu dữ liệu trừu tượng phổ biến khác, bao gồm danh sách, ngăn xếp, hàng đợi, mảng kết hợp và biểu thức S, mặc dù không có gì lạ khi triển khai trực tiếp các cấu trúc dữ liệu đó mà không sử dụng danh sách liên kết làm cơ sở.

Các thuật ngữ trong Danh sách liên kết

Các thuật ngữ quan trọng để hiểu khái niệm về Danh sách được liên kết:

Liên kết (Link) - Mỗi liên kết của danh sách được liên kết có thể lưu trữ một dữ liệu được gọi là một phần tử
Tiếp theo (Next) - Mỗi liên kết của danh sách được liên kết chứa một liên kết đến liên kết tiếp theo được gọi là Next
LinkedList - Danh sách được liên kết chứa liên kết kết nối đến liên kết đầu tiên được gọi là First

Biểu diễn Danh sách liên kết

Danh sách được liên kết có thể được hình dung như một chuỗi các nút, nơi mọi nút đều trỏ đến nút tiếp theo

Theo hình minh họa ở trên, sau đây là những điểm quan trọng cần được xem xét.

Danh sách được Liên kết chứa một phần tử liên kết được gọi là đầu tiên
Mỗi liên kết mang (các) trường dữ liệu và một trường liên kết được gọi là tiếp theo
Mỗi liên kết được liên kết với liên kết tiếp theo của nó bằng cách sử dụng liên kết tiếp theo của nó
Liên kết cuối cùng mang một liên kết là null để đánh dấu phần cuối của danh sách

Các loại danh sách liên kết

Danh sách liên kết đơn:
Danh sách được liên kết đơn chứa các nút có trường dữ liệu (data) cũng như trường 'tiếp theo' (next), trỏ đến nút tiếp theo trong chuỗi các nút. Các thao tác có thể được thực hiện trên các danh sách được liên kết đơn bao gồm chèn, xóa và duyệt.
Danh sách liên kết kép
Trong 'danh sách được liên kết kép', mỗi nút chứa, ngoài liên kết nút tiếp theo, một trường liên kết thứ hai trỏ đến nút 'trước đó' trong chuỗi các nút. Hai liên kết có thể được gọi là 'chuyển tiếp' (forward) và 'quay lại' (backwards), hoặc' tiếp theo' (next) và 'trước' (prev/previous).
Danh sách liên kết móc vòng
Trong nút cuối cùng của danh sách, trường liên kết thường chứa tham chiếu rỗng, một giá trị đặc biệt được sử dụng để chỉ ra việc thiếu các nút tiếp theo. Một quy ước ít phổ biến hơn là làm cho nó trỏ đến nút đầu tiên của danh sách; trong trường hợp đó, danh sách được cho là 'vòng tròn' hoặc 'liên kết móc vòng'; nếu không, nó được cho là 'mở' hoặc 'tuyến tính'. Nó là một danh sách mà con trỏ cuối cùng trỏ đến nút đầu tiên.

Các thao tác cơ bản trên Danh sách liên kết

Chèn - Thêm một phần tử vào đầu danh sách
Duyệt - Duyệt qua lần lượt các phần tử trong danh sách. VD Thao tác hiển thị danh sách đầy đủ các phần tử
Xóa - Xóa một phần tử ở đầu danh sách
Xóa - Xóa một phần tử bằng cách sử dụng khóa đã cho
Tìm kiếm - Tìm kiếm một phần tử bằng cách sử dụng khóa đã cho

Triển khai danh sách liên kết

Việc triển khai danh sách liên kết phụ thuộc vào dữ liệu (data) mà bạn muốn tạo danh sách liên kết, ở đây chúng ta sẽ lấy ví dụ dữ liệu chúng ta muốn xây dựng danh sách liên kết là số nguyên cho đơn giản nhất. Để triển khai được danh sách liên kết như vậy trong C chúng ta cần định nghĩa cấu trúc như sau:

Danh sách liên kết đơn hoặc danh sách liên kết móc vòng:

typedef struct Node{
    int data;
    struct Node * next;
} intLinkedList;

Danh sách liên kết kép:

typedef struct Node { 
	int data; 
	struct node *prev;
	struct node *next;
} intDoublyLinkedList;

Ngoài việc định nghĩa cấu trúc dữ liệu danh sách như trên, chúng ta còn triển khai một loạt các thao tác (thuật toán) khác trên danh sách liên kết. Để triển khai các thao tác này chúng ta cũng lấy danh sách liên kết đơn cho dễ hình dung nhất.

Thêm phần tử và đầu của danh sách liên kết

Để thêm một phần tử (Node/Element) mới vào trong danh sách liên kết đơn, chúng ta thực hiện các bước như sau:

Cấp phát bộ nhớ cho phần tử mới
Gán thuộc tính data của phần tử mới cho giá trị cần thêm vào
Gán thuộc tính next của phần tử mới cho phần tử đầu tiên
Gán phần tử đầu tiên của danh sách cho phần tử mới

Mã nguồn ngôn ngữ C cho thao tác thêm phần tử vào đầu danh sách:

int insertToHead(int value, intLinkedList** head){
    intLinkedList *newElement;
    //allocate memory for new element
    newElement = (intLinkedList*)malloc(sizeof(intLinkedList));
    //assign new element value for value parameter
    newElement->data = value;
    //step 1: assign next new element for head element
    newElement->next = *head;
    //step 2: assign head element for new element
    *head = newElement;
    return 1;
}

Trong đó:

value: là giá trị cần thêm mới vào danh sách
head: là địa chỉ phần tử đầu tiên của danh sách. Do thao tác chèn thêm 1 phần tử của danh sách này cần thay đổi đầu của danh sách nên tham số truyền vào phải truyền tham trị (dùng con trỏ hay địa chỉ của head).

Thao tác duyệt Danh sách liên kết

Thao tác duyệt trên Danh sách liên kết cơ bản là cách thức làm sao đi có thể lấy lần lượt ra được tất cả các phần tử có trong danh sách để làm một công việc cụ thể nào đó như: hiển thị, tìm kiếm, lấy phần tử theo vị trí,...

Thao tác Hiển thị tất cả các phẩn tử trong danh sách là thao tác duyệt cơ bản nhất đối với danh sách liên kết. Mã nguồn triển khai thao tác này như sau:

void display(intLinkedList *head){
    intLinkedList *iterator;
    iterator = head;
    while(iterator != NULL){
        printf("|data:%d|->", iterator->data);
        iterator = iterator->next;
    }
    printf("NULL\n");
}

Thao tác tìm kiếm một giá trị có trong danh sách hay không (trả về vị trí / thứ tự xuất hiện trong danh sách)

int indexOf(int value, intLinkedList *head){
    intLinkedList *iterator;
    int i;
    for(iterator=head, i=0; iterator!=NULL; iterator=iterator->next, i++){
        if(iterator->data==value){
            return i;
        }
    }
    //not found value
    return -1;
}

Thao tác xóa phần tử đầu tiên trong Danh sách liên kết

Để thực hiện thao tác xóa phẩn tử đầu tiên trong danh sách liên kết ta thực hiện các bước như sau:

Kiểm tra danh sách có rỗng hay không? Nếu danh sách rỗng thì không thể thực hiện thao tác xóa và trả về cho hàm giá trị sai (false)
Lưu lại vị trí cần xóa
Chuyển phần tử đầu của danh sách sang phần tử kế tiếp của chính nó
Giải phóng bộ nhớ cho phần tử đã lưu lại trước đó
Trả về cho hàm giá trị đúng (true)

Mã nguồn thao tác xóa phần tử đầu tiên của danh sách:

bool deleteFromHead(intLinkedList **head){
    //check Linked List don't have any element -> can't delete
    if(*head == NULL){
        return false;
    }
    //get delete element (first element)
    intLinkedList *del;
    del = *head;
    //step 1: move head element to next head element
    *head = del->next;
    //step 2: free memory deleted element
    free(del);
    return true;
}

Lưu ý: Khi áp dụng mã nguồn cho hàm trên thì trên chúng ta cần phải sử dụng thêm thư viên stdbool.h bằng lệnh #include <stdbool.h> ở ngay sau lệnh #include <stdio.h> phần đầu tệp mã nguồn.

Các thao tác khác Danh sách liên kết

Còn rất nhiều các thao tác khác có thể thực hiện được trên danh sách liên kết, tuy nhiên trong phạm vi bài viết ngắn này chúng ta sẽ không thảo luận hết được các thao tác như vậy. Do vậy bạn có thể tham khảo các thao tác này trong mã nguồn với liên kết sau: https://github.com/sinhdev/dsa/blob/master/LinkedList/LinkedListDemo.c

Nếu áp dụng các kiểu dữ liệu khác vào trong danh sách liên kết ví dụ như là tạo một danh sách liên kết các quyển sách ta có thể tạo cấu trúc như sau:

typedef struct{
    char isbn[15];
    char title[51];
    char author[51];
    float price;
}Book;
typedef struct Node{
    Books *data;
    struct Node* next;
}BookLinkedList;

Mã nguồn tham khảo ví dụ trên tại liên kết sau: https://github.com/sinhdev/dsa/blob/master/LinkedList/BookManagement.c

Kết luận

Trong bài viết này chỉ đề cập cách đơn giản nhất để hiểu được các thao tác trên Cấu trúc dữ liệu Danh sách liên kết đơn, do vậy các ví dụ cũng như phần mã nguồn có trích dẫn ở trên vẫn chỉ chưa thể đầy đủ các vai trò và các thao tác cần thiết trên danh sách liên kết.

Một câu hỏi nữa đặt ra là ở 2 ví dụ có liên kết ở trên (LinkedListDemo.c và BookManagement.c) là với mỗi kiểu dữ liệu khác nhau chúng ta phải viết lại hết tất cả các thao tác trên Danh sách liên kết? Thực ra điều này hoàn toàn có thể ra dưới dạng thư viện chung cho các kiểu dữ liệu. Tuy nhiên, trong bài viết ngắn này chỉ tập trung vào các thao tác cơ bản nhất cho dễ hiểu đặc biệt là những người không tìm hiểu quá sâu về ngôn ngữ lập trình C. Tôi có viết tạm một thư viện về Danh sách liên kết và các thao tác trên đó cho tất cả dữ liêu các bạn có thể tham khảo ở các liên kết sau:

Thư viện Danh sách liên kết: https://github.com/sinhdev/dsa/blob/master/snxlib/llsnxlib.c
Ví dụ sử dụng Thư viện Danh sách liên kết với số nguyên: https://github.com/sinhdev/dsa/blob/master/LinkedList/llsnxlib-int.c
Ví dụ sử dụng Thư viện Danh sách liên kết với Sách (struct Book): https://github.com/sinhdev/dsa/blob/master/LinkedList/llsnxlib-book.c
Lưu ý khi sử dụng thư viện Danh sách liên kết
- Cần sử dụng các thư viện sau:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
```
- Để chạy được 2 ví dụ sử dụng thư viện, cần đưa các tệp theo cấu trúc thư mục như sau:
```
LinkedList
     |_ llsnxlib-book.c
     |_ llsnxlib-int.c
snxlib
     |_ llsnxlib.c
```

Trong thực tế các ngôn ngữ lập trình phát triển sau ngôn ngữ lập trình C đều có cài đặt sẵn các Cấu trúc dữ liệu chuẩn như ArrayList / List, LinkedList, Tree,... trong các bộ thư viện thường được đặt tên là Collection chứ không phải tiến hành tự cài đặt như trong ngôn ngữ lập trình C.