Danh sách liên kết đôi vòng C

Chào ace, bài này chúng ta sẽ tìm hiểu về Duyệt danh sách liên kết đơn dạng vòng Circular Linked List trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ) về nó thông qua các phần sau.

Trong bài trước, chúng ta đã tìm hiểu về danh sách liên kết vòng và ứng dụng của nó. Ở bài này, chúng ta sẽ thảo luận về việc duyệt danh sách liên kết vòng.

Trong danh sách liên kết bình thường, chúng ta sẽ duyệt qua danh sách này từ node đầu tiên là node head và dừng việc duyệt khi đi tới NULL. Trong một danh sách liên kết vòng, chúng ta sẽ dừng việc duyệt khi lại đi tới node đầu tiên một lần nữa. Đoạn code C dưới đây sẽ mô tả thao tác duyệt danh sách liên kết vòng, và in ra các nodes đã được duyệt tới.

Chúng ta cùng xem một chương trình hoàn chỉnh thể hiện việc duyệt nodes trong danh sách liên kết vòng:

ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG NHIỀU NGÔN NGỮ C++, C, Java, Python, C#

C

// C program to implement // the above approach #include #include /* structure for a node */ struct Node { int data; struct Node *next; }; /* Function to insert a node at the beginning of a Circular linked list */ void push(struct Node **head_ref, int data) { struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node)); struct Node *temp = *head_ref; ptr1->data = data; ptr1->next = *head_ref; /* If linked list is not NULL then set the next of last node */ if (*head_ref != NULL) { while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; /*For the first node */ *head_ref = ptr1; } /* Function to print nodes in a given Circular linked list */ void printList(struct Node *head) { struct Node *temp = head; if (head != NULL) { do { printf("%d ", temp->data); temp = temp->next; } while (temp != head); } } /* Driver program to test above functions */ int main() { /* Initialize lists as empty */ struct Node *head = NULL; /* Created linked list will be 11->2->56->12 */ push(&head, 12); push(&head, 56); push(&head, 2); push(&head, 11); printf("Contents of Circular Linked List\n "); printList(head); return 0; }

C++

// C++ program to implement // the above approach #include using namespace std; /* structure for a node */ class Node { public: int data; Node *next; }; /* Function to insert a node at the beginning of a Circular linked list */ void push(Node **head_ref, int data) { Node *ptr1 = new Node(); Node *temp = *head_ref; ptr1->data = data; ptr1->next = *head_ref; /* If linked list is not NULL then set the next of last node */ if (*head_ref != NULL) { while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; /*For the first node */ *head_ref = ptr1; } /* Function to print nodes in a given Circular linked list */ void printList(Node *head) { Node *temp = head; if (head != NULL) { do { cout << temp->data << " "; temp = temp->next; } while (temp != head); } } /* Driver program to test above functions */ int main() { /* Initialize lists as empty */ Node *head = NULL; /* Created linked list will be 11->2->56->12 */ push(&head, 12); push(&head, 56); push(&head, 2); push(&head, 11); cout << "Contents of Circular Linked List\n "; printList(head); return 0; }

Java

// Java program to implement // the above approach class GFG { // node static class Node { int data; Node next; }; /* Function to insert a node at the beginning of a Circular linked list */ static Node push(Node head_ref, int data) { Node ptr1 = new Node(); Node temp = head_ref; ptr1.data = data; ptr1.next = head_ref; /* If linked list is not null then set the next of last node */ if (head_ref != null) { while (temp.next != head_ref) temp = temp.next; temp.next = ptr1; } else ptr1.next = ptr1; head_ref = ptr1; return head_ref; } /* Function to print nodes in a given Circular linked list */ static void printList(Node head) { Node temp = head; if (head != null) { do { System.out.print(temp.data + " "); temp = temp.next; } while (temp != head); } } // Driver Code public static void main(String args[]) { /* Initialize lists as empty */ Node head = null; /* Created linked list will be 11.2.56.12 */ head = push(head, 12); head = push(head, 56); head = push(head, 2); head = push(head, 11); System.out.println("Contents of Circular " + "Linked List:"); printList(head); } }

Python

# Python program to demonstrate # circular linked list traversal # Structure for a Node class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.next = None class CircularLinkedList: # Constructor to create a empty circular linked list def __init__(self): self.head = None # Function to insert a node at the beginning of a # circular linked list def push(self, data): ptr1 = Node(data) temp = self.head ptr1.next = self.head # If linked list is not None then set the next of # last node if self.head is not None: while(temp.next != self.head): temp = temp.next temp.next = ptr1 else: ptr1.next = ptr1 # For the first node self.head = ptr1 # Function to print nodes in a given circular linked list def printList(self): temp = self.head if self.head is not None: while(True): print "%d" %(temp.data), temp = temp.next if (temp == self.head): break # Driver program to test above function # Initialize list as empty cllist = CircularLinkedList() # Created linked list will be 11->2->56->12 cllist.push(12) cllist.push(56) cllist.push(2) cllist.push(11) print "Contents of circular Linked List" cllist.printList()

C#

-->

// C# program to implement // the above approach using System; class GFG { // node class Node { public int data; public Node next; }; /* Function to insert a node at the beginning of a Circular linked list */ static Node push(Node head_ref, int data) { Node ptr1 = new Node(); Node temp = head_ref; ptr1.data = data; ptr1.next = head_ref; /* If linked list is not null then set the next of last node */ if (head_ref != null) { while (temp.next != head_ref) temp = temp.next; temp.next = ptr1; } else ptr1.next = ptr1; head_ref = ptr1; return head_ref; } /* Function to print nodes in a given Circular linked list */ static void printList(Node head) { Node temp = head; if (head != null) { do { Console.Write(temp.data + " "); temp = temp.next; } while (temp != head); } } // Driver Code static public void Main(String []args) { /* Initialize lists as empty */ Node head = null; /* Created linked list will be 11.2.56.12 */ head = push(head, 12); head = push(head, 56); head = push(head, 2); head = push(head, 11); Console.WriteLine("Contents of Circular " + "Linked List:"); printList(head); } }

Kết quả in ra là:

Contents of Circular Linked List 11 2 56 12

Nguồn và Tài liệu tiếng anh tham khảo:

• w3schools
• Geeksforgeeks
• codechef
• dev.to

Tài liệu từ cafedev:

• Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
• Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
• Các series tự học lập trình khác

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

• Group Facebook
• Fanpage
• Youtube
• Instagram
• Twitter
• Linkedin
• Pinterest
• Trang chủ

Chào thân ái và quyết thắng!

Đăng ký kênh youtube để ủng hộ nha các bạn, Thanks you!