Chương 4: Danh sách liên kết đơn (Linked list)

4.1. Sơ lược về lịch sử ra đời Linked list

Danh sách liên kết (Linked List) là một cấu trúc dữ liệu cổ điển trong khoa học máy tính. Nó xuất hiện từ thời kỳ đầu của máy tính và lập trình. Dù không thể xác định chính xác thời điểm đầu tiên danh sách liên kết được phát minh, nhưng có thể nói rằng nó ra đời cùng với ngành khoa học máy tính.

4.2. Nguyên Lý Hoạt Động của Linked

Danh sách liên kết (Linked List) có thể được minh họa giống như một đoàn tàu hỏa, trong đó mỗi toa tàu là một nút (node) trong danh sách, và các toa tàu được liên kết với nhau bằng dây xích (con trỏ next).

• Toa đầu (Head node): Toa đầu tượng trưng cho node đầu, con trỏ head sẽ trỏ đến node này
• Toa cuối (Tail node): Toa cuối đại diện cho node cuối và node cuối trỏ đến NULL
• Dây xích (Link): các pointer (con trỏ next)

4.3. Định nghĩa Node và LIST

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

struct LIST {
    Node* head;
    Node* tail;
};

• Cấu trúc Node: gồm hai thành phần là dữ liệu (data – trong ví dụ là một dữ liệu kiểu int) và một con trỏ (pointer) đến nút kế tiếp trong danh sách.
• Cấu trúc LIST: gồm hai thành phần là con trỏ đầu danh sách (head) và con trỏ đuôi (tail).

Ví dụ: Minh hoạ về 1 Danh sách liên kết đơn

4.4. Các thao tác với danh sách liên kết đơn

Khởi tạo danh sách liên kết đơn rỗng

void createEmptyList(LIST& L) {
	L.head = L.tail = NULL;
}

Hàm thêm vào đầu một danh sách liên kết đơn

void addHead(LIST& L, int x) {
    Node* p = new Node();
    p->data = x;
    p->next = NULL;
    if (L.head == NULL) {
        L.head = p;
        L.tail = L.head;
    }
    else {
        p->next = L.head;
        L.head = p;
    }
}

Hàm in ra Linked List

void printList(LIST L) {
    Node* p;
    if (L.head == NULL) {
        cout << "Empty List.";
    }
    else {
        p = L.head;
        while (p) {
            cout << p->data << "\t";
            p = p->next;
        }
    }
    cout << endl;
}

Hàm xoá phần tử ở vị trí k

void Remove_k_th(LIST& L, int k) {
    if (L.head == NULL) {
        return;
    }
    Node* p = L.head;
    if (k == 1) {
        L.head = p->next;
        delete p;
        return;
    }
    Node* p1 = L.head;
    for (int i = 0; i < k - 2 && p1 != NULL; i++) {
        p1 = p1->next;
    }
    if (p1 == NULL || p1->next == NULL) {
        return;
    }
    Node* p2 = p1->next;
    p1->next = p2->next;
    delete p2;
}