Bài 3.2 Thêm node và duyệt danh sách liên kết đơn

Nội dung bài học

Tạo danh sách liên kết đơn
Thêm node vào đầu danh sách
Thêm node vào cuối danh sách
Thêm node vào sau node x
Duyệt danh sách liên kết
Ví dụ và bài tập thực hành

Tạo danh sách liên kết đơn

Ta thực hiện hai bước: tạo node của danh sách và tạo danh sách.
Để tạo node ta sử dụng kiểu dữ liệu người dùng tự định nghĩa như struct(trong C) hoặc struct/class trong C++.
Ví dụ sau tạo node trong ngôn ngữ lập trình C++:

template<class T> class Node { // sử dụng lớp template
public:
    T data; // dữ liệu của node hiện tại
    Node<T>* next; // con trỏ trỏ tới node kế tiếp
    Node(T data) {
        this->next = nullptr; // khởi tạo mặc định khi tạo node
        this->data = data; // gán giá trị của data cho node
    }
};

Tiếp theo ta tạo danh sách liên kết đơn với các tùy chọn:
- Tạo danh sách liên kết chỉ gồm node head.
- Tạo danh sách liên kết bao gồm hai node head, tail.
Trong khóa học này sẽ tạo danh sách liên kết theo cả hai cách. Ưu điểm của cách thứ nhất là đơn giản. Nhược điểm là phải thực hiện nhiều thao tác để chèn node vào cuối danh sách liên kết.
Với cách thứ 2, ưu điểm là dễ dàng chèn thêm node mới vào cuối danh sách. Nhược điểm là tốn thêm chi phí bộ nhớ cho node tail.
Code mẫu C++:

template<class T> class LinkedList {
private:
    Node<T>* head; // con trỏ trỏ đến node đầu tiên trong danh sách
    Node<T>* tail; // con trỏ trỏ tới node cuối của danh sách
public:
    LinkedList() {
    }
    void add(T data) {
    }
    void addAfterX(T data, T x) {
    }

    void addTail(T data) { // chèn node vào cuối danh sách liên kết
    }

    void showList() { // hàm hiển thị danh sách liên kết
    }

    bool isEmpty() {}
};

Ví dụ tạo node trong ngôn ngữ lập trình C:

// tạo node
struct Node {
    int data;
    struct Node* next;
};

// khai báo sử dụng kiểu 'Node' thay cho 'struct Node'
typedef struct Node Node;

// tạo danh sách liên kết
typedef struct {
    Node* head; // con trỏ giữ tham chiếu tới node đầu tiên
    Node* tail; // con trỏ giữ tham chiếu tới node cuối cùng
} LinkedList;

// khởi tạo  danh sách liên kết
void init(LinkedList* linkedList) {
    linkedList->head = NULL;
    linkedList->tail = NULL;
}

Thêm node vào đầu danh sách liên kết

Các bước thực hiện để chèn node p vào đầu danh sách liên kết:
Kiểm tra xem danh sách có rỗng hay không.
Nếu danh sách rỗng, ta gán head = tail = p.
Nếu danh sách không rỗng:
- Gán head cho p->next: p->next = head;
- Gán lại head là p: head = p;
Code C++:

void add(T data) {
    Node<T>* p = new Node<T>(data); // tạo node mới p
    if (isEmpty()) { // kiểm tra xem danh sách rỗng không
        head = tail = p; // gán giá trị cho head, tail
    }
    else { // nếu danh sách không rỗng
        p->next = head; // cập nhật node next của p
        head = p; // cập nhật lại node head
    }
}

Code C:

// chèn thêm node mới vào đầu dslk
void addHead(LinkedList* list, int data) {
    Node* p = (Node*)malloc(sizeof(Node));
    if (p != NULL) {
        p->data = data;
        p->next = NULL;
        if (isEmpty(*list)) {
            list->head = p;
            list->tail = p;
        }
        else { // danh sách không rỗng
            p->next = list->head; // gán con trỏ next của p là head cũ của danh sách
            list->head = p; // cập nhật lại head mới
        }
    }
}

Thêm node vào cuối danh sách

Giả sử ta muốn thêm node p vào cuối danh sách liên kết hiện tại:
- Nếu danh sách rỗng, ta gán head = tail = p.
- Nếu danh sách không rỗng, ta thực hiện:
  - Gán p làm next của p: tail->next = p;
  - Cập nhật lại tail: tail = p;
Code mẫu C++:

