Algorithms/doubly linked lists

تحتوي القوائم المترابطة المزدوجة Doubly Linked List على مؤشر إضافي -عادة ما يسمّى بالمؤشر السابق Previous- إلى جانب المؤشر اللاحق Next والبيانات الموجودة في القوائم المترابطة المفردة.

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

• C:

struct Node { 
	int data; 
	struct Node* next; // Pointer to next node in DLL 
	struct Node* prev; // Pointer to previous node in DLL 
};

• بايثون:

class Node: 
	def __init__(self, next=None, prev=None, data=None): 
		self.next = next # إشارة إلى العقدة التالية
		self.prev = prev # إشارة إلى العقدة السابقة
		self.data = data

• جافا:

public class DLL { 
	Node head; // رأس القائمة المترابطة 

	/* عقدة في القائمة المترابطة المزدوجة*/
	class Node { 
		int data; 
		Node prev; 
		Node next; 

		// دالة بانية لإنشاء عقدة جديدة
		// تأخذ الإشارتان اللاحقة والسابقة القيمة null كقيمة افتراضية
		Node(int d) { data = d; } 
	} 
}

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

تمتاز القوائم المترابطة المزدوجة مقارنة بالمفردة بما يلي:

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

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

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

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

يمكن إضافة العناصر إلى القوائم المترابطة المزدوجة بأربعة طرق:

1. في بداية القائمة المترابطة المزدوجة.
2. بعد عقدة معينة.
3. في نهاية القائمة المترابطة المزدوجة.
4. قبل عقدة معينة.

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

تضاف العقدة الجديدة دائمًا قبل رأس القائمة المترابطة، وتصبح العقدة المضافة رأسًا لتلك القائمة.

يجب أن تستقبل الدالة التي ستضيف العقدة مؤشرًا إلى مؤشر الرأس، وذلك لأن على الدالة أن تغير مؤشر الرأس ليشير إلى العقدة الجديدة.

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

/* تدرج الدالة عقدة جديدة في بداية القائمة باستخدام إشارة (مؤشر إلى مؤشر) إلى
رأس القائمة وعدد صحيح */
void push(struct Node** head_ref, int new_data) 
{ 
	/* 1. حجز مكان للعقدة في الذاكرة */
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

	/* 2. إضافة البيانات */
	new_node->data = new_data; 

	/* 3. NULL جعل رأس القائمة يلي العقدة الجديدة وجعل القيمة السابقة لها هي */
	new_node->next = (*head_ref); 
	new_node->prev = NULL; 

	/* 4. جعل العقدة الجديدة تسبق رأس القائمة */
	if ((*head_ref) != NULL) 
		(*head_ref)->prev = new_node; 

	/* 5. تحريك رأس القائمة ليشير إلى العقدة الجديدة */
	(*head_ref) = new_node; 
}

إضافة عقدة بعد عقدة معينة

نمتلك في هذه الحالة مؤشرًا إلى العقدة السابقة إلى جانب عقدة جديدة ستُضاف بعد العقدة المعطاة.

/* Given a node as prev_node, insert a new node after the given node */
void insertAfter(struct Node* prev_node, int new_data) 
{ 
	/*1. check if the given prev_node is NULL */
	if (prev_node == NULL) { 
		printf("the given previous node cannot be NULL"); 
		return; 
	} 

	/* 2. allocate new node */
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

	/* 3. put in the data */
	new_node->data = new_data; 

	/* 4. Make next of new node as next of prev_node */
	new_node->next = prev_node->next; 

	/* 5. Make the next of prev_node as new_node */
	prev_node->next = new_node; 

	/* 6. Make prev_node as previous of new_node */
	new_node->prev = prev_node; 

	/* 7. Change previous of new_node's next node */
	if (new_node->next != NULL) 
		new_node->next->prev = new_node; 
}

إضافة عقدة إلى نهاية القائمة المترابطة

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

/* Given a reference (pointer to pointer) to the head 
of a DLL and an int, appends a new node at the end */
void append(struct Node** head_ref, int new_data) 
{ 
	/* 1. allocate node */
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

	struct Node* last = *head_ref; /* used in step 5*/

	/* 2. put in the data */
	new_node->data = new_data; 

	/* 3. This new node is going to be the last node, so 
		make next of it as NULL*/
	new_node->next = NULL; 

	/* 4. If the Linked List is empty, then make the new 
		node as head */
	if (*head_ref == NULL) { 
		new_node->prev = NULL; 
		*head_ref = new_node; 
		return; 
	} 

	/* 5. Else traverse till the last node */
	while (last->next != NULL) 
		last = last->next; 

	/* 6. Change the next of last node */
	last->next = new_node; 

	/* 7. Make last node as previous of new node */
	new_node->prev = last; 

	return; 
}

إضافة عقدة قبل عقدة معيّنة

لنفترض أنّ المؤشر إلى العقدة المعيّنة هو next_node وأنّ البيانات الخاصة بالعقدة الجديدة المراد إضافتها هو new_data.

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

1. التحقق ممّا إذا كانت قيمة next_node تساوي Null، فإن كانت كذلك نوقف عمل الدالة وذلك لأنّه لا يمكن إضافة عقدة جديدة قبل Null.
2. نحجز الذاكرة المطلوبة للعقدة الجديدة، ونسمّيها new_node.
3. نسند البيانات إلى العقدة الجديدة new_node->data = new_data.
4. نعين العقدة السابقة للعقدة الجديدة new_node لتكون العقدة السابقة للعقدة التالية next_node كما يلي: new_node->prev = next_node->prev.
5. نعين المؤشر السابق للعقدة next_node ليكون new_node وكما يلي: next_node->prev = new_node.
6. نعين المؤشر اللاحق للعقدة new_noe ليكون next_node وكما يلي: new_node->next = next_node.
7. إن لم تكن العقدة السابقة للعقدة new_node موجودة (أي أنّها ليست Null) فنعين المؤشر اللاحق لهذه العقدة السابقة لتصبح new_node، وكما يلي: new_node->prev->next = new_node.
8. أما إن كانت العقدة السابقة للعقدة new_node هي Null، فإنّها ستكون العقدة الرأسية الجديدة: ‎(*head_ref) = new_node.

حذف عقدة من قائمة مترابطة مزدوجة

لو افترضنا أنّ العقدة المراد حذفها هي del فإنّ عملية حذف العقدة تتبع الخوارزمية التالية:

1. إن كانت العقدة المراد حذفها هي عقدة الرأس، فيجب تحويل مؤشر الرأس إلى العقدة التالية.
2. تعيين العقدة التي تلي العقدة السابقة للعقدة المحذوفة، إن كانت هناك عقدة سابقة.
3. تعيين العقدة السابقة للعقدة التي تلي العقدة المحذوفة، إن كانت هناك عقدة تالية.

إن مقدار تعقيد الوقت لهذه الخوارزمية هو O(1)‎.

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

ما نحتاجه لقلب عناصر قائمة مترابطة مزدوجة هو تبديل المؤشرات السابقة واللاحقة لكل عقدة، وتغيير ما يسبق عقدة الرأس وتغيير مؤشر الرأس في نهاية القائمة.

إن مقدار تعقيد الوقت لهذه الخوارزمية هو O(n)‎.

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

مصادر

• https://www.geeksforgeeks.org/doubly-linked-list/
• https://www.geeksforgeeks.org/delete-a-node-in-a-doubly-linked-list/
• https://www.geeksforgeeks.org/reverse-a-doubly-linked-list/