Danh sách liên kết vòng (Circular Linked List)

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<stdio.h> 
#include<stdlib.h> 
  
/* 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 <bits/stdc++.h> 
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

Related Posts

So sánh ngôn ngữ C++ và Java

Có nhiều điểm khác biệt và tương đồng giữa ngôn ngữ lập trình C++ và Java . Dưới đây là danh sách những điểm khác Read more

Con trỏ trong C/C++

Con trỏ là một trong những tính năng quan trọng của mỗi ngôn ngữ lập trình. Thực tế, để được Read more

Single Linked List C++ (Danh sách liên kết đơn).

Danh sách liên kết đơn là gì? Danh sách đơn liên kết (Danh sách liên kết đơn) là một dữ Read more

Con trỏ và cấp phát động trong C++

Con trỏ và cấp phát động trong C++ Con trỏ (pointer) là một khái niệm quan trọng và khó nhất Read more