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 nguyên về chính nó. Ở đây, “nút” là một phần tử tự tham chiếu với các con trỏ tới một hoặc hai nút ở 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ó thể truy xuất được chính nó. Ví dụ hiển thị ở trên là một danh sách liên kết đơn tròn.

Lưu ý: Danh sách liên kết vòng đơn giản nhất là một nút chỉ theo dõi chính nó như được hiển thị

Cơ bản Operacác mục trong danh sách liên kết vòng

Các thao tác cơ bản trên danh sách liên kết vòng là:

chèn
Xóa và
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ó.
Truyền tải 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à truy ngược lại nút nguồn.

Trong phần tiếp theo, bạn sẽ hiểu cách chèn một nút và các kiểu chèn có thể có trong Danh sách liên kết đơn vòng.

chèn Operasản xuất

Ban đầu, bạn cần tạo một nút trỏ đến chính nó như trong hình này. Nếu không có nút này, thao tác chèn sẽ tạo nút đầu tiên.

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

Chèn 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 phần cuối của danh sách liên kết số ít thông thường. Trong danh sách liên kết vòng, phần đầu và phần cuối giống nhau.
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/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,

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ỏ là mã thông báo chính hoặc điểm bắt đầu/kết thúc của vòng tròn có thể được thay đổi. Nó vẫn sẽ quay trở lại cùng một nút khi truyền tải, đã được thảo luận trước.

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ụ: chúng ta hãy chèn “VALUE2” sau nút có “VALUE0”. Giả sử rằng điểm bắt đầu là nút có “VALUE0”.

Bạn sẽ phải ngắt ranh giới giữa nút thứ nhất và nút thứ hai và đặt nút có “VALUE2” ở giữa.
Con trỏ tiếp theo của nút đầu tiên phải liên kết với nút này và con trỏ tiếp theo của nút này phải liên kết với nút thứ hai trước đó.
Phần còn lại của sự sắp xếp vẫn không thay đổi. Tất cả các nút đều có thể truy xuất được chính chúng.

LƯU Ý: Vì có sự sắp xếp theo chu kỳ nên việc chèn một nút bao gồm quy trình tương tự đối với bất kỳ nút nào. Con trỏ hoàn thành một chu trình sẽ hoàn thành chu trình đó giống như bất kỳ nút nào khác.

Đ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ử danh sách liên kết vòng gồm 3 nút. Các trường hợp xóa được đưa ra dưới đây:

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

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

Đi qua nút đầu tiên từ nút cuối cùng.
Để xóa từ cuối, chỉ cần thực hiện một bước truyền tải từ nút cuối cùng đến nút đầu tiên.
Xóa liên kết giữa nút cuối cùng và nút tiếp theo.
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.
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 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/giải phóng nút đầu tiên

Xóa sau một nút:

