Danh sách liên kết vòng [Circular Linked List] là gì?
Danh sách liên kết vòng [Circular Linked List] là một biến thể của Danh sách liên kết [Linked List], trong đó phần tử đầu tiên trỏ tới phần tử cuối cùng và phần tử cuối cùng trỏ tới phần tử đầu tiên.
Cả hai loại Danh sách liên kết đơn [Singly Linked List] và Danh sách liên kết đôi [Doubly Linked List] đều có thể được tạo thành dạng Danh sách liên kết vòng. Phần dưới chúng ta sẽ tìm hiểu từng cách tạo một.
Tạo Danh sách liên kết vòng từ Danh sách liên kết đơn
Trong Danh sách liên kết đơn, điểm trỏ tới kế tiếp của nút cuối sẽ trỏ tới nút đầu tiên, thay vì sẽ trỏ tới NULL.
Tạo Danh sách liên kết vòng từ Danh sách liên kết đôi
Trong Danh sách liên kết đôi, điểm trỏ tới kế tiếp của nút cuối trỏ tới nút đầu tiên và điểm trỏ tới phía trước của nút trước sẽ trỏ tới nút cuối cùng. Quá trình này sẽ tạo thành vòng ở cả hai hướng.
Nhìn vào hai hình minh họa trên, bạn cần ghi nhớ:
Next của Last Link trỏ tới First Link trong cả hai trường hợp với Danh sách liên kết đơn cũng như Danh sách liên kết đôi.
Prev của First Link trỏ tới phần tử cuối của Danh sách liên kết với trường hợp Danh sách liên kết đôi.
Các hoạt động cơ bản trên Danh sách liên kết vòng
Dưới đây là một số hoạt động cơ bản được hỗ trợ bởi Danh sách liên kết vòng:
Hoạt động chèn: chèn một phần tử vào vị trí bắt đầu của Danh sách liên kết vòng.
Hoạt động xóa: xóa một phần tử của Danh sách liên kết vòng.
Hiển thị: hiển thị toàn bộ Danh sách liên kết vòng.
Hoạt động chèn trong Danh sách liên kết vòng
Dưới đây là giải thuật minh họa hoạt động chèn trong Danh sách liên kết vòng dựa trên Danh sách liên kết đơn.
//Chèn link tại vị trí đầu tiên void insertFirst[int key, int data] { //tạo một link struct node *link = [struct node*] malloc[sizeof[struct node]]; link->key = key; link->data= data; if [isEmpty[]] { head = link; head->next = head; }else { //trỏ nó tới first node cũ link->next = head; //trỏ first tới first node mới head = link; } }Để theo dõi phần triển khai code minh họa chi tiết trong ngôn ngữ C, bạn vào chương: Chương trình Danh sách liên kết vòng trong C.
Hoạt động xóa trong Danh sách liên kết vòng
Dưới đây là giải thuật minh họa hoạt động xóa trong Danh sách liên kết vòng dựa trên Danh sách liên kết đơn.
//Xóa phần tử đầu tiên struct node * deleteFirst[] { //Lưu tham chiếu tới first link struct node *tempLink = head; if[head->next == head]{ head = NULL; return tempLink; } //Đánh dấu next tới first link là first head = head->next; //trả về link đã bị xóa return tempLink; }Để theo dõi phần triển khai code minh họa chi tiết trong ngôn ngữ C, bạn vào chương: Chương trình Danh sách liên kết vòng trong C.
Hiển thị Danh sách liên kết vòng
Dưới đây là giải thuật minh họa hoạt động hiển thị toàn bộ Danh sách liên kết vòng.
//Hiển thị danh sách liên kết vòng void printList[] { struct node *ptr = head; printf["\n[ "]; //Bắt đầu từ vị trí đầu tiên if[head != NULL] { while[ptr->next != ptr] { printf["[%d,%d] ",ptr->key,ptr->data]; ptr = ptr->next; } } printf[" ]"]; }Để theo dõi phần triển khai code minh họa chi tiết trong ngôn ngữ C, bạn vào chương: Chương trình Danh sách liên kết vòng trong C.
Theo Tutorialspoint
Bài trước: Cấu trúc dữ liệu danh sách liên kết [Linked List]
Bài tiếp: Cấu trúc dữ liệu ngăn xếp [Stack]
void Saochep[List &s,ListB &b] { Sinhvien *data; data=s.dau; Copy *t= new Copy[1]; for[data=s.dau;data!=NULL;data=data->tiep] { if[data->Diem>5] { strcpy[t->Ten,data->Ten]; t->Diem=data->Diem; t->Mssv=data->Mssv; ChencuoiB[b,t]; } } coutnext = node;
l.tail = node;
}
}
Thêm vào điểm bất kỳ
Gọi p là node cần thêm, còn q là node đằng trước vị trí cần thêm. Đầu tiên, ta sẽ kiểm tra xem node q có gán với NULL hay không. Nếu có gán tức là danh sách rỗng. Khi đó chỉ cần gán p lên đầu là được. Nếu không, người dùng sẽ thực hiện theo các bước sau: trỏ p->next = q->next, sau đó q->next = p. Khi hoàn thành, phải kiểm tra tiếp q có phải nốt cuối hay không. Nếu phải thì cần tiếp tục gán p vài tail.
void InsertAfterQ[LinkedList& l, Node* p, Node* q]
{
if [q != NULL]
{
p->next = q->next;
q->next = p;
Xóa phần tử khỏi danh sách liên kết đơn
Xóa ở đầu
Đầu tiên, ta tiến hành kiểm tra xem danh sách đó có rỗng không. Nếu có thì trực tiếp xóa đi và để giá trị bằng 0 là được. Còn nếu danh sách không rỗng thì thực hiện theo những bước sau. Đầu tiên là gán lại head vào vị trí đằng sau phần tử cần xóa, nhớ phải lưu head lại. Sau đó mới tiến hành xóa.
int RemoveHead[LinkedList& l, int& x]
{
if [l.head != NULL]
{
Node* node = l.head;
x = node->data; // Lưu giá trị của node head lại
l.head = node->next;
delete node; // Hủy node head đi
if [l.head == NULL]
l.tail = NULL;
return 1;
}
return 0;
}
Xóa ở điểm bất kỳ
Cách xóa một node
Nếu cần xóa node p sau một node q bất kỳ, ta sẽ có 3 trường hợp cần xét:
- Nếu q là NULL suy ra danh sách rỗng, không cần xóa mà chỉ cần chỉnh về 0
- Nếu next của q là NULL, chứng tỏ p là NULL, suy ra p không tồn tại để xóa
- Nếu p có tồn tại, kiểm tra xem p có phải tail không, nếu có thì chỉ cần gán tail lại vào q là được.
int RemoveAfterQ[LinkedList& l, Node* q, int& x]
{
if [q != NULL]
{
Node* p = q->next;
if [p != NULL]
{
if [l.tail == p]
l.tail = q;
q->next = p->next;
x = p->data;
delete p;
return 1;
}
return 0;
}
return 0;
}
Duyệt danh sách liên kết đơn và in
Để kiểm tra xem danh sách đã hoàn chỉnh hay chưa, ta sẽ gán một node bằng head. Sau đó kiểm tra xem node đó NULL hay không. Nếu đã đạt tức là ta đã có dữ liệu của node này. Tiếp tục thực hiện thao tác đó cho đến node NULL, đó chính tail của danh sách.
Mời bạn đọc tham khảo thêm: SQL là gì?
Vậy trong bài viết vừa rồi, Teky đã giúp bạn tìm hiểu thêm về các đặc điểm của danh sách liên kết đơn cũng như cách tạo một danh sách hoàn chỉnh. Mong rằng những kiến thức này sẽ giúp ích cho quá trình học tập và làm việc của bạn.