void addTail(T data) { // chèn node vào cuối danh sách liên kết
    Node<T>* p = new Node<T>(data); // tạo node mới p
    if (!isEmpty()) {
        tail->next = p; // cập nhật node next của tail
        tail = p; // cập nhật lại tail mới
    }
    else {
        head = tail = p; // gán head, tail cùng bằng p
    }
}

Code mẫu C:

// thêm node vào cuối danh sách liên kết
void addTail(LinkedList* list, int data) {
    if (isEmpty(*list)) {
        addHead(list, data);
    }
    else {
        Node* p = (Node*)malloc(sizeof(Node));
        if (p != NULL) {
            p->data = data;
            p->next = NULL;
            list->tail->next = p; // gán con trỏ next của tail cũ của danh sách
            list->tail = p; // cập nhật lại tail mới
        }
    }
}

Thêm node vào sau node x

Giả sử ta muốn thêm node p sau node có giá trị C:
- Tìm node chứa data bằng C gọi là nodeX.
- Nếu tìm thấy và nodeX là node cuối: gọi hàm chèn vào cuối DSLK.
- Nếu tìm thấy và nodeX không phải node cuối của DSLK:
  - Gán node next của nodeX cho next của p: p->next = nodeX->next;
  - Gán node p cho node next của nodeX: nodeX->next = p;
- Nếu không tìm thấy node cần tìm, thông báo ra màn hình và kết thúc.
Code C++:

void addAfterX(T data, T x) {
    Node<T>* nodeX = head; // bắt đầu từ node head
    while (nodeX != nullptr) { // tìm nodeX
        if (nodeX->data == x) { // nếu tìm thấy
            break; // kết thúc việc tìm kiếm
        }
        nodeX = nodeX->next; // chuyển tới node kế tiếp
    }
    if (nodeX != nullptr) { // nếu tìm thấy
        if(nodeX == tail) { // và x là node cuối danh sách
            addTail(data); // thêm vào cuối dslk
        } else {
            Node<T>* p = new Node<T>(data); // tạo node mới p
            p->next = nodeX->next; // cập nhật next của p
            nodeX->next = p; // cập nhật next của nodeX
        }
    }
    else { // nếu không tìm thấy
        cout << "Khong tim thay node muc tieu\n";
    }
}

Code mẫu C:

// thêm vào sau node có giá trị x
void addAfterX(LinkedList* list, int data, int x) {
    if (isEmpty(*list)) { // nếu dslk rỗng, thêm vào đầu
        addHead(list, data);
    }
    else if(list->tail->data == x) { // nếu node có giá trị x là node cuối, thêm vào cuối
        addTail(list, data);
    }
    else { // tìm node có giá trị data == x
        Node* keyNode = list->head; // bắt đầu từ node đầu tiên
        while (keyNode != NULL) { // tìm đến khi hết danh sách
            if (keyNode->data == x) { // nếu gặp node cần tìm đầu tiên
                break; // kết thúc việc tìm kiếm
            }
            keyNode = keyNode->next; // chuyển đến node kế tiếp
        }
        if (keyNode == NULL) { // nếu không tìm thấy node x
            puts("==> Khong tim thay node x.");
            return; // kết thúc hàm này
        }
        else { // nếu tìm thấy x
            if(keyNode == list->tail) {
                addTail(list, data);
            } else {
                Node* p = (Node*)malloc(sizeof(Node)); // tạo node mới
                if (p == NULL) {
                    puts("==> Khong the cap phat bo nho.");
                }
                else {
                    p->next = NULL;
                    p->data = data;
                    p->next = keyNode->next;
                    keyNode->next = p;
                }
            }
        }
    }
}

Duyệt danh sách liên kết

Khai báo node p và khởi tạo bằng head: p = head;
Lặp chừng nào p chưa null:
- Xuất ra giá trị của p->data;
- Cập nhật p: p = p->next;
Code mẫu C++:

    void showList() { // hàm hiển thị danh sách liên kết
        Node<T>* p = head; // khởi đầu từ node head
        while (p != nullptr) // lặp chừng nào p chưa null
        {
            cout << p->data << " "; // hiển thị data của p
            p = p->next; // cập nhật p
        }
    }

Code mẫu C:

