Rate this post

Linked list là một trong những cấu trúc dữ liệu cơ bản và thiết yếu trong lập trình, được thiết kế để giải quyết một số hạn chế của mảng thông thường. Chúng bao gồm một chuỗi các “node” liên kết với nhau, mỗi node chứa dữ liệu và một hoặc nhiều con trỏ đến node tiếp theo hoặc trước đó trong chuỗi. Đây là một cấu trúc dữ liệu động, cho phép thực hiện các thao tác thêm và xóa các phần tử một cách hiệu quả mà không cần tái cấu trúc toàn bộ cấu trúc dữ liệu như khi sử dụng mảng.

Tóm tắt nội dung

Định Nghĩa về Linked List

Một linked list được định nghĩa là một chuỗi các phần tử, được gọi là node, trong đó mỗi node chứa hai thành phần chính: dữ liệu và một hoặc nhiều con trỏ liên kết. Con trỏ này có thể trỏ đến node tiếp theo trong danh sách, tạo thành một singly linked list, hoặc có thể bao gồm cả con trỏ trỏ đến node trước đó, tạo thành một doubly linked list. Node cuối cùng trong danh sách thường trỏ đến NULL, biểu thị rằng đây là node cuối cùng.

So Sánh Linked List với Mảng: Ưu và Nhược Điểm

Ưu điểm của Linked List so với Mảng:

Động: Linked list không yêu cầu kích thước cố định ban đầu, cho phép cấu trúc mở rộng và thu hẹp linh hoạt theo nhu cầu sử dụng thực tế.
Quản lý bộ nhớ hiệu quả: Các node trong linked list không cần được cấp phát bộ nhớ liên tục; chúng có thể tận dụng các phân mảnh bộ nhớ rải rác, giảm thiểu lãng phí tài nguyên.
Chèn và xóa hiệu quả: Các thao tác thêm và xóa node không yêu cầu di chuyển các phần tử khác trong cấu trúc, làm giảm đáng kể chi phí thực thi so với mảng.

Nhược điểm của Linked List so với Mảng:

Truy cập: Truy cập các phần tử trong linked list không trực tiếp như mảng (O(1)), mà phải duyệt qua từng node từ đầu đến node cần truy cập (O(n)).
Sử dụng bộ nhớ cao hơn: Mỗi node trong linked list cần thêm không gian cho ít nhất một con trỏ, làm tăng lượng bộ nhớ sử dụng so với mảng.
Hiệu suất: Do các node không liên tục trong bộ nhớ, hiệu suất truy cập có thể bị ảnh hưởng, làm giảm hiệu quả của bộ nhớ cache so với mảng có cấu trúc liên tục.

Các Loại Linked List

Singly Linked List: Đây là dạng đơn giản nhất, mỗi node chỉ chứa một con trỏ đến node tiếp theo. Phù hợp cho các ứng dụng đơn giản, nơi chỉ cần duyệt danh sách theo một hướng.
Doubly Linked List: Mỗi node chứa hai con trỏ, một trỏ đến node tiếp theo và một trỏ về node trước đó, cho phép duyệt danh sách theo cả hai hướng. Điều này làm tăng tính linh hoạt và dễ dàng trong việc xử lý dữ liệu.
Circular Linked List: Trong cấu trúc này, node cuối cùng của danh sách liên kết trỏ lại đến node đầu tiên, tạo thành một vòng lặp. Loại linked list này hữu ích trong các ứng dụng cần duyệt dữ liệu liên tục, như lập lịch trình và quản lý tài nguyên.

Mỗi loại linked list đều có những đặc điểm và ứng dụng riêng biệt, phù hợp với các yêu cầu khác nhau của các thuật toán hoặc ứng dụng, và việc lựa chọn phù hợp phụ thuộc vào yêu cầu về tính năng và hiệu suất của chương trình.

Cấu trúc của một Node

