Algorithms/circular linked lists

القوائم المترابطة الدائرية Circular Linked Lists هي قوائم مترابطة تكون فيها جميع العقد مرتبطة بعضها ببعض لتكون دائرة كاملة. لا تنتهي هذه القائمة بالقيمة 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); 
} 
}

إدراج العناصر في القوائم المترابطة الدائرية المفردة

لماذا نستخدم القوائم المترابطة الدائرية؟

تحتاج عملية الوصول إلى عقدة معينة في القوائم المترابطة المفردة التنقّل عبر عناصر القائمة المترابطة ابتدءًا من العقدة الأولى، وليس بالإمكان الوصول إلى أي عقدة سابقة للعقدة التي نقف عندها. ويمكن تجاوز هذه المشكلة بإجراء تعديل بسيط على بنية القائمة المترابطة المفردة، وذلك بتعديل العقدة التي تشير إليها العقدة الأخيرة في القائمة المترابطة وهي NULL لتصبح العقدة الأولى في القائمة نفسها.

ويمكن توضيح بنية القائمة المترابطة الدائرية المفردة بالصورة التالية:

ملف:https://media.geeksforgeeks.org/wp-content/uploads/CircularSinglyLinkedList.png

caption

إنشاء قائمة مترابطة دائرية مفردة

يمكن الاستعانة بمؤشر خارجي لإنشاء قائمة مترابطة دائرية مفردة، حيث يشير هذا المؤشر الخارجي إلى العقدة الأخيرة في القائمة، وبهذا يمكن القول بأنّه لو كان لدينا مؤشر يشير إلى العقدة الأخيرة في القائمة، فإنّ العقدة التالية لها last -> next ستكون العقدة الأولى في القائمة.

ملف:https://media.geeksforgeeks.org/wp-content/uploads/CircularSinglyLinkedList1.png

caption

يشير المؤشر last إلى العقدة Z ويشير last -> next إلى العقدة P.

إنّ الهدف من استخدام مؤشر خارجي يشير إلى العقدة الأخيرة عوضًا عن العقدة الأولى هو أنّه لغرض إدراج عقدة جديدة في بداية القائمة فإننا سنحتاج إلى التنقل عبر عقد القائمة كلّها، وكذلك الأمر عند إضافة عقدة جديدة في نهاية القائمة. ولكن إن أخذنا مؤشرًا إلى العقدة الأخيرة عوضًا عن مؤشر البداية start فلن تكون هناك حاجة إلى التنقل عبر القائمة بأكملها في كلتا الحالتين السابقتين، وبهذا ستستغرق عملية الإضافة في بداية القائمة أو نهايتها وقتًا ثابتًا لا علاقة له بطول القائمة.

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

يمكن إضافة العقدة بأربعة طرق:

• إدراج عقدة في قائمة فارغة.
• إدراج عقدة في بداية القائمة.
• إدراج عقدة في نهاية القائمة.
• إدراج عقدة بعد عقدة معينة.

إدراج عقدة في قائمة فارغة

يحمل المؤشر last القمة NULL عندما تكون القائمة فارغة.

fig: وبعد إدراج العقدة T: fig:

بعد إدراج العقدة T تصبح هي العقدة الأخيرة لذا سيشير المؤشر last إليها، وتكون العقدة T هي الأولى والأخيرة أي أنّها ستشير إلى نفسها.

يعرض المثال التالي دالة لإدراج عقدة في قائمة فارغة:

struct Node *addToEmpty(struct Node *last, int data) 
{ 
	// هذه الدالة للقوائم الفارغة فقط 
	if (last != NULL) 
	return last; 

	// إنشاء العقدة ديناميكياً
	struct Node *last = 
		(struct Node*)malloc(sizeof(struct Node)); 

	// إسناد البيانات
	last -> data = data; 

    // ملاحظة: القائمة كانت فارغة؛ لذا ربطنا العقدة المفردة بنفسها
	last -> next = last; 

	return last; 
}

إدراج عقدة في بداية القائمة

يمكن اتباع الخطوات التالية لإدراج عقدة في بداية القائمة:

1. إنشاء العقدة، لتكن T مثلًا.
2. جعل T -> next = last -> next.
3. last -> next = T. fig: بعد إدراج العقدة: fig:

