Danh sách liên kết đơn và các biến thể — Những cách cài đặt hiệu quả và ngắn gọn

Danh sách liên kết đơn (Singly linked list) là một cấu trúc dữ liệu cơ bản và có rất nhiều ứng dụng. Trong bài viết này, chúng ta sẽ thảo luận về các cách cài đặt danh sách liên kết (trong C) sao cho hiệu quả và ngắn gọn.

Cài đặt danh sách liên kết đơn trong C

Để cài đặt danh sách liên kết đơn trong C, chúng ta không thể tránh khỏi sử dụng con trỏ (pointer) và struct. Con trỏ là một kiểu dữ liệu rất mạnh của ngôn ngữ C, cho phép thao tác bộ nhớ một cách hiệu quả. Tuy nhiên, việc làm việc với con trỏ có thể khó và khó debug các chương trình có con trỏ, đặc biệt là đối với những người mới tiếp xúc với khái niệm con trỏ.

Một con trỏ (pointer) là một biến dùng để lưu trữ địa chỉ của một biến khác. Trong trường hợp này, biến khác có thể là một biến thông thường như biến số nguyên, biến số thực, hoặc một mảng. Con trỏ cũng cần phải được lưu trữ ở một vị trí trong bộ nhớ. Điều này cho phép chúng ta sử dụng con trỏ để lưu địa chỉ của một con trỏ khác. Đây chính là điểm mạnh và kỳ diệu của con trỏ.

Một con trỏ được khai báo bằng cách chỉ định kiểu của biến mà con trỏ lưu trữ địa chỉ, dấu * và tên của con trỏ. Ví dụ:

int *a; // con trỏ tới một số nguyên
float *b; // con trỏ tới một số thực
char *c; // con trỏ tới ký tự

Struct trong C cho phép chúng ta tạo ra một kiểu dữ liệu mới bằng cách kết hợp một hoặc nhiều kiểu dữ liệu khác nhau. Trong trường hợp này, struct được sử dụng để khai báo một "mắt xích" của danh sách liên kết. Ví dụ:

typedef struct llnode{
    int x;
    struct llnode *next;
} llnode;

Trong đoạn code trên, biến x là dữ liệu của mỗi mắt xích, có kiểu là int. Con trỏ next chỉ đến mắt xích kế tiếp trong danh sách và thường có giá trị là Null khi đến mắt xích cuối cùng.

Để khởi tạo một mắt xích, chúng ta sử dụng hàm malloc để cấp phát bộ nhớ. Hàm malloc là một hàm quản lý bộ nhớ trong C. Ví dụ:

llnode * create_new_node(int datum){
    llnode * node = (llnode *)malloc(sizeof(llnode)); // cấp phát bộ nhớ cho một mắt xích mới
    node->x = datum;
    node->next = NULL;
    return node;
}

Danh sách liên kết đơn

Danh sách liên kết đơn là một cấu trúc dữ liệu tuyến tính giống như một cái xích dài, trong đó các mắt xích được liên kết với nhau. Để theo dõi danh sách, chúng ta sử dụng một con trỏ đặc biệt, gọi là con trỏ head. Con trỏ này lưu trữ địa chỉ của mắt xích đầu tiên trong danh sách. Chúng ta có thể duyệt qua danh sách bằng cách bắt đầu từ mắt xích đầu tiên và đi qua các mắt xích kế tiếp cho đến khi gặp con trỏ Null, tức là đã duyệt qua toàn bộ danh sách.

void walk_down(llnode *head){
    while(head->next != NULL){
        printf("%d, ", head->x);
        head = head->next;
    }
}

Trong đoạn code trên, chúng ta duyệt qua danh sách từ đầu đến cuối bằng cách sử dụng vòng lặp while. Mỗi lần qua một mắt xích, chúng ta hiển thị giá trị của mắt xích đó và chuyển sang mắt xích kế tiếp bằng cách thay đổi con trỏ head.

Thêm phần tử mới vào danh sách liên kết

Khi thêm phần tử mới vào danh sách liên kết, thường nên thêm vào đầu danh sách vì việc này đơn giản và hiệu quả. Đối với việc thêm vào cuối danh sách, chúng ta cần xét trường hợp danh sách rỗng (con trỏ head là Null) và phải duyệt qua toàn bộ danh sách để tìm mắt xích cuối cùng. Điều này làm cho code trở nên dài và phức tạp.

llnode * insert_to_tail(llnode *tail, int datum){
    llnode *node = create_new_node(datum); // tạo mắt xích mới
    if( tail == NULL) { // danh sách rỗng
        tail = node;
        head = tail;
    } else{
        tail->next = node;
        tail= node;
    }
    return tail;
}

Xóa một phần tử khỏi danh sách liên kết

Để xóa một mắt xích có giá trị khỏi danh sách, chúng ta cần duyệt qua danh sách và cập nhật mắt xích trước mắt xích cần xóa.

void remove( int datum){
    llnode **iterator = &(head); // lấy địa chỉ của con trỏ head
    while((*iterator)->x != datum){
        iterator = &((*iterator)->next);
    }
    *iterator = (*iterator)->next;
}

Phương pháp trên thực hiện trên địa chỉ của con trỏ, thay vì trên con trỏ. Điều này làm cho code trở nên sạch sẽ và hiệu quả.

Như vậy, danh sách liên kết đơn là một cấu trúc dữ liệu cơ bản và quan trọng trong lập trình. Ngoài ra, còn có các biến thể khác của danh sách liên kết như danh sách liên kết đôi (doubly linked list) và danh sách liên kết vòng (circularly linked list). Mỗi biến thể có những đặc điểm riêng và ứng dụng trong các trường hợp cụ thể.

Hy vọng bài viết này đã giúp bạn hiểu rõ hơn về danh sách liên kết và các biến thể của nó.

Được sự cho phép của tác giả Hùng Lê.

Tham khảo:

• Tutorial về con trỏ và ý nghĩa của con trỏ
• Cách hoạt động của hàm malloc
• Con trỏ hàm
• Cormen, T.H., Leiserson, C.E., Rivest, R., Stein, C. (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill.
• Knuth, D.E. (2000). Dancing Links. arXiv preprint cs/0011047.