// hiển thị các phần hiện có của dslk ra màn hình
void showList(LinkedList list) {
    Node* p = list.head;
    while (p != NULL) {
        printf("%d => ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

Ví dụ hoàn chỉnh C++

#include <iostream>
using namespace std;

template<class T> class Node { // sử dụng lớp template
public:
    T data; // dữ liệu của node hiện tại
    Node<T>* next; // con trỏ trỏ tới node kế tiếp
    Node(T data) {
        this->next = nullptr; // khởi tạo mặc định khi tạo node
        this->data = data; // gán giá trị của data cho node
    }
};

template<class T> class LinkedList {
private:
    Node<T>* head; // con trỏ trỏ đến node đầu tiên trong danh sách
    Node<T>* tail; // con trỏ trỏ tới node cuối của danh sách
public:
    LinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    void add(T data) {
        Node<T>* p = new Node<T>(data); // tạo node mới p
        if (isEmpty()) { // kiểm tra xem danh sách rỗng không
            head = tail = p; // gán giá trị cho head, tail
        }
        else { // nếu danh sách không rỗng
            p->next = head; // cập nhật node next của p
            head = p; // cập nhật lại node head
        }
    }

    void addAfterX(T data, T x) {
        Node<T>* nodeX = head; // bắt đầu từ node head
        while (nodeX != nullptr) { // tìm nodeX
            if (nodeX->data == x) { // nếu tìm thấy
                break; // kết thúc việc tìm kiếm
            }
            nodeX = nodeX->next; // chuyển tới node kế tiếp
        }
        if (nodeX != nullptr) { // nếu tìm thấy
            if(nodeX == tail) { // nếu node x là node cuối
                addTail(data); // gọi hàm chèn vào cuối dslk
            } else {
                Node<T>* p = new Node<T>(data); // tạo node mới p
                p->next = nodeX->next; // cập nhật next của p
                nodeX->next = p; // cập nhật next của nodeX
            }
        }
        else { // nếu không tìm thấy
            cout << "Khong tim thay node muc tieu\n";
        }
    }

    void addTail(T data) { // chèn node vào cuối danh sách liên kết
        Node<T>* p = new Node<T>(data); // tạo node mới p
        if (!isEmpty()) {
            tail->next = p; // cập nhật node next của tail
            tail = p; // cập nhật lại tail
        }
        else {
            head = tail = p; // gán head, tail cùng bằng p
        }
    }

    void showList() { // hàm hiển thị danh sách liên kết
        Node<T>* p = head; // khởi đầu từ node head
        while (p != nullptr) // lặp chừng nào p chưa null
        {
            cout << p->data << " "; // hiển thị data của p
            p = p->next; // cập nhật p
        }
    }
    bool isEmpty() {
        return head == nullptr;
    }
};

int main() {
    LinkedList<string> list;
    list.addTail("Khanh");
    list.addTail("Hi");
    list.addTail("Mai");
    list.addTail("Nga");
    list.addTail("Oanh");
    list.addAfterX("Loan", "Khanh");
    list.addTail("Huong");
    list.showList();
}

Ví dụ hoàn chỉnh trong C

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

// tạo node của danh sách liên kết
// thêm node mới vào đầu dslk
// thêm node mới vào cuối dslk
// thêm node mới vào sau node có giá trị x
// hiển thị các node của dslk ra màn hình

// tạo node
struct Node {
    int data;
    struct Node* next;
};

// khai báo cho phép 'Node' làm tên kiểu thay vì 'struct Node'
typedef struct Node Node;

// tạo danh sách liên kết
typedef struct {
    Node* head; // con trỏ giữ tham chiếu tới node đầu tiên
    Node* tail; // con trỏ giữ tham chiếu tới node cuối cùng
} LinkedList;

// khởi tạo  danh sách liên kết
void init(LinkedList* linkedList) {
    linkedList->head = NULL;
    linkedList->tail = NULL;
}

// kiểm tra dslk rỗng
int isEmpty(LinkedList list) {
    return list.head == NULL;
}

// chèn thêm node mới vào đầu dslk
void addHead(LinkedList* list, int data) {
    Node* p = (Node*)malloc(sizeof(Node));
    if (p != NULL) {
        p->data = data;
        p->next = NULL;
        if (isEmpty(*list)) {
            list->head = p;
            list->tail = p;
        }
        else { // danh sách không rỗng
            p->next = list->head; // gán con trỏ next của p là head cũ của danh sách
            list->head = p; // cập nhật lại head mới
        }
    }
}

// thêm node vào cuối danh sách liên kết
void addTail(LinkedList* list, int data) {
    if (isEmpty(*list)) {
        addHead(list, data);
    }
    else {
        Node* p = (Node*)malloc(sizeof(Node));
        if (p != NULL) {
            p->data = data;
            p->next = NULL;
            list->tail->next = p; // gán con trỏ next của tail cũ của danh sách
            list->tail = p; // cập nhật lại tail mới
        }
    }
}

// thêm vào sau node có giá trị x
void addAfterX(LinkedList* list, int data, int x) {
    if (isEmpty(*list)) { // thêm vào đầu
        addHead(list, data);
    }
    else if (list->tail->data == x) { // thêm vào cuối
        addTail(list, data);
    }
    else { // tìm node có giá trị data == x
        Node* keyNode = list->head;
        while (keyNode != NULL) {
            if (keyNode->data == x) {
                break;
            }
            keyNode = keyNode->next;
        }
        if (keyNode == NULL) { // nếu không tìm thấy node x
            puts("==> Khong tim thay node x.");
            return;
        }
        else { // nếu tìm thấy x
            if(keyNode == list->tail) { // nếu node chứa x là node cuối dslk
                addTail(list, data); // gọi hàm chèn vào cuối dslk
            } else {
                Node* p = (Node*)malloc(sizeof(Node)); // tạo node mới
                if (p == NULL) {
                    puts("==> Khong the cap phat bo nho.");
                }
                else {
                    p->next = NULL;
                    p->data = data;
                    p->next = keyNode->next;
                    keyNode->next = p;
                }
            }
        }
    }
}

// hiển thị các phần hiện có của dslk ra màn hình
void showList(LinkedList list) {
    Node* p = list.head;
    while (p != NULL) {
        printf("%d => ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

int main() {
    LinkedList singlyLinkedList;
    init(&singlyLinkedList);

    // thêm vào đầu danh sách
    for (int i = 0; i < 10; i++) {
        addHead(&singlyLinkedList, i + 1);
    }
    puts("==> Sau khi them vao dau DSLK:");
    showList(singlyLinkedList);

    // thêm vào cuối danh sách
    addTail(&singlyLinkedList, 100);
    addTail(&singlyLinkedList, 200);
    addTail(&singlyLinkedList, 300);
    addTail(&singlyLinkedList, 400);
    puts("==> Sau khi them vao cuoi DSLK:");
    showList(singlyLinkedList);

    // thêm vào sau node có giá trị x đầu tiên
    addAfterX(&singlyLinkedList, 500, 200);
    puts("==> Sau khi them vao sau node 500:");
    showList(singlyLinkedList);
    addAfterX(&singlyLinkedList, 600, 400);
    puts("==> Sau khi them vao sau node 400:");
    showList(singlyLinkedList);
    addAfterX(&singlyLinkedList, 700, 10);
    puts("==> Sau khi them vao sau node 10:");
    showList(singlyLinkedList);

    return 0;
}

==> Sau khi them vao dau DSLK:
10 => 9 => 8 => 7 => 6 => 5 => 4 => 3 => 2 => 1 => NULL
==> Sau khi them vao cuoi DSLK:
10 => 9 => 8 => 7 => 6 => 5 => 4 => 3 => 2 => 1 => 100 => 200 => 300 => 400 => NULL
==> Sau khi them vao sau node 500:
10 => 9 => 8 => 7 => 6 => 5 => 4 => 3 => 2 => 1 => 100 => 200 => 500 => 300 => 400 => NULL
==> Sau khi them vao sau node 400:
10 => 9 => 8 => 7 => 6 => 5 => 4 => 3 => 2 => 1 => 100 => 200 => 500 => 300 => 400 => 600 => NULL
==> Sau khi them vao sau node 10:
10 => 700 => 9 => 8 => 7 => 6 => 5 => 4 => 3 => 2 => 1 => 100 => 200 => 500 => 300 => 400 => 600 => NULL

Bài tập thực hành

Tải đề bài: nhấn vào đây
Bài giải mẫu: nhấn vào đây

Bài 3.2 Thêm node và duyệt danh sách liên kết đơn

Nội dung bài học

Tạo danh sách liên kết đơn

Thêm node vào đầu danh sách liên kết

Thêm node vào cuối danh sách

Thêm node vào sau node x

Duyệt danh sách liên kết

Ví dụ hoàn chỉnh C++

Ví dụ hoàn chỉnh trong C

Bài tập thực hành

Để lại nhận xét Hủy

Đăng nhập với tài khoản trang web của bạn

Đăng ký tài khoản mới

Modal title