Trong bất kỳ cấu trúc dữ liệu linked list nào, node là thành phần cơ bản và thiết yếu. Mỗi node trong linked list thường chứa hai thành phần chính: dữ liệu và một hoặc nhiều con trỏ liên kết với node(s) khác trong danh sách.

Giới Thiệu về Node

Node là một đơn vị cấu trúc chứa thông tin (dữ liệu) cùng với tham chiếu (con trỏ) đến node tiếp theo trong chuỗi, và trong trường hợp của doubly linked list, cả đến node trước đó. Thông qua những con trỏ này, các node được nối với nhau theo một trình tự nhất định, tạo thành một chuỗi dữ liệu có thể dễ dàng thêm vào hoặc xóa bỏ mà không cần tái cấu trúc toàn bộ cấu trúc.

Cấu Trúc Dữ Liệu cho một Node trong Singly và Doubly Linked List

Singly Linked List Node Structure
Đối với singly linked list, mỗi node chứa một phần dữ liệu và một con trỏ đến node tiếp theo trong danh sách. Cú pháp cơ bản để định nghĩa một node trong singly linked list trong C++ có thể như sau:

struct Node {
    int data;       // Dữ liệu mà node chứa
    Node* next;     // Con trỏ đến node tiếp theo trong danh sách

    // Constructor để khởi tạo node
    Node(int data) : data(data), next(nullptr) {}
};

Doubly Linked List Node Structure
Trong doubly linked list, mỗi node có thêm một con trỏ nữa so với singly linked list, trỏ về node trước đó, cho phép điều hướng hai chiều trong danh sách:

struct Node {
    int data;        // Dữ liệu mà node chứa
    Node* next;      // Con trỏ đến node tiếp theo trong danh sách
    Node* prev;      // Con trỏ đến node trước đó trong danh sách

    // Constructor để khởi tạo node
    Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};

Ví Dụ Mã Nguồn Cơ Bản về Cách Định Nghĩa một Node

Dưới đây là ví dụ về cách khai báo và khởi tạo một node cho một singly linked list:

#include <iostream>
using namespace std;

int main() {
    // Khởi tạo node đầu tiên
    Node* head = new Node(10);

    // Thêm node tiếp theo
    head->next = new Node(20);

    // In ra dữ liệu của từng node
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;

    return 0;
}

Trong đoạn mã này, chúng ta đã tạo một linked list đơn giản với hai node. Mỗi node được khởi tạo với dữ liệu và con trỏ tiếp theo, qua đó minh họa cách liên kết các node lại với nhau. Các node được truy cập và dữ liệu được in ra thông qua một vòng lặp đi qua từng node cho đến khi gặp nullptr.

Triển khai Singly Linked List

Singly linked list là một trong những cấu trúc dữ liệu cơ bản, cho phép lưu trữ một tập hợp các đối tượng theo một thứ tự nhất định. Mỗi phần tử trong danh sách liên kết (node) chứa một phần dữ liệu và một con trỏ đến node tiếp theo trong danh sách. Dưới đây là cách triển khai các phương thức cơ bản cho singly linked list: thêm (insert), xóa (delete), và tìm kiếm (search).

Cách Triển Khai Phương Thức Insert

Việc thêm một node vào singly linked list có thể được thực hiện ở hai vị trí chính: đầu danh sách hoặc cuối danh sách.

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

void insertAtHead(Node*& head, int newData) {
    Node* newNode = new Node(newData); // Tạo node mới
    newNode->next = head; // Làm cho node mới trỏ đến node đầu tiên hiện tại
    head = newNode; // Cập nhật head để trỏ đến node mới
}

Thêm 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 đến phần tử cuối cùng của danh sách, sau đó làm cho con trỏ next của nó trỏ đến node mới.

void insertAtTail(Node*& head, int newData) {
    Node* newNode = new Node(newData); // Tạo node mới
    if (head == nullptr) { // Nếu danh sách rỗng
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) { // Duyệt đến phần tử cuối cùng
            temp = temp->next;
        }
        temp->next = newNode; // Chèn node mới vào cuối
    }
}

