Danh sách liên kết vòng: Ưu điểm và nhược điểm

Danh sách liên kết vòng là gì?

Danh sách liên kết vòng là một chuỗi các nút được sắp xếp sao cho mỗi nút có thể được truy cập lại.tracMỗi "nút" là một phần tử tự tham chiếu với các con trỏ đến một hoặc hai nút trong vùng lân cận của nó.

Dưới đây là mô tả về danh sách liên kết vòng với 3 nút.

Ở đây, bạn có thể thấy rằng mỗi nút đều được tái tạo lại.tracCó thể tự liên kết với chính nó. Ví dụ trên là một danh sách liên kết đơn dạng vòng tròn.

Lưu ý: Danh sách liên kết vòng đơn giản nhất là một nút duy nhất có con trỏ next. tracnó quay trở lại chính nó, như hình dưới đây.

Cơ bản Operacác phần tử trong danh sách liên kết vòng tròn

Ba phép toán cơ bản trên danh sách liên kết vòng là:

1. chèn
2. Xóa và
3. Truyền tải

• Chèn là quá trình đặt một nút vào một vị trí xác định trong danh sách liên kết vòng.
• Xóa là quá trình loại bỏ một nút hiện có khỏi danh sách liên kết. Nút có thể được xác định bằng sự xuất hiện của giá trị hoặc vị trí của nó.
• Duyệt qua danh sách liên kết vòng là quá trình hiển thị toàn bộ nội dung của danh sách liên kết và sau đó lặp lại.tracquay trở lại nút nguồn.

Phần tiếp theo giải thích cách thức chèn hoạt động và hai loại chèn có thể có trong danh sách liên kết đơn vòng tròn.

chèn Operasản xuất

Đầu tiên, bạn tạo một nút mà con trỏ next của nó trỏ ngược về chính nó, như hình bên dưới. Nếu không có nút gốc này, lần chèn đầu tiên sẽ trở thành nút đầu tiên trong danh sách.

Tiếp theo, có hai khả năng:

• Chèn phần tử vào vị trí hiện tại của danh sách liên kết vòng. Điều này tương ứng với việc chèn vào đầu hoặc cuối của một danh sách liên kết đơn thông thường — trong danh sách liên kết vòng, đầu và cuối là cùng một điểm.
• Chèn sau một nút được lập chỉ mục. Nút phải được xác định bằng số chỉ mục tương ứng với giá trị phần tử của nó.

Để chèn vào đầu hoặc cuối danh sách liên kết vòng — tức là tại vị trí nút đầu tiên được thêm vào — hãy làm theo các bước sau:

• Bạn sẽ phải ngắt liên kết tự hiện có với nút hiện có
• Con trỏ tiếp theo của nút mới sẽ liên kết đến nút hiện có.
• Con trỏ tiếp theo của nút cuối cùng sẽ trỏ đến nút được chèn.

LƯU Ý: Con trỏ đánh dấu điểm bắt đầu hoặc kết thúc của vòng tròn có thể được gán lại cho bất kỳ nút nào. Quá trình duyệt vẫn sẽ quay trở lại cùng một nút, như đã thảo luận ở phần sau của bài viết này.

Các bước trong (a) i-iii được trình bày dưới đây:

(Nút hiện có)

Bước 1) Phá vỡ liên kết hiện có

Bước 2) Tạo liên kết chuyển tiếp (từ nút mới đến nút hiện có)

Bước 3) Tạo một liên kết vòng lặp đến nút đầu tiên

Tiếp theo, bạn sẽ thử chèn sau một nút.

Ví dụ, hãy chèn “VALUE2” sau nút chứa “VALUE0”, giả sử điểm bắt đầu là nút có “VALUE0”.

• Hãy ngắt liên kết giữa nút thứ nhất và nút thứ hai, rồi đặt nút có "VALUE2" vào giữa.
• Con trỏ next của nút đầu tiên liên kết đến nút mới, và con trỏ next của nút mới liên kết đến nút trước đó là nút thứ hai.
• Các phần còn lại của bố cục vẫn không thay đổi. Tất cả các nút đều được thiết lập lại.tracCó khả năng tự lo cho bản thân.

LƯU Ý: Vì cấu trúc này có tính chu kỳ, nên quy trình chèn một nút là giống nhau bất kể bạn chọn vị trí nào. Con trỏ đóng chu kỳ hoạt động giống như bất kỳ con trỏ nào khác trong danh sách.

Điều này được hiển thị dưới đây:

(Giả sử chỉ có hai nút. Đây là một trường hợp tầm thường)

Bước 1) Xóa liên kết bên trong giữa các nút được kết nối

Bước 2) Kết nối nút bên trái với nút mới

Bước 3) Kết nối nút mới với nút bên phải.

xóa Operasản xuất

Giả sử có một danh sách liên kết vòng 3 nút. Có hai trường hợp xóa phần tử:

• Xóa phần tử hiện tại
• Xóa sau một phần tử.

Xóa ở đầu/cuối:

1. Đi qua nút đầu tiên từ nút cuối cùng.
2. Việc xóa từ cuối chỉ cần một bước duyệt duy nhất, từ nút cuối cùng đến nút đầu tiên.
3. Xóa liên kết giữa nút cuối cùng và nút đầu tiên.
4. Liên kết nút cuối cùng với phần tử tiếp theo của nút đầu tiên.
5. Giải phóng nút đầu tiên.

(Thiết lập hiện tại)

Bước 1) Xóa liên kết vòng tròn

Bước 2) Xóa liên kết giữa nút đầu tiên và nút tiếp theo, liên kết nút cuối cùng với nút theo sau nút đầu tiên

Bước 3) Giải phóng/thu hồi bộ nhớ của nút đầu tiên

Xóa sau một nút:

1. Duyệt tiếp cho đến khi gặp nút tiếp theo cần xóa.
2. Di chuyển tới nút tiếp theo, đặt con trỏ lên nút trước đó.
3. Kết nối nút trước với nút sau nút hiện tại, sử dụng con trỏ tiếp theo của nó.
4. Giải phóng nút hiện tại (đã hủy liên kết).

Bước 1) Giả sử chúng ta cần xóa nút có “VALUE1”.

Bước 2) Xóa liên kết giữa nút trước đó và nút hiện tại, sau đó liên kết trực tiếp nút trước đó với nút được trỏ bởi con trỏ next của nút hiện tại (nút sau VALUE1).

Bước 3) Giải phóng hoặc giải phóng nút hiện tại.

Duyệt qua danh sách liên kết vòng

Để duyệt qua một danh sách liên kết vòng từ con trỏ cuối cùng, trước tiên hãy kiểm tra xem con trỏ cuối cùng có phải là NULL hay không. Nếu không phải là NULL, hãy kiểm tra xem danh sách chỉ có một phần tử hay không. Nếu không, hãy duyệt qua danh sách bằng một con trỏ tạm thời cho đến khi bạn quay lại con trỏ cuối cùng, như được minh họa trong hình động bên dưới.

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

Một số ưu điểm của danh sách liên kết vòng là:

1. Không có yêu cầu gán NULL trong mã. Danh sách vòng không bao giờ trỏ đến con trỏ NULL trừ khi được giải phóng hoàn toàn.
2. Danh sách liên kết vòng có lợi thế trong các thao tác ở cuối danh sách vì điểm bắt đầu và điểm kết thúc trùng nhau. Algorithms Ví dụ như phương pháp lập lịch luân phiên (round-robin scheduling) có thể xử lý các tiến trình trong hàng đợi một cách trơn tru, mà không gặp phải các con trỏ lơ lửng hoặc con trỏ NULL.
3. Danh sách liên kết vòng vẫn hỗ trợ tất cả các thao tác thông thường của danh sách liên kết đơn. Danh sách liên kết vòng danh sách liên kết kép Thậm chí có thể loại bỏ nhu cầu duyệt toàn bộ danh sách để định vị một phần tử — trong trường hợp xấu nhất, phần tử đích nằm đối diện với con trỏ bắt đầu, vì vậy chỉ cần duyệt tối đa một nửa danh sách.

Nhược điểm của danh sách liên kết vòng

Dưới đây là những nhược điểm của việc sử dụng danh sách liên kết vòng:

1. Danh sách vòng tròn phức tạp hơn danh sách liên kết đơn.
2. RevXóa một danh sách vòng phức tạp hơn so với việc đảo ngược một danh sách liên kết đơn hoặc liên kết đôi.
3. Nếu việc kết thúc vòng lặp không được xử lý cẩn thận, mã duyệt có thể rơi vào vòng lặp vô hạn.
4. Việc tìm ra điểm cuối của danh sách và viết các điều kiện điều khiển vòng lặp chính xác trở nên khó khăn hơn.
5. Việc chèn vào đầu danh sách đòi hỏi phải duyệt toàn bộ danh sách để đến được nút cuối cùng (xét về mặt lập trình).

Danh sách liên kết đơn dưới dạng danh sách liên kết vòng

Bạn nên đọc và thực hiện đoạn mã C dưới đây. Nó minh họa phép toán con trỏ liên quan đến danh sách liên kết đơn vòng tròn.

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

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Giải thích mã:

1. Hai dòng mã đầu tiên là các tệp tiêu đề cần thiết đi kèm.
2. Phần tiếp theo định nghĩa cấu trúc của mỗi nút tự tham chiếu. Nó chứa một giá trị và một con trỏ cùng kiểu với cấu trúc đó.
3. Mỗi thể hiện của cấu trúc liên kết với các đối tượng cấu trúc khác cùng loại.
4. Có nhiều nguyên mẫu hàm khác nhau cho:
   1. Thêm một phần tử vào danh sách liên kết trống
   2. Chèn tại hiện đang chỉ vị trí của danh sách liên kết vòng.
   3. Chèn sau một cái cụ thể lập chỉ mục giá trị trong danh sách liên kết.
   4. Xóa/Xóa sau một thông tin cụ thể lập chỉ mục giá trị trong danh sách liên kết.
   5. Xóa tại vị trí hiện tại của danh sách liên kết vòng
