Danh sách liên kết vòng và một số thao tác

Chúng ta cùng tìm hiểu một cấu trúc dữ liệu cũng khá hữu ích là Danh sách liên kết vòng (Circular Linked List). Nó biểu diễn một cách tự nhiên các cấu trúc dạng tròn như các góc của đa giác, v.v... DSLK vòng có hai dạng thường thấy là dạng vòng đơn và vòng kép.

Dạng vòng đơn thực chất là một danh sách liên kết đơn có phần tử cuối trỏ về phần tử đầu tiên. Nó cũng có nhược điểm là chỉ duyệt từ một chiều. Dạng vòng kép cũng là một danh sách liên kết kép có phần tử cuối trỏ về đầu và đầu trỏ ngược về cuối.

Với DSLK vòng ta cần biết một vài thao tác cơ bản đủ dùng và các thao tác này sẽ được minh họa bằng C++. Bài này chỉ nói về danh sách liên kết vòng kép và bạn cũng nên sử dụng vòng kép để việc code lại đơn giản hơn.

Tổ chức dữ liệu
Một danh sách gồm có các phần tử gọi là node, mỗi node gồm 1 biến chứa dữ liệu và một hoặc nhiều biến con trỏ để liên kết với các node khác. Dưới đây là khai báo cấu trúc node:

struct DoublyNode
{
   <datatype> info;
   DoublyNode* prev, *next;
};

Do cấu trúc này ở dạng vòng nên một danh sách ta chỉ cần chọn một phần tử đầu thôi.

struct DoublyList
{
   DoublyNode* head;
};

Danh sách liên kết kép và các thao tác cơ bản

Nếu bạn đã đọc bài viết về Danh sách liên kết đơn thì có thể thấy việc tổ chức dạng danh sách tiện lợi hơn rất nhiều so với dùng mảng. Tuy nhiên, danh sách liên kết đơn vẫn có nhược điểm là chỉ có thể duyệt từ đầu đến cuối. Vì vậy, một số thao tác sẽ rất khó cài đặt trên nó. Danh sách liên kết kép có thể khắc phục nhược điểm này. Hầu hết các thao tác điều giống với danh sách liên kết đơn nhưng mình cũng khuyên các bạn nên đọc bài: Danh sách liên kết đơn và các thao tác cơ bản trước khi đọc bài viết này. Các thao tác được minh họa bằng C++.

Tổ chức dữ liệu
Với danh sách liên kết kép, mỗi phần tử sẽ liên kết với phần tử đứng trước và sau nó trong danh sách.
Mỗi phần tử trong danh sách (node) gồm biến lưu dữ liệu và 2 con trỏ liên kết tới phần tử trước và sau nó.

Khai báo phần tử của danh sách:

struct Node
{
   <datatype> info;
   Node  *prev, *next;
};

Một danh sách thì gồm nhiều phần tử, các phần tử đã liên kết nhau, mà đây là cấu trúc dữ liệu động nên ta cần biết phần tử đầu và phần tử cuối của danh sách.

Khai báo cấu trúc danh sách:

struct List
{
   Node *head, *tail;
}

Có thể minh họa danh sách liên kết kép như sau:

Các thao tác cơ bản
Tạo danh sách rỗng
Khi bạn tạo một biến kiểu List như trên thì 2 con trỏ thành viên được tạo ra, tuy nhiên chúng chưa được khởi tạo giá trị. Thao tác với con trỏ rỗng thì nguy hiểm nên cần thiết phải gán NULL cho 2 con trỏ này.

void CreateList(List &list)
{
   list.head = list.tail = NULL;
}

Danh sách liên kết đơn và các thao tác cơ bản

Danh sách liên kết là một cấu trúc dữ liệu mà mỗi phần tử cần phải lưu thông tin của nó và địa chỉ của phần tử kế tiếp hoặc trước nó. Danh sách liên kết linh động hơn mảng rất nhiều do có thể thêm, xóa phần tử. Có nhiều dạng danh sách liên kết khác nhau và ở phần này mình sẽ nói về danh sách liên kết đơn cùng các thao tác với nó (minh họa bằng C++).

Tổ chức dữ liệu
Mỗi phần tử trong DSLK đơn (gọi là node hay nút) sẽ gồm một biến lưu dữ liệu của bạn và một biến con trỏ lưu địa chỉ của phần tử kế tiếp. Các phần tử được liên kết với nhau dựa vào con trỏ này.

struct Node
{
   <kiểu dữ liệu> info;
   Node *next;
};

Như vậy, khi biết được phần tử đầu danh sách thì dựa vào con trỏ next, ta có thể truy cập được tất cả các phần tử trong danh sách. Vậy một danh sách chỉ gồm 1 con trỏ trỏ đến phần tử đầu danh sách. Tuy nhiên, để một vài thao tác trở nên dễ dàng, ta có thể thêm một con trỏ đến cuối danh sách.

struct List
{
   Node *head, *tail;
};

Nếu chưa hiểu cấu trúc của nó, bạn có thể xem hình minh họa sau.

Các thao tác cơ bản
Tạo danh sách rỗng
Tại sao đây lại là một thao tác quan trọng. Một danh sách được tạo ra chứa 2 con trỏ rỗng chưa trỏ đến đâu cả. Vì vậy sẽ rất nguy hiểm nếu thao tác với 2 con trỏ này. Cần thiết phải gán cho nó giá trị NULL trước khi thao tác trên nó. Nếu bạn cài đặt danh sách theo phương pháp hướng đối tượng thì có thể khai báo phần này trong constructor nên không cần gọi hàm này bên ngoài.

void CreateList(List &list)
{
   list.head = list.tail = NULL;
}