Cách Triển Khai Phương Thức Delete

Xóa một node yêu cầu duyệt tìm node đó trong danh sách, sau đó thay đổi con trỏ của node liền trước nó để trỏ qua node đó đến node kế tiếp.

void deleteNode(Node*& head, int key) {
    Node* temp = head;
    Node* prev = nullptr;
    if (temp != nullptr && temp->data == key) { // Nếu node để xóa là head
        head = temp->next; // Thay đổi head
        delete temp; // Giải phóng node head cũ
        return;
    }
    // Tìm key và node trước của node cần xóa
    while (temp != nullptr && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == nullptr) return; // Nếu key không tồn tại
    prev->next = temp->next; // Unlink node từ danh sách liên kết
    delete temp; // Giải phóng bộ nhớ
}

Cách Triển Khai Phương Thức Search

Tìm kiếm một giá trị trong singly linked list đơn giản là duyệt qua từng node và so sánh dữ liệu của chúng với giá trị cần tìm.

bool search(Node* head, int key) {
    Node* current = head; // Khởi tạo current
    while (current != nullptr) {
        if (current->data == key) {
            return true; // Đã tìm thấy data
        }
        current = current->next; // Di chuyển đến node tiếp theo
    }
    return false; // Không tìm thấy data trong danh sách
}

Qua đoạn mã trên, chúng ta đã thấy cách triển khai các thao tác cơ bản trên singly linked list trong C++. Những phương thức này là nền tảng cho việc quản lý dữ liệu một cách linh hoạt và hiệu quả trong các ứng dụng thực tế sử dụng linked list.

Triển khai Circular Linked List

Circular linked list là một biến thể đặc biệt của linked list, trong đó node cuối cùng trong danh sách liên kết lại với node đầu tiên, tạo thành một vòng lặp liên tục. Điều này mang lại một số lợi ích đặc biệt so với các dạng linked list truyền thống khác.

Đặc Điểm của Circular Linked List

Circular linked list có một số đặc điểm nổi bật:

Không có Node Cuối Cùng Rõ Ràng: Trong circular linked list, không có node nào được định nghĩa là node cuối cùng vì mỗi node đều trỏ đến một node khác trong danh sách, tạo thành một vòng lặp liên tục.
Duyệt Vô Tận: Có thể duyệt qua danh sách liên tục mà không cần quan tâm đến điểm bắt đầu hay kết thúc, điều này rất hữu ích cho các ứng dụng cần xử lý liên tục và lặp đi lặp lại các phần tử.
Thống Nhất trong Thêm và Xóa Node: Các phương thức thêm và xóa nodes không cần xử lý trường hợp đặc biệt cho node đầu hoặc node cuối như trong singly hoặc doubly linked list.

Cách Triển Khai Thêm và Xóa Nodes trong Circular Linked List

Thêm Node:

Việc thêm node vào circular linked list có thể thực hiện ở bất kỳ vị trí nào, nhưng thường thêm vào cuối danh sách là phổ biến nhất do dễ dàng quản lý:

void addToEnd(Node*& head, int data) {
    Node* newNode = new Node(data);
    if (head == nullptr) {
        newNode->next = newNode;
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = head;
    }
}

Xóa Node:

Xóa node từ circular linked list đòi hỏi phải tìm node trước node cần xóa để cập nhật con trỏ của nó:

void deleteNode(Node*& head, int key) {
    if (head == nullptr) return;
    Node* curr = head, *prev = nullptr;
    while (curr->data != key) {
        if (curr->next == head) return; // Node không tồn tại
        prev = curr;
        curr = curr->next;
    }
    if (curr == head && curr->next == head) {
        head = nullptr;
    } else {
        if (curr == head) {
            prev = head;
            while (prev->next != head) {
                prev = prev->next;
            }
            head = curr->next;
            prev->next = head;
        } else {
            prev->next = curr->next;
        }
    }
    delete curr;
}