5. Hàm cuối cùng in từng phần tử thông qua việc duyệt vòng tròn ở bất kỳ trạng thái nào của danh sách liên kết.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

Giải thích mã:

1. Đối với đoạn mã addToEmpty, hãy cấp phát một nút trống bằng cách sử dụng hàm malloc().
2. Đưa dữ liệu đến vào nút tạm thời.
3. Gán nút tạm thời làm nút cuối cùng và đặt con trỏ tiếp theo của nó trỏ về chính nó để nút đơn lẻ đó trỏ ngược lại chính nó.
4. Trả về con trỏ cuối cùng cho ngữ cảnh chính (main()) / ứng dụng.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Giải thích mã

1. Nếu danh sách trống, hãy chuyển quyền điều khiển cho hàm addToEmpty() và trả lại quyền điều khiển.
2. Tạo một nút tạm thời để đặt sau nút hiện tại.
3. Nối các điểm trỏ như trong sơ đồ phía trên.
4. Trả về con trỏ cuối cùng, khớp với mẫu được sử dụng trong hàm trước đó.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Giải thích mã:

1. Nếu danh sách trống, hãy bỏ qua khóa tìm kiếm, thêm mục hiện tại làm nút duy nhất trong danh sách và trả về quyền điều khiển.
2. Trong mỗi vòng lặp do-while, con trỏ previous lưu giữ kết quả được duyệt lần cuối.
3. Chỉ khi đó bước duyệt tiếp theo mới diễn ra.
4. Vòng lặp do-while kết thúc khi tìm thấy dữ liệu mục tiêu hoặc khi biến temp quay trở lại con trỏ cuối cùng. Khối mã tiếp theo sẽ quyết định phải làm gì với mục đã tìm thấy.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Giải thích mã:

1. Nếu đã duyệt qua toàn bộ danh sách nhưng vẫn không tìm thấy mục cần tìm, hãy hiển thị thông báo “Không tìm thấy phần tử” và trả lại quyền điều khiển cho hàm gọi.
2. Nếu tìm thấy nút đích, hãy cấp phát một nút mới để chèn giá trị.
3. liên kết Nối nút trước đó với nút mới, và liên kết con trỏ next của nút mới với temp (biến duyệt).
4. Thao tác này đặt phần tử mới ngay sau nút đích trong danh sách liên kết vòng. Sau đó, quyền điều khiển được trả về cho hàm gọi.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Giải thích mã

1. Để xóa nút cuối cùng (hiện tại), trước tiên hãy kiểm tra xem danh sách có rỗng hay không. Nếu rỗng, không thể xóa bất kỳ phần tử nào.
2. Biến tạm thời làm tăng thêm một liên kết.
3. Liên kết con trỏ cuối cùng với nút sau nút đầu tiên.
4. Giải phóng con trỏ tạm thời để hủy cấp phát bộ nhớ cho nút chưa được liên kết.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Giải thích mã

1. Tương tự như hàm xóa trước đó, trước tiên hãy kiểm tra xem danh sách có rỗng hay không. Nếu rỗng, không thể xóa phần tử nào.
2. Hai con trỏ được chỉ định các vị trí cụ thể để xác định vị trí phần tử cần xóa.
3. Các con trỏ được dịch chuyển lần lượt từng cái một (nhiệt độ của các đường mòn trước đó).
4. Quá trình duyệt tiếp tục cho đến khi tìm thấy phần tử mục tiêu hoặc con trỏ tiếp theo quay trở lại nút cuối cùng.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

Giải thích chương trình

1. Nếu toàn bộ danh sách liên kết được duyệt mà không tìm thấy phần tử cần tìm, thông báo “Không tìm thấy phần tử” sẽ được hiển thị.
2. Ngược lại, phần tử sẽ bị ngắt liên kết và giải phóng ở bước 3 và 4.
3. Con trỏ trước đó được liên kết với nút được trỏ bởi con trỏ tiếp theo của temp (nút nằm sau nút đang bị xóa).
4. Sau đó, con trỏ tạm thời được giải phóng.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Giải thích mã

1. Việc duyệt qua từng nút riêng lẻ là không thể nếu không có nút nào — người dùng phải cấp phát hoặc chèn thêm một nút trước.
2. Nếu chỉ có một nút, không cần duyệt qua các nút — nội dung của nút được in trực tiếp và vòng lặp while không thực thi.
3. Nếu có nhiều hơn một nút, biến tạm thời sẽ in ra mọi mục cho đến phần tử cuối cùng.
4. Khi đạt đến phần tử cuối cùng, vòng lặp kết thúc và hàm trả quyền điều khiển về hàm main().

Ứng dụng của Danh sách liên kết vòng

• Triển khai lập lịch vòng tròn trong các quy trình hệ thống và lập lịch vòng tròn trong đồ họa tốc độ cao.
• Lập lịch Token-ring trong mạng máy tính.
• Được sử dụng trong các thiết bị hiển thị như bảng hiệu cửa hàng kỹ thuật số, nơi yêu cầu việc truyền tải dữ liệu liên tục.

Câu Hỏi Thường Gặp