Di chuyển cho đến nút tiếp theo là nút cần xóa.
Di chuyển tới nút tiếp theo, đặt con trỏ lên nút trước đó.
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ó.
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. Liên kết nút trước đó với nút tiếp theo được trỏ bởi nút hiện tại (với 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 danh sách liên kết vòng, bắt đầu từ con trỏ cuối cùng, hãy kiểm tra xem con trỏ cuối cùng có phải là NULL không. Nếu điều kiện này là sai, hãy kiểm tra xem chỉ có một phần tử. Nếu không, hãy duyệt bằng con trỏ tạm thời cho đến khi con trỏ cuối cùng được chạm tới một lần nữa hoặc nhiều lần tùy theo nhu cầu, như được hiển thị trong GIF 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à:

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.
Danh sách liên kết vòng tròn có lợi thế cho các hoạt động cuối vì điểm bắt đầu và kết thúc trùng nhau. Algorithms chẳng hạn như lập lịch Round Robin có thể loại bỏ gọn gàng các quy trình được xếp hàng theo kiểu vòng tròn mà không gặp phải các con trỏ lơ lửng hoặc tham chiếu NULL.
Danh sách liên kết vòng cũng thực hiện tất cả các chức năng thông thường của danh sách liên kết đơn. Trên thực tế, hình tròn danh sách liên kết đôi được thảo luận dưới đây thậm chí có thể loại bỏ nhu cầu duyệt toàn bộ chiều dài để xác định vị trí một phần tử. Phần tử đó nhiều nhất sẽ chỉ hoàn toàn ngược lại với phần đầu, chỉ hoàn thành một nửa danh sách được liên kết.

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:

Danh sách tròn phức tạp hơn so với danh sách liên kết đơn.
RevDanh sách vòng tròn phức tạp hơn so với danh sách đơn hoặc danh sách đôi.
Nếu không được xử lý cẩn thận, mã có thể bị lặp vô hạn.
Khó tìm thấy phần cuối của danh sách và điều khiển vòng lặp.
Chèn vào Bắt đầu, chúng ta phải duyệt qua danh sách đầy đủ để tìm nút cuối cùng. (Góc nhìn thực hiện)

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

Bạn được khuyến khích cố gắng đọc và triển khai mã bên dưới. Nó trình bày số học con trỏ liên quan đến danh sách liên kết vòng.

#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ã:

Hai dòng mã đầu tiên là các tệp tiêu đề cần thiết đi kèm.
Phần tiếp theo mô tả 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.
Mỗi cấu trúc liên kết nhiều lần tới các đối tượng cấu trúc cùng loại.
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
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ã:

Đối với mã addEmpty, hãy phân bổ một nút trống bằng hàm malloc.
Đối với nút này, đặt dữ liệu vào biến tạm thời.
Gán và liên kết biến duy nhất với biến tạm thời
Trả phần tử cuối cùng về ngữ cảnh chính()/ứ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ã

Nếu không có phần tử nào để chèn thì bạn nên đảm bảo thêm vào danh sách trống và trả lại quyền kiểm soát.
Tạo phần tử tạm thời để đặt sau phần tử hiện tại.
Liên kết các con trỏ như được hiển thị.
Trả về con trỏ cuối cùng như 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ã:

Nếu không có phần tử nào trong danh sách, hãy bỏ qua dữ liệu, thêm mục hiện tại làm mục cuối cùng trong danh sách và trả về quyền kiểm soát
Đối với mỗi lần lặp trong vòng lặp do-while, hãy đảm bảo rằng có một con trỏ trước đó chứa kết quả duyệt qua lần cuối.
Chỉ khi đó lần truyền tải tiếp theo mới có thể xảy ra.
Nếu dữ liệu được tìm thấy hoặc temp quay trở lại con trỏ cuối cùng thì do-while sẽ kết thúc. Phần mã tiếp theo quyết định những gì phải được thực hiện với mục nà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ã:

Nếu toàn bộ danh sách đã được duyệt nhưng vẫn không tìm thấy mục, hãy hiển thị thông báo “không tìm thấy mục” và sau đó trả lại quyền điều khiển cho người gọi.
Nếu tìm thấy một nút và/hoặc nút đó chưa phải là nút cuối cùng thì hãy tạo một nút mới.
liên kết nút trước đó với nút mới. Liên kết nút hiện tại với temp (biến truyền tải).
Điều này đảm bảo rằng phần tử được đặt sau một nút cụ thể trong danh sách liên kết vòng. Quay lại với người 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ã

Để chỉ xóa nút cuối cùng (hiện tại), hãy kiểm tra xem danh sách này có trống không. Nếu có thì không thể loại bỏ phần tử nào.
Biến tạm thời chỉ đi qua một liên kết về phía trước.
Liên kết con trỏ cuối cùng với con trỏ sau con trỏ đầu tiên.
Giải phóng con trỏ tạm thời. Nó giải phóng con trỏ cuối cùng không đượ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ã

Giống như chức năng loại bỏ trước đó, hãy kiểm tra xem có phần tử nào không. Nếu điều này đúng thì không thể loại bỏ phần tử nào.
con trỏ được chỉ định các vị trí cụ thể để xác định vị trí phần tử cần xóa.
Các con trỏ được nâng cao, cái này nối tiếp cái kia. (trước đằng sau nhiệt độ)
Quá trình tiếp tục cho đến khi tìm thấy một phần tử hoặc phần tử tiếp theo quay trở lại con trỏ 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

Nếu phần tử được tìm thấy sau khi duyệt qua toàn bộ danh sách liên kết, một thông báo lỗi sẽ hiển thị cho biết không tìm thấy mục đó.
Nếu không, phần tử sẽ được hủy liên kết và giải phóng ở bước 3 và 4.
Con trỏ trước đó được liên kết với địa chỉ được chỉ định là “tiếp theo” bởi phần tử cần xóa (temp).
Do đó, con trỏ tạm thời được giải phóng và 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ã

Không thể xem nhanh hoặc truyền tải nếu không cần thiết. Người dùng cần phân bổ hoặc chèn một nút.
Nếu chỉ có một nút thì không cần duyệt qua, nội dung của nút có thể được in và vòng lặp while không thực thi.
Nếu có nhiều hơn một nút thì temp sẽ in tất cả mục cho đến phần tử cuối cùng.
Khi đến phần tử cuối cùng, vòng lặp kết thúc và hàm trả về lệnh gọi hàm chính.

Ứ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 kế hoạch vòng mã thông báo trong mạng máy tính.
Nó được sử dụng trong các đơn vị hiển thị như bảng cửa hàng yêu cầu truyền dữ liệu liên tục.

Bạn có thể thích:

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

Cơ bản Operacác mục trong danh sách liên kết vòng

chèn Operasản xuất

NHỮNG BÀI VIẾT LIÊN QUAN

xóa Operasản xuất

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

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

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

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

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