Ứng Dụng Thực Tế của Circular Linked List

Circular linked list có nhiều ứng dụng thực tiễn, bao gồm:

Quản lý Các Quy Trình Hệ Thống: Trong các hệ điều hành, circular linked list thường được sử dụng để quản lý các quy trình đang chạy, cho phép chuyển đổi liên tục giữa các quy trình một cách hiệu quả.
Ứng Dụng Trong Multimedia: Circular linked list cũng rất hữu ích trong các ứng dụng multimedia, ví dụ như tạo các danh sách phát nhạc lặp đi lặp lại mà không cần thao tác quay lại đầu danh sách.
Ứng Dụng trong Ứng dụng Thời gian Thực

Triển khai Doubly Linked List

Doubly linked list cung cấp một bước tiến vượt trội so với singly linked list nhờ vào cấu trúc của nó, cho phép mỗi node có hai con trỏ: một trỏ tới node tiếp theo và một trỏ về node trước. Điều này không những tăng cường khả năng điều hướng mà còn làm cho các thao tác thêm và xóa trở nên hiệu quả hơn.

Đặc Điểm của Doubly Linked List So Với Singly Linked List

Điều hướng hai chiều: Trái ngược với singly linked list chỉ cho phép di chuyển theo một hướng, doubly linked list cho phép điều hướng qua lại giữa các node một cách dễ dàng.
Dễ dàng xóa: Trong singly linked list, để xóa một node, bạn cần phải tìm node trước đó để cập nhật con trỏ next. Trong khi đó, với doubly linked list, mỗi node đã tự chứa con trỏ đến node trước đó, giúp việc xóa trở nên đơn giản hơn mà không cần duyệt tìm node trước.
Sử dụng bộ nhớ nhiều hơn: Mỗi node trong doubly linked list chứa thêm một con trỏ, do đó sử dụng nhiều bộ nhớ hơn so với singly linked list.

Triển Khai Các Phương Thức Thêm và Xóa Nodes

Thêm Node vào Doubly Linked List:

Thêm vào Đầu Danh Sách:
Việc thêm một node mới vào đầu danh sách đòi hỏi việc cập nhật con trỏ của node hiện tại đầu tiên và thiết lập liên kết với node mới.

void insertAtHead(Node*& head, int value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    newNode->prev = nullptr;
    if (head != nullptr) {
        head->prev = newNode;
    }
    head = newNode;
}

Thêm vào Cuối Danh Sách:
Thêm một node vào cuối danh sách yêu cầu tìm node cuối cùng và cập nhật các con trỏ của nó và node mới.

void insertAtTail(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        newNode->prev = nullptr;
        head = newNode;
        return;
    }
    Node* lastNode = head;
    while (lastNode->next != nullptr) {
        lastNode = lastNode->next;
    }
    lastNode->next = newNode;
    newNode->prev = lastNode;
    newNode->next = nullptr;
}

Xóa Node trong Doubly Linked List:

Xóa một Node Bất Kỳ:
Việc xóa node trong doubly linked list trở nên đơn giản hơn do có thể truy cập trực tiếp node trước đó.

void deleteNode(Node*& head, Node* delNode) {
    if (head == nullptr || delNode == nullptr) {
        return;
    }
    if (head == delNode) {
        head = delNode->next;
    }
    if (delNode->next != nullptr) {
        delNode->next->prev = delNode->prev;
    }
    if (delNode->prev != nullptr) {
        delNode->prev->next = delNode->next;
    }
    delete delNode;
}

Quản Lý Node Trước và Sau Khi Thêm hoặc Xóa

Khi thực hiện thêm hoặc xóa node, việc quản lý các con trỏ prev và next là rất quan trọng để đảm bảo liên kết giữa các node không bị gián đoạn. Đối với mỗi thao tác:

Sau khi thêm, cần cập nhật con trỏ của node liền kề để chúng trỏ chính xác đến node mới hoặc cập nhật node mới trỏ đúng về node liền kề.
Khi xóa, việc cập nhật các node liền kề để bỏ qua node bị xóa và liên kết trực tiếp với nhau là bước không thể bỏ qua để tránh “dangling pointers” và rò rỉ bộ nhớ.

Triển khai và quản lý hiệu quả doubly linked list không những tăng cường khả năng của chương trình mà còn giúp tối ưu hóa tài nguyên và đảm bảo tính toàn vẹn của dữ liệu trong các thao tác phức tạp.

Thao Tác Trên Linked List

Linked list là một cấu trúc dữ liệu động, cho phép thực hiện nhiều thao tác phức tạp mà không cần phải cấp phát hoặc giải phóng bộ nhớ liên tục như trong mảng. Các thao tác như sắp xếp, đảo ngược và tìm kiếm là cơ bản nhưng vô cùng quan trọng để quản lý và sử dụng hiệu quả linked list.

Sắp Xếp Dữ Liệu Trong Linked List

Sắp xếp là một trong những thao tác quan trọng nhất trên các cấu trúc dữ liệu. Trong linked list, sắp xếp có thể được thực hiện bằng nhiều thuật toán, nhưng merge sort là một trong những thuật toán hiệu quả nhất do nó có hiệu suất ổn định là O(n log n) và không đòi hỏi không gian bổ sung như trong quick sort.

Ví dụ về Merge Sort trên Linked List:

Node* merge(Node* left, Node* right) {
    if (!left)
        return right;
    if (!right)
        return left;

    if (left->data < right->data) {
        left->next = merge(left->next, right);
        left->next->prev = left;
        left->prev = nullptr;
        return left;
    } else {
        right->next = merge(left, right->next);
        right->next->prev = right;
        right->prev = nullptr;
        return right;
    }
}

Node* mergeSort(Node* head) {
    if (!head || !head->next)
        return head;
    Node* second = split(head);

    head = mergeSort(head);
    second = mergeSort(second);

    return merge(head, second);
}

Đảo Ngược Linked List

Đảo ngược linked list là một thao tác thường gặp, yêu cầu thay đổi hướng của tất cả các con trỏ next để đầu danh sách trở thành cuối và ngược lại.

Cách đảo ngược một singly linked list:

Node* reverse(Node* head) {
    Node* current = head;
    Node* prev = nullptr, *next = nullptr;

    while (current != nullptr) {
        next = current->next; // lưu trữ node tiếp theo
        current->next = prev; // đảo con trỏ
        prev = current; // di chuyển prev và current một bước về phía trước
        current = next;
    }
    head = prev;
    return head;
}

Tìm Kiếm và Xử Lý Lỗi Phổ Biến Trong Quản Lý Linked List

Tìm kiếm một giá trị trong linked list thường được thực hiện bằng cách duyệt từ đầu đến cuối danh sách.

Ví dụ về tìm kiếm:

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == key)
            return current;
        current = current->next;
    }
    return nullptr; // Trả về nullptr nếu không tìm thấy
}

Xử lý lỗi phổ biến:

Lỗi truy cập: Cố gắng truy cập vào node không tồn tại, như truy cập phần tử sau node cuối cùng.
Rò rỉ bộ nhớ: Quên giải phóng bộ nhớ đã cấp phát cho các node sau khi chúng không còn được sử dụng nữa.
Con trỏ treo: Giữ con trỏ đến các node đã được giải phóng.

Các thao tác này, khi được hiểu rõ và sử dụng đúng cách, sẽ giúp tăng cường hiệu quả sử dụng linked list trong các ứng dụng thực tế, giúp quản lý dữ liệu một cách linh hoạt và hiệu quả.

C/C++

linked list trong C++: những điều cần biết