Tìm hiểu danh sách liên kết vòng, ứng dụng và cài đặt bằng lập trình c++

Trong bài viết này Stanford sẽ giúp bạn đang học lập trình tìm hiểu về danh sách liên kết vòng (circular linked list), ứng dụng của nó trong thực tế và hướng dẫn cài đặt thuật toán bằng lập trình c++.

Danh sách liên kết vòng (circular linked list)

Danh sách liên kết vòng (circular linked list) là một cấu trúc dữ liệu trong đó các phần tử được liên kết với nhau theo một vòng tròn, tức là phần tử cuối cùng sẽ liên kết trở lại phần tử đầu tiên. Điều này khác với danh sách liên kết đơn hoặc đôi, nơi phần tử cuối cùng không liên kết với phần tử đầu tiên.

Đặc điểm của danh sách liên kết vòng:

  • Phần tử cuối cùng liên kết với phần tử đầu tiên: Điều này tạo thành một vòng tròn.
  • Không có phần tử nào có giá trị NULL: Mỗi phần tử đều có một liên kết đến phần tử tiếp theo.
  • Có thể là đơn hoặc đôi: Danh sách liên kết vòng có thể là danh sách liên kết đơn (chỉ có liên kết đến phần tử tiếp theo) hoặc danh sách liên kết đôi (có liên kết đến cả phần tử trước và phần tử tiếp theo).

Ứng dụng của danh sách liên kết vòng trong thực tế

Danh sách liên kết vòng có nhiều ứng dụng trong thực tế nhờ vào cấu trúc đặc biệt của nó. Dưới đây là một số ứng dụng phổ biến:

  • Hệ thống quản lý tài nguyên: Trong các hệ thống như bộ lập lịch CPU, danh sách liên kết vòng có thể được sử dụng để quản lý các tiến trình đang chờ xử lý. Mỗi tiến trình sẽ được xử lý theo thứ tự và sau đó quay lại đầu danh sách để tiếp tục vòng lặp.
  • Trò chơi: Trong các trò chơi nhiều người chơi, danh sách liên kết vòng có thể được sử dụng để quản lý lượt chơi của các người chơi. Sau khi một người chơi hoàn thành lượt của mình, lượt chơi sẽ chuyển sang người chơi tiếp theo theo vòng tròn.
  • Bộ đệm vòng (circular buffer): Danh sách liên kết vòng có thể được sử dụng để triển khai bộ đệm vòng, nơi dữ liệu mới sẽ ghi đè lên dữ liệu cũ khi bộ đệm đầy. Điều này hữu ích trong các ứng dụng như ghi âm liên tục hoặc lưu trữ dữ liệu cảm biến.
  • Hệ thống điều khiển vòng lặp: Trong các hệ thống điều khiển, danh sách liên kết vòng có thể được sử dụng để quản lý các tác vụ hoặc sự kiện theo chu kỳ, đảm bảo rằng mỗi tác vụ được thực hiện đúng thời gian.
  • Triển khai thuật toán: Một số thuật toán yêu cầu sử dụng danh sách liên kết vòng để tối ưu hóa hiệu suất hoặc đơn giản hóa việc triển khai, chẳng hạn như thuật toán Josephus.

Minh họa bằng lập trình C++:

Dưới đây là một ví dụ đơn giản về cách tạo và thao tác với danh sách liên kết vòng đơn trong lập trình C++:

#include <iostream>
using namespace std;
 
struct Node {
    int data;
    Node* next;
};
 
class CircularLinkedList {
public:
    Node* head;
 
    CircularLinkedList() {
        head = nullptr;
    }
 
    void append(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        if (!head) {
            head = newNode;
            head->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
        }
    }
 
    void deleteNode(int key) {
        if (!head) return;
 
        Node* current = head;
        Node* previous = nullptr;
 
        // Nếu node cần xóa là node đầu tiên
        if (head->data == key) {
            while (current->next != head) {
                current = current->next;
            }
            if (head == head->next) {
                delete head;
                head = nullptr;
            } else {
                current->next = head->next;
                delete head;
                head = current->next;
            }
            return;
        }
 
        // Tìm node cần xóa
        do {
            previous = current;
            current = current->next;
        } while (current != head && current->data != key);
 
        // Nếu tìm thấy node cần xóa
        if (current->data == key) {
            previous->next = current->next;
            delete current;
        }
    }
 
    void display() {
        if (!head) return;
        Node* temp = head;
        do {
            cout << temp->data << "\t";
            temp = temp->next;
        } while (temp != head);
        cout << endl;
    }
};
 
int main() {
    CircularLinkedList cll;
    cll.append(10);
    cll.append(20);
    cll.append(30);
    cll.display(); // Output: 10  20  30
    cll.deleteNode(2);
    cll.display(); // Output: 10 30
    return 0;
}
Trong ví dụ này, chúng ta đã tạo một danh sách liên kết vòng đơn giản với ba phần tử và hiển thị các phần tử của nó. Phương thức deleteNode(int key) sẽ xóa phần tử có giá trị bằng key khỏi danh sách liên kết vòng. Nếu phần tử cần xóa là phần tử đầu tiên, chúng ta cần cập nhật lại con trỏ head. Nếu không, chúng ta sẽ tìm phần tử cần xóa và điều chỉnh các liên kết để bỏ qua phần tử đó.

Để hiểu rõ hơn về thuật toán này bạn có thể thực hiện lập trình cài đặt thuật toán danh sách liên kết vòng (circular linked list) như hướng dẫn trong bài viết. Bạn có thể tìm hiểu thêm về danh sách liên kết đôi ở đây: danh sách liên kết đôi. Chúc các bạn thành công !

Bên cạnh đó bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé.

==========🎬 🎬 🎬==========
☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ
Hotline: 0963 723 236 - 0866 586 366
Website: https://stanford.com.vn
Facebook: https://www.facebook.com/Stanford.com.vn
Youtube: http://bit.ly/2TkKT7I

Tags: danh sách liên kết vòng, circular linked list