يعرض المثال التالي دالة لإدراج عقدة في بداية القائمة:

struct Node *addBegin(struct Node *last, int data) 
{ 
if (last == NULL) 
	return addToEmpty(last, data); 

// إنشاء العقدة ديناميكياً 
struct Node *temp 
		= (struct Node *)malloc(sizeof(struct Node)); 
	
// إسناد البيانات 
temp -> data = data; 

// تعديل الروابط 
temp -> next = last -> next; 
last -> next = temp; 
	
return last; 
}

إدراج عقدة في نهاية القائمة

يمكن اتباع الخطوات التالية لإدراج عقدة في نهاية القائمة:

1. إنشاء العقدة، لتكن T مثلًا.
2. جعل T -> next = last -> next.
3. last -> next = T.
4. last = T.

ملف:https://media.geeksforgeeks.org/wp-content/uploads/CircularSinglyLinkedlist-6.png

caption

بعد إدراج العقدة:

ملف:https://media.geeksforgeeks.org/wp-content/uploads/CircularSinglyLinkedlist-7.png

caption

يعرض المثال التالي دالة لإدراج عقدة في نهاية القائمة:

struct Node *addEnd(struct Node *last, int data) 
{ 
if (last == NULL) 
	return addToEmpty(last, data); 

// إنشاء العقدة ديناميكياً 
struct Node *temp = 
		(struct Node *)malloc(sizeof(struct Node)); 
	
// إسناد البيانات. 
temp -> data = data; 

// تعديل الروابط 
temp -> next = last -> next; 
last -> next = temp; 
last = temp; 
	
return last; 
}

إدراج عقدة بعد عقدة معينة

يمكن اتباع الخطوات التالية لإدراج عقدة بين عقد القائمة المترابطة:

1. إنشاء العقدة، لتكن T مثلًا.
2. البحث عن العقدة التي ستسبق العقدة المراد إضافتها، ولتكن P مثلًا.
3. جعل T -> next = P -> next.
4. P -> next = T.

لنفترض أننا نرغب في إدراج عقدة تحمل القيمة 12 بعد عقدة تحمل القيمة 10: fig: بعد إجراء عملية البحث وإدراج العقدة: fig: يعرض المثال التالي دالة لإدراج عقدة بعد عقدة معينة:

struct Node *addAfter(struct Node *last, int data, int item) 
{ 
	if (last == NULL) 
	return NULL; 

	struct Node *temp, *p; 
	p = last -> next; 

	// البحث عن العنصر المطلوب 
	do
	{ 
		if (p ->data == item) 
		{ 
			// إنشاء عقدة ديناميكيًا
			temp = (struct Node *)malloc(sizeof(struct Node)); 

			// إسناد البيانات 
			temp -> data = data; 

			// تعديل الروابط 
			temp -> next = p -> next; 

			// p إدراج العقدة الجديدة بعد العقدة 
			p -> next = temp; 

			// التحقق من العقدة الأخيرة
			if (p == last) 
				last = temp; 

			return last; 
		} 
		p = p -> next; 
	} while (p != last -> next); 

	cout << item << " not present in the list." << endl; 
	return last; 
}

أمثلة برمجية

تعرض الأمثلة التالية طريقة إدراج عقدة في قائمة مترابطة دائرية في عدد من لغات البرمجة:

• C++:

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

struct Node 
{ 
	int data; 
	struct Node *next; 
}; 

struct Node *addToEmpty(struct Node *last, int data) 
{ 
	// تعمل هذه الدالة على القائمة الفارغة فقط
    if (last != NULL) 
	return last; 

	// إنشاء العقدة ديناميكيًا 
	struct Node *temp = 
		(struct Node*)malloc(sizeof(struct Node)); 

	// إسناد البيانات 
	temp -> data = data; 
	last = temp; 

	// إنشاء الرابطة 
	last -> next = last; 

	return last; 
} 

struct Node *addBegin(struct Node *last, int data) 
{ 
	if (last == NULL) 
		return addToEmpty(last, data); 

	struct Node *temp = 
			(struct Node *)malloc(sizeof(struct Node)); 

	temp -> data = data; 
	temp -> next = last -> next; 
	last -> next = temp; 

	return last; 
} 

struct Node *addEnd(struct Node *last, int data) 
{ 
	if (last == NULL) 
		return addToEmpty(last, data); 
	
	struct Node *temp = 
		(struct Node *)malloc(sizeof(struct Node)); 

	temp -> data = data; 
	temp -> next = last -> next; 
	last -> next = temp; 
	last = temp; 

	return last; 
} 

struct Node *addAfter(struct Node *last, int data, int item) 
{ 
	if (last == NULL) 
		return NULL; 

	struct Node *temp, *p; 
	p = last -> next; 
	do
	{ 
		if (p ->data == item) 
		{ 
			temp = (struct Node *)malloc(sizeof(struct Node)); 
			temp -> data = data; 
			temp -> next = p -> next; 
			p -> next = temp; 

			if (p == last) 
				last = temp; 
			return last; 
		} 
		p = p -> next; 
	} while(p != last -> next); 

	cout << item << " not present in the list." << endl; 
	return last; 

} 

void traverse(struct Node *last) 
{ 
	struct Node *p; 

	// إيقاف عمل الدالة إن كانت القائمة فارغة 
	if (last == NULL) 
	{ 
		cout << "List is empty." << endl; 
		return; 
	} 

	// الإشارة إلى أول عقدة في القائمة 
	p = last -> next; 

	// التنقل عبر عناصر القائمة 
	do
	{ 
		cout << p -> data << " "; 
		p = p -> next; 

	} 
	while(p != last->next); 

} 

// اختبار الدوال السابقة 
int main() 
{ 
	struct Node *last = NULL; 

	last = addToEmpty(last, 6); 
	last = addBegin(last, 4); 
	last = addBegin(last, 2); 
	last = addEnd(last, 8); 
	last = addEnd(last, 12); 
	last = addAfter(last, 10, 8); 

	traverse(last); 

	return 0; 
}

• جافا:

class GFG 
{ 

static class Node 
{ 
	int data; 
	Node next; 
}; 

static Node addToEmpty(Node last, int data) 
{ 
	// تعمل هذه الدالة على القائمة الفارغة فقط
	if (last != null) 
	return last; 

	// إنشاء العقد ديناميكيًا 
	Node temp = new Node(); 

	// إسناد البيانات
	temp.data = data; 
	last = temp; 

	// إنشاء الرابطة
	last.next = last; 

	return last; 
} 

static Node addBegin(Node last, int data) 
{ 
	if (last == null) 
		return addToEmpty(last, data); 

	Node temp = new Node(); 

	temp.data = data; 
	temp.next = last.next; 
	last.next = temp; 

	return last; 
} 

static Node addEnd(Node last, int data) 
{ 
	if (last == null) 
		return addToEmpty(last, data); 
	
	Node temp = new Node(); 

	temp.data = data; 
	temp.next = last.next; 
	last.next = temp; 
	last = temp; 

	return last; 
} 

static Node addAfter(Node last, int data, int item) 
{ 
	if (last == null) 
		return null; 

	Node temp, p; 
	p = last.next; 
	do
	{ 
		if (p.data == item) 
		{ 
			temp = new Node(); 
			temp.data = data; 
			temp.next = p.next; 
			p.next = temp; 

			if (p == last) 
				last = temp; 
			return last; 
		} 
		p = p.next; 
	} while(p != last.next); 

	System.out.println(item + " not present in the list."); 
	return last; 

} 

static void traverse(Node last) 
{ 
	Node p; 

	// إنهاء عمل الدالة إن كانت القائمة فارغة
	if (last == null) 
	{ 
		System.out.println("List is empty."); 
		return; 
	} 

	// الإشارة إلى أول عقدة في القائمة 
	p = last.next; 

	// التنقل عبر عناصر القائمة
	do
	{ 
		System.out.print(p.data + " "); 
		p = p.next; 

	} 
	while(p != last.next); 

} 

// اختبار الدوال السابقة 
public static void main(String[] args) 
{ 
	Node last = null; 

	last = addToEmpty(last, 6); 
	last = addBegin(last, 4); 
	last = addBegin(last, 2); 
	last = addEnd(last, 8); 
	last = addEnd(last, 12); 
	last = addAfter(last, 10, 8); 

	traverse(last); 
} 
}

مصادر

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