القوائم المترابط الدائرية

القوائم المترابطة الدائرية هي قوائم مترابطة تكون فيها جميع العقد مرتبطة بعضها ببعض لتكون دائرة كاملة. لا تنتهي هذه القائمة بالقيمة Null، ويمكن أن تكون القائمة المترابطة الدائرية مفردة أو مزدوجة.

مزايا القوائم المترابطة الدائرية

1. يمكن لأي عقدة أن تكون نقطة بداية، ويمكن المرور على عناصر القائمة كلها ابتداءً من أي نقطة فيها، وكل ما نحتاج إليه هو التوقف عند الوصول مرة أخرى إلى العقدة التي بدأنا منها.
2. يمكن الاستفادة من هذا النوع من القوائم عند التعامل مع الطوابير queues؛ إذ لا حاجة لوجود مؤشرين قبل وبعد كل عقدة عند استخدام القوائم المترابطة الدائرية، بل يكفي وجود مؤشر لآخر عقدة مدرجة، ويمكن الحصول على المؤشر الأمامي من العقدة التي تلي العقدة الأخيرة.
3. يمكن الاستفادة من القوائم المترابطة الدائرية في التطبيقات وذلك للتحرك ضمن القائمة بصورة متكررة. فمثلًا عند تشغيل عدد من التطبيقات على الحاسوب، فإنّ من الشائع أن يضع نظام التشغيل التطبيقات المفتوحة في قائمة ثم يبدأ بالتنقل بين هذه التطبيقات ليمنح كل واحد منها جزءًا من الوقت للتنفيذ، ثم يجعل هذه التطبيق في وضع الانتظار أثناء انتقال المعالج إلى التطبيق الآخر. إن استخدام القوائم المترابطة الدائرية ملائم جدًّا لأنظمة التشغيل إذ يمكن الرجوع إلى بداية القائمة بعد الوصول إلى نهايتها.
4. يمكن الاستفادة من القوائم المترابطة الدائرية المزدوجة في تطبيقات متقدمة لبنى المعطيات مثل كومة فابيوناتشي.

التنقل عبر عناصر القائمة المترابطة الدائرية

يجري التنقل بين عناصر القائمة المترابطة العادية ابتداءً من العقدة الرأس وصولًا إلى القيمة Null. أما في القوائم المترابطة الدائرية، فإنّنا نتوقف عند وصولنا إلى العقدة التي بدأنا منها. يعرض المثال التالي طريقة التنقل بين عناصر القائمة المترابطة الدائرية باستخدام اللغة C:

/*دالة للتنقل عبر عناصر قائمة مترابطة دائرية وطباعة عقدها*/
void printList(struct Node *first) 
{ 
    struct Node *temp = first;  
  
    // التحقق من أن القائمة المترابطة غير فارغة
    if (first != NULL)  
    { 
        // الاستمرار في طباعة العقد إلى حين الوصول إلى العقدة الأولى 
        do
        { 
            printf("%d ", temp->data); 
            temp = temp->next; 
        } 
        while (temp != first); 
    } 
}

يعرض المثال التالي طريقة التنقل بين عناصر القائمة المترابطة الدائرية باستخدام اللغة ++C:

#include <bits/stdc++.h> 
using namespace std; 

/* بنية العقدة */
class Node 
{ 
	public: 
	int data; 
	Node *next; 
}; 

/* دالة لإدراج عقدة في بداية القائمة المترابطة الدائرية */
void push(Node **head_ref, int data) 
{ 
	Node *ptr1 = new Node(); 
	Node *temp = *head_ref; 
	ptr1->data = data; 
	ptr1->next = *head_ref; 

	/* إن لم نصل إلى القيمة NULL فسنعين العقدة اللاحقة للعقدة الأخيرة */
    if (*head_ref != NULL) 
	{ 
		while (temp->next != *head_ref) 
			temp = temp->next; 
		temp->next = ptr1; 
	} 
	else
		ptr1->next = ptr1; /*للعقدة الأولى */

	*head_ref = ptr1; 
} 

/* دالة لطباعة العقد في قائمة مترابطة دائرية */

void printList(Node *head) 
{ 
	Node *temp = head; 
	if (head != NULL) 
	{ 
		do
		{ 
			cout << temp->data << " "; 
			temp = temp->next; 
		} 
		while (temp != head); 
	} 
} 

/* دالة تختبر الدوال السابقة */
int main() 
{ 
	/* تهيئة قوائم فارغة */
	Node *head = NULL; 

	/* القائمة التي ستنشأ ستكون بالترتيب 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; 
}

بايثون:

# إنشاء بنية العقدة
class Node: 
      
    # دالة بانية لإنشاء عقد جديدة 
    def __init__(self, data): 
        self.data = data  
        self.next = None
  
class CircularLinkedList: 
      
    # دالة بانية لإنشاء قائمة مترابطة دائرية فارغة 
    def __init__(self): 
        self.head = None
  
    # دالة لإدراج عقدة جديدة في بداية
    # القائمة الدائرية المترابطة
    def push(self, data): 
        ptr1 = Node(data) 
        temp = self.head 
          
        ptr1.next = self.head 
  		# إن لم نصل إلى القيمة None فسنعين العقدة اللاحقة للعقدة الأخيرة
        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  
  
    # دالة لطباعة العقد في قائمة مترابطة دائرية
    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 
  
  
# اختبار الدوال السابقة 
  
# تهيئة قائمة فارغة
cllist = CircularLinkedList() 
  
# ستنشأ قائمة مترابطة دائرية تضم العناصر 11->2->56->12 
cllist.push(12) 
cllist.push(56) 
cllist.push(2) 
cllist.push(11) 
  
print "Contents of circular Linked List"
cllist.printList()

جافا:

class GFG 
{ 
  
// إنشاء عقدة  
static class Node 
{ 
    int data; 
    Node next; 
}; 

/* دالة لإدراج عقدة جديدة في بداية القائمة الدائرية المترابطة */

static Node push(Node head_ref,  
                 int data) 
{ 
    Node ptr1 = new Node(); 
    Node temp = head_ref; 
    ptr1.data = data; 
    ptr1.next = head_ref; 
  
    	/* إن لم نصل إلى القيمة null فسنعين العقدة اللاحقة للعقدة الأخيرة */
    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; 
} 
  
/* دالة لطباعة العقد في قائمة مترابطة دائرية */

static void printList(Node head) 
{ 
    Node temp = head; 
    if (head != null) 
    { 
        do
        { 
            System.out.print(temp.data + " "); 
            temp = temp.next; 
        } 
        while (temp != head); 
    } 
} 
  
// اختبار الدوال السابقة
public static void main(String args[]) 
{ 
    /* تهيئة قائمة فارغة */
    Node head = null; 
  
    /* ستضم القائمة المترابطة العناصر 
       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); 
} 
}

مصادر

• صفحة Circular Linked List Introduction and Applications في توثيق بنى المعطيات في موقع GeeksforGeeks.