Danh Sách Liên Kết Đôi trong C - Khái Niệm, Cài Đặt, và Ứng Dụng Thực Tế

Trong ngôn ngữ lập trình C, Danh Sách Liên Kết Đôi (Doubly Linked List) là một cấu trúc dữ liệu linh hoạt, cho phép lưu trữ các phần tử trong một chuỗi liên kết hai chiều. Khác với danh sách liên kết đơn, danh sách liên kết đôi có thể duyệt theo cả hai hướng: từ đầu đến cuối và ngược lại. Với tính năng này, danh sách liên kết đôi trở thành lựa chọn lý tưởng trong các bài toán đòi hỏi thao tác nhanh chóng và dễ dàng với các phần tử ở giữa danh sách.

1. Khái Niệm về Danh Sách Liên Kết Đôi

Danh sách liên kết đôi là một chuỗi các node liên kết với nhau. Mỗi node chứa ba phần:

• Dữ liệu (data): Giá trị của node.
• Con trỏ đến node trước (prev): Trỏ đến node trước trong danh sách.
• Con trỏ đến node sau (next): Trỏ đến node tiếp theo trong danh sách.

Nếu prev của node đầu tiên và next của node cuối cùng đều bằng NULL, đó là một danh sách liên kết đôi tuyến tính. Nếu prev của node đầu tiên trỏ đến node cuối và next của node cuối trỏ đến node đầu, đó là danh sách liên kết đôi vòng.

2. Cấu Trúc của Danh Sách Liên Kết Đôi trong C

Để cài đặt danh sách liên kết đôi trong C, trước tiên chúng ta cần định nghĩa cấu trúc Node. Mỗi Node bao gồm ba phần:

• data: Lưu trữ dữ liệu của node.
• prev: Trỏ đến node trước.
• next: Trỏ đến node tiếp theo.

Cấu trúc Node trong danh sách liên kết đôi:

#include <stdio.h>
#include <stdlib.h>

// Cấu trúc của một node trong danh sách liên kết đôi
struct Node {
    int data;               // Giá trị của node
    struct Node* prev;      // Con trỏ đến node trước
    struct Node* next;      // Con trỏ đến node sau
};

3. Các Thao Tác Cơ Bản với Danh Sách Liên Kết Đôi

1. Khởi Tạo Danh Sách Liên Kết Đôi

Ban đầu, chúng ta khởi tạo một danh sách trống với con trỏ head được gán bằng NULL:

struct Node* head = NULL; // Khởi tạo danh sách trống

2. Thêm Một Node vào Đầu Danh Sách

Để thêm một node vào đầu danh sách, chúng ta cần tạo node mới, cập nhật next của node mới trỏ đến node hiện tại của head, sau đó cập nhật head để trỏ đến node mới.

void insertAtBeginning(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = head;

    if (head != NULL) {
        head->prev = newNode;
    }
    head = newNode;
}

3. Thêm Một Node vào Cuối Danh Sách

Để thêm một node vào cuối danh sách, chúng ta cần duyệt qua danh sách đến node cuối cùng, sau đó cập nhật next và prev của node mới để nối vào cuối danh sách.

void insertAtEnd(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        newNode->prev = NULL;
        head = newNode;
        return;
    }

    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = newNode;
    newNode->prev = temp;
}

4. Xóa Một Node trong Danh Sách Liên Kết Đôi

Để xóa một node có giá trị key, bạn cần điều chỉnh các con trỏ của node trước và node sau sao cho không còn tham chiếu đến node đó, sau đó giải phóng bộ nhớ của node.

void deleteNode(int key) {
    struct Node* temp = head;

    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

    if (temp == NULL) return;

    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    } else {
        head = temp->next;
    }

    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }

    free(temp);
}

5. Duyệt và In Các Phần Tử trong Danh Sách

Duyệt qua danh sách liên kết đôi có thể thực hiện theo cả hai chiều. Dưới đây là hàm duyệt và in tất cả các phần tử từ đầu đến cuối danh sách:

void printList() {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

4. Ưu và Nhược Điểm của Danh Sách Liên Kết Đôi

Ưu Điểm

• Duyệt hai chiều: Bạn có thể duyệt danh sách theo cả hai chiều, rất tiện lợi cho các bài toán cần truy cập ngược.
• Dễ dàng xóa và chèn node: Danh sách liên kết đôi cho phép xóa và chèn node ở bất kỳ vị trí nào với thao tác đơn giản hơn danh sách liên kết đơn.

Nhược Điểm

• Tiêu tốn nhiều bộ nhớ hơn: Mỗi node cần thêm một con trỏ prev, làm tăng yêu cầu bộ nhớ.
• Quản lý phức tạp hơn: Danh sách liên kết đôi đòi hỏi phải cập nhật hai con trỏ (next và prev), khiến cho việc cài đặt và bảo trì phức tạp hơn.

5. Các Ứng Dụng Thực Tế của Danh Sách Liên Kết Đôi

Danh sách liên kết đôi là một công cụ quan trọng trong nhiều ứng dụng khác nhau:

1. Trình duyệt web (Browser)

Các trình duyệt sử dụng danh sách liên kết đôi để quản lý lịch sử duyệt web. Khi người dùng chuyển tiếp hoặc quay lại, trình duyệt có thể nhanh chóng truy cập trang trước đó hoặc sau đó.

2. Quản lý bộ nhớ trong hệ điều hành

Hệ điều hành có thể sử dụng danh sách liên kết đôi để quản lý các tiến trình đang hoạt động, các tài nguyên, hoặc quản lý bộ nhớ để giảm thiểu chi phí chuyển đổi.

3. Cài đặt ngăn xếp (Stack) và hàng đợi (Queue)

Danh sách liên kết đôi cung cấp khả năng quản lý dữ liệu linh hoạt, phù hợp để cài đặt các cấu trúc dữ liệu như ngăn xếp và hàng đợi với thao tác chèn và xóa nhanh chóng.

6. So Sánh Danh Sách Liên Kết Đơn và Danh Sách Liên Kết Đôi

Dưới đây là bảng so sánh giữa danh sách liên kết đơn và danh sách liên kết đôi:

7. Kết Luận

Danh sách liên kết đôi là một cấu trúc dữ liệu quan trọng trong lập trình C, mang lại tính linh hoạt cao và hiệu quả trong việc xử lý dữ liệu. Dù có nhược điểm là tốn nhiều bộ nhớ hơn danh sách liên kết đơn, danh sách liên kết đôi vẫn là lựa chọn lý tưởng cho các bài toán yêu cầu duyệt hai chiều, chèn và xóa nhanh chóng ở bất kỳ vị trí nào.

Nếu bạn muốn nắm vững lập trình C và làm chủ quản lý dữ liệu trong các ứng dụng thực tế, thì việc hiểu và thành thạo cách cài đặt và sử dụng danh sách liên kết đôi là điều không thể bỏ qua. Hy vọng bài viết này sẽ giúp bạn hiểu rõ hơn về danh sách liên kết đôi và ứng dụng nó vào các bài toán thực tế trong lập trình.