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

تحتوي القوائم المترابطة المزدوجة 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; 
}

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

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

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

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

أمثلة

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

• C++‎:

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

// عقدة في قائمة مترابطة
class Node 
{ 
	public: 
	int data; 
	Node* next; 
	Node* prev; 
}; 


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

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

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

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

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

/* تدرج الدالة عقدة جديدة بعد عقدة معينة معطاة */
void insertAfter(Node* prev_node, int new_data) 
{ 
	/*1. null التحقق من أن العقدة المعطاة هي */
	if (prev_node == NULL) 
	{ 
		cout<<"the given previous node cannot be NULL"; 
		return; 
	} 

	/* 2. حجز موقع العقدة الجديدة في الذاكرة */
	Node* new_node = new Node(); 

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

	/* 4. جعل ما يلي العقدة الجديدة هو ما يلي العقدة السابقة */
	new_node->next = prev_node->next; 

	/* 5. جعل العقدة الجديدة تلي العقدة السابقة */
	prev_node->next = new_node; 

	/* 6. جعل العقدة السابقة تسبق العقدة الجديدة */
	new_node->prev = prev_node; 

	/* 7. تغيير ما يسبق العقدة التي تلي العقدة الجديدة */
	if (new_node->next != NULL) 
		new_node->next->prev = new_node; 
} 

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

	Node* last = *head_ref; /* يستخدم في الخطوة 5*/

	/* 2. إضافة البيانات */
	new_node->data = new_data; 
	/* 3. NULL ستكون هذه العقدة هي العقدة الأخيرة لذا سنجعل ما يليها هو */
	new_node->next = NULL; 

	
	/* 4. نجعل العقدة الجديدة رأسًا للقائمة إن كانت القائمة فارغة */
	if (*head_ref == NULL) 
	{ 
		new_node->prev = NULL; 
		*head_ref = new_node; 
		return; 
	} 

	/* 5. وإلا سننتقل عبر عناصر القائمة إلى نهايتها  */
	while (last->next != NULL) 
		last = last->next; 

	/* 6. العقدة الجديدة تتلو العقدة الأخيرة في القائمة */
	last->next = new_node; 

	/* 7. العقدة الأخيرة في القائمة هي التي تسبق العقدة الجديدة */
	new_node->prev = last; 

	return; 
} 

// تطبع هذه الدالة محتويات القائمة المترابطة المزدوجة بدءًا من العقدة المعطاة 
void printList(Node* node) 
{ 
	Node* last; 
	cout<<"\nTraversal in forward direction \n"; 
	while (node != NULL) 
	{ 
		cout<<" "<<node->data<<" "; 
		last = node; 
		node = node->next; 
	} 

	cout<<"\nTraversal in reverse direction \n"; 
	while (last != NULL) 
	{ 
		cout<<" "<<last->data<<" "; 
		last = last->prev; 
	} 
} 

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

	// ندرج العنصر 6 لتصبح القائمة
	// 6->NULL 
	append(&head, 6); 

	// ندرج العنصر 7 في بداية القائمة لتصبح 
	// 7->6->NULL 
	push(&head, 7); 

	// ندرج العنصر 1 في بداية القائمة لتصبح 
	// 1->7->6->NULL 
	push(&head, 1); 

	// ندرج العنصر 4 في نهاية القائمة لتصبح 
	// 1->7->6->4->NULL 
	append(&head, 4); 

	// ندرج العنصر 8 بعد العنصر 7 في القائمة لتصبح
	// 1->7->8->6->4->NULL 
	insertAfter(head->next, 8); 

	cout << "Created DLL is: "; 
	printList(head); 

	return 0; 
}

• بايثون:

# Aعقدة في قائمة مترابطة
class Node: 

	# دالة بانية لإنشاء عقدة جديدة 
	def __init__(self, data): 
		self.data = data 
		self.next = None
		self.prev = None

# صنف لإنشاء قائمة مترابطة مزدوجة 
class DoublyLinkedList: 

	# دالة بانية لإنشاء قائمة مترابطة مزدوجة فارغة 
	def __init__(self): 
		self.head = None

	# يدرج التابع عقدة جديدة في مقدمة القائمة المترابطة باستخدام
	# الإشارة المعطاة (مؤشر إلى مؤشر) إلى رأس القائمة والعدد الصحيح المعطى 
	def push(self, new_data): 

		# 1. حجز موقع العقدة في الذاكرة 
		# 2. إضافة البيانات 
		new_node = Node(new_data) 

		# 3. None جعل ما يلي العقدة الجديدة رأسًا للقائمة وما يسبقها
		new_node.next = self.head 

		# 4. تحويل ما يسبق عقدة رأس القائمة ليصبح العقدة الجديدة 
		if self.head is not None: 
			self.head.prev = new_node 

		# 5. تحريك الرأس ليشير إلى العقدة الجديدة 
		self.head = new_node 

	# يدرج التابع عقدة جديدة بعد عقدة معينة معطاة 
	def insertAfter(self, prev_node, new_data): 

		# 1. None التحقق من أن العقدة المعطاة هي
		if prev_node is None: 
			print "the given previous node cannot be NULL"
			return

		# 2. حجز موقع العقدة الجديدة في الذاكرة
		# 3. إضافة البيانات
		new_node = Node(new_data) 

		# 4. جعل ما يلي العقدة الجديدة هو ما يلي العقدة السابقة
		new_node.next = prev_node.next

		# 5. جعل العقدة الجديدة تلي العقدة السابقة
		prev_node.next = new_node 

		# 6. جعل العقدة السابقة تسبق العقدة الجديدة 
		new_node.prev = prev_node 

		# 7. تغيير ما يسبق العقدة التي تلي العقدة الجديدة
		if new_node.next is not None: 
			new_node.next.prev = new_node 

	# تدرج الدالة عقدة جديدة في نهاية القائمة المترابطة المزدوجة
	# باستخدام إشارة (مؤشر إلى مؤشر) إلى رأس القائمة والعدد الصحيح المعطى 
	def append(self, new_data): 

		# 1. حجز موقع العقدة في الذاكرة 
		# 2. إضافة البيانات 
		new_node = Node(new_data) 

		# 3.None ستكون هذه العقدة هي العقدة الأخيرة لذا سنجعل ما يليها هو 
		new_node.next = None

		# 4. نجعل العقدة الجديدة رأسًا للقائمة إن كانت القائمة فارغة 
		if self.head is None: 
			new_node.prev = None
			self.head = new_node 
			return

		# 5. وإلا سننتقل عبر عناصر القائمة إلى نهايتها 
		last = self.head 
		while(last.next is not None): 
			last = last.next

		# 6. العقدة الجديدة تتلو العقدة الأخيرة في القائمة
		last.next = new_node 

		# 7. العقدة الأخيرة في القائمة هي التي تسبق العقدة الجديدة 
		new_node.prev = last 

		return

	# تطبع هذه الدالة محتويات القائمة المترابطة المزدوجة بدءًا من العقدة المعطاة 
	def printList(self, node): 

		print "\nTraversal in forward direction"
		while(node is not None): 
			print " % d" %(node.data), 
			last = node 
			node = node.next

		print "\nTraversal in reverse direction"
		while(last is not None): 
			print " % d" %(last.data), 
			last = last.prev 

# Dاختبار الدوال السابقة 

# نبدأ بقائمة فارغة 
llist = DoublyLinkedList() 

# ندرج العنصر 6 لتصبح القائمة
# 6->None 
llist.append(6) 

# ندرج العنصر 7 في بداية القائمة لتصبح 
# 7->6->None 
llist.push(7) 

# ندرج العنصر 1 في بداية القائمة لتصبح. 
# 1->7->6->None 
llist.push(1) 

# ندرج العنصر 4 في نهاية القائمة لتصبح. 
# 1->7->6->4->None 
llist.append(4) 

# ندرج العنصر 8 بعد العنصر 7 في القائمة لتصبح 
# 1->7->8->6->4->None 
llist.insertAfter(llist.head.next, 8) 

print "Created DLL is: ", 
llist.printList(llist.head)

• جافا:

// صنف القائمة المترابطة المزدوجة
public class DLL { 
	Node head; // رأس القائمة

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

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

	// إضافة عقدة في بداية القائمة المترابطة
	public void push(int new_data) 
	{ 
		/* 1. حجز موقع في الذاكرة
		* 2. إضافة البيانات */
		Node new_Node = new Node(new_data); 

		/* 3. NULL جعل ما يلي العقدة الجديدة رأسًا للقائمة وما يسبقها */
		new_Node.next = head; 
		new_Node.prev = null; 

		/* 4. تحويل ما يسبق عقدة رأس القائمة ليصبح العقدة الجديدة */
		if (head != null) 
			head.prev = new_Node; 

		/* 5. تحريك الرأس ليشير إلى العقدة الجديدة */
		head = new_Node; 
	} 

	/* تدرج الدالة عقدة جديدة بعد عقدة معينة معطاة */
	public void InsertAfter(Node prev_Node, int new_data) 
	{ 

		/*1. null التحقق من أن العقدة المعطاة هي */
		if (prev_Node == null) { 
			System.out.println("The given previous node cannot be NULL "); 
			return; 
		} 

		/* 2. حجز موقع العقدة الجديدة في الذاكرة */
		/* 3. إضافة البيانات */
		Node new_node = new Node(new_data); 

		/* 4. جعل ما يلي العقدة الجديدة هو ما يلي العقدة السابقة */
		new_node.next = prev_Node.next; 

		/* 5. جعل العقدة الجديدة تلي العقدة السابقة */
		prev_Node.next = new_node; 

		/* 6. جعل العقدة السابقة تسبق العقدة الجديدة */
		new_node.prev = prev_Node; 

		/* 7. تغيير ما يسبق العقدة التي تلي العقدة الجديدة */
		if (new_node.next != null) 
			new_node.next.prev = new_node; 
	} 

	// تدرج الدالة عقدة جديدة في نهاية القائمة المترابطة المزدوجة
	void append(int new_data) 
	{ 
		/* 1. حجز موقع العقدة في الذاكرة
		* 2. إضافة البيانات */
		Node new_node = new Node(new_data); 

		Node last = head; /* يستخدم في الخطوة 5*/

		/* 3. NULL ستكون هذه العقدة هي العقدة الأخيرة لذا سنجعل ما يليها هو */
		new_node.next = null; 

		/* 4. نجعل العقدة الجديدة رأسًا للقائمة إن كانت القائمة فارغة */
		if (head == null) { 
			new_node.prev = null; 
			head = new_node; 
			return; 
		} 

		/* 5. وإلا سننتقل عبر عناصر القائمة إلى نهايتها  */
		while (last.next != null) 
			last = last.next; 

		/* 6. العقدة الجديدة تتلو العقدة الأخيرة في القائمة */
		last.next = new_node; 

		/* 7. العقدة الأخيرة في القائمة هي التي تسبق العقدة الجديدة */
		new_node.prev = last; 
	} 

	// تطبع هذه الدالة محتويات القائمة المترابطة المزدوجة بدءًا من العقدة المعطاة 
	public void printlist(Node node) 
	{ 
		Node last = null; 
		System.out.println("Traversal in forward Direction"); 
		while (node != null) { 
			System.out.print(node.data + " "); 
			last = node; 
			node = node.next; 
		} 
		System.out.println(); 
		System.out.println("Traversal in reverse direction"); 
		while (last != null) { 
			System.out.print(last.data + " "); 
			last = last.prev; 
		} 
	} 

	/* اختبار الدوال السابقة*/
	public static void main(String[] args) 
	{ 
		/* نبدأ بقائمة فارغة */
		DLL dll = new DLL(); 

		// ندرج العنصر 6 لتصبح القائمة
		// 6->NULL 
		dll.append(6); 

		// ندرج العنصر 7 في بداية القائمة لتصبح
		// 7->6->NULL 
		dll.push(7); 

		// ندرج العنصر 1 في بداية القائمة لتصبح
		// 1->7->6->NULL 
		dll.push(1); 

		// ندرج العنصر 4 في نهاية القائمة لتصبح
		// 1->7->6->4->NULL 
		dll.append(4); 

		// ندرج العنصر 8 بعد العنصر 7 في القائمة لتصبح
		// 1->7->8->6->4->NULL 
		dll.InsertAfter(dll.head.next, 8); 

		System.out.println("Created DLL is: "); 
		dll.printlist(dll.head); 
	} 
}

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

لنفترض أنّ المؤشر إلى العقدة المعيّنة هو 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.

تعرض الشيفرة التالية طريقة تنفيذ الخطوات السابقة في لغة C++‎‎:

#include <stdio.h> 
#include <stdlib.h> 

// عقدة في قائمة مترابطة
struct Node { 
	int data; 
	struct Node* next; 
	struct Node* prev; 
}; 

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

	new_node->data = new_data; 

	new_node->next = (*head_ref); 
	new_node->prev = NULL; 

	if ((*head_ref) != NULL) 
		(*head_ref)->prev = new_node; 

	(*head_ref) = new_node; 
} 

/* تدرج الدالة التالية عقدة جديدة قبل العقدة المعطاة */
void insertBefore(struct Node** head_ref, struct Node* next_node, int new_data) 
{ 
	/*1. null التحقق من أنّ ما يلي العقدة الجديدة هو */
	if (next_node == NULL) { 
		printf("the given next node cannot be NULL"); 
		return; 
	} 

	/* 2. حجز موقع للعقدة الجديدة في الذاكرة */
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

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

	/* 4. جعل ما يسبق العقدة الجديدة هو نفسه ما يسبق العقدة التالية */
	new_node->prev = next_node->prev; 

	/* 5. جعل العقدة الجديدة تسبق العقدة التالية */
	next_node->prev = new_node; 

	/* 6. جعل العقدة التالية تلي العقدة الجديدة */
	new_node->next = next_node; 

	/* 7. تغيير ما يلي العقدة السابقة للعقدة الجديدة */
	if (new_node->prev != NULL) 
		new_node->prev->next = new_node; 
	/* 8. null إن كان ما يسبق العقدة الجديدة هو
	فإنها ستكون رأس القائمة الجديد */
	else
		(*head_ref) = new_node; 
	
} 

// تطبع الدالة محتويات القائمة المترابطة بدءًا من العقدة المعطاة
void printList(struct Node* node) 
{ 
	struct Node* last; 
	printf("\nTraversal in forward direction \n"); 
	while (node != NULL) { 
		printf(" %d ", node->data); 
		last = node; 
		node = node->next; 
	} 

	printf("\nTraversal in reverse direction \n"); 
	while (last != NULL) { 
		printf(" %d ", last->data); 
		last = last->prev; 
	} 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
	/* البدء بقائمة جديدة */
	struct Node* head = NULL; 
	push(&head, 7); 

	push(&head, 1); 

	push(&head, 4); 

    // إدراج العنصر 8 قبل العنصر 1، لتصبح القائمة
    // 4->8->1->7->NULL 
	insertBefore(&head, head->next, 8); 

	printf("Created DLL is: "); 
	printList(head); 

	getchar(); 
	return 0; 
}

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

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

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

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

أمثلة

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

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

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

/* تحذف هذه الدالة عقدة من القائمة المترابطة المزدوجة
head_ref --> مؤشر إلى مؤشر عقدة الرأس. 
del --> مؤشر إلى العقدة المراد حذفها. */
void deleteNode(Node** head_ref, Node* del) 
{ 
	/* الشرط الأساسي */
	if (*head_ref == NULL || del == NULL) 
		return; 

	/* إن كانت العقدة المراد حذفها هي عقدة الرأس */
	if (*head_ref == del) 
		*head_ref = del->next; 

	/* إن كانت العقدة المراد حذفها ليست العقدة الأخيرة فسنغير ما يليها */
	if (del->next != NULL) 
		del->next->prev = del->prev; 

	/* إن كانت العقدة المراد حذفها ليست العقدة الأولى فسنغير ما يسبقها */
	if (del->prev != NULL) 
		del->prev->next = del->next; 

	/* إفراغ الجزء المشغول بالعقدة المراد حذفها من الذاكرة */
	free(del); 
	return; 
} 

/* دوال مساعدة */
/* تدرج هذه الدالة عقدة في مقدمة القائمة المترابطة المزدوجة */
void push(Node** head_ref, int new_data) 
{ 
	/* حجز موقع العقدة في الذاكرة */
	Node* new_node = new Node(); 

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

	/* NULL بما أنّ العقدة المضافة هي في بداية القائمة فإنّ ما يسبقها هو */
	new_node->prev = NULL; 

	/* link the old list off the new node */
	new_node->next = (*head_ref); 

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

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

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

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

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

	/* إنشاء القائمة المترابطة المزدوجة التالية:
	 10<->8<->4<->2 */
	push(&head, 2); 
	push(&head, 4); 
	push(&head, 8); 
	push(&head, 10); 

	cout << "Original Linked list "; 
	printList(head); 

	/* حذف عقد من القائمة المترابطة المزدوجة */
	deleteNode(&head, head); /* حذف العقدة الأولى */
	deleteNode(&head, head->next); /*حذف عقد في وسط القائمة*/
	deleteNode(&head, head->next); /*حذف العقدة الأخيرة*/

	/* القائمة المترابطة بعد التعديلات:
	  NULL<-8->NULL */
	cout << "\nModified Linked list "; 
	printList(head); 

	return 0; 
}

• بايثون:

# استيراد وحدة جمع الكائنات المحذوفة Garbage Collector 
import gc 

# عقدة في القائمة المترابطة المزدوجة
class Node: 
	
	# دالة بانية لإنشاء عقدة جديدة
	def __init__(self, data): 
		self.data = data 
		self.next = None
		self.prev = None

class DoublyLinkedList: 
	# دالة بانية لإنشاء قائمة مترابطة فارغة
	def __init__(self): 
		self.head = None

# تحذف هذه الدالة عقدة من القائمة المترابطة المزدوجة 
# head_ref --> مؤشر إلى مؤشر عقدة الرأس.  
# dele --> مؤشر إلى العقدة المراد حذفها 

	def deleteNode(self, dele): 
		
		# الشرط الأساسي 
		if self.head is None or dele is None: 
			return
		
		# إن كانت العقدة المراد حذفها هي عقدة الرأس 
		if self.head == dele: 
			self.head = dele.next

		# إن كانت العقدة المراد حذفها ليست العقدة الأخيرة فسنغير ما يليها
		if dele.next is not None: 
			dele.next.prev = dele.prev 
	
		# إن كانت العقدة المراد حذفها ليست العقدة الأولى فسنغير ما يسبقها 
		if dele.prev is not None: 
			dele.prev.next = dele.next
		# إفراغ الجزء المشغول بالعقدة المراد حذفها من الذاكرة
		# استدعاء دالة جمع المهملات في بايثون 
		gc.collect() 


	# تدرج هذه الدالة عقدة في مقدمة القائمة المترابطة المزدوجة
	def push(self, new_data): 

		# 1.  حجز موقع العقدة في الذاكرة 
		# 2. إضافة البيانات  
		new_node = Node(new_data) 

		# 3. None جعل ما يلي العقدة الجديدة هو رأس القائمة وما يسبقها هو
		new_node.next = self.head 

		# 4. جعل العقدة الجديدة تسبق عقدة الرأس 
		if self.head is not None: 
			self.head.prev = new_node 

		# 5. تحريك رأس القائمة ليشير إلى العقدة الجديدة
		self.head = new_node 


	def printList(self, node): 
		while(node is not None): 
			print node.data, 
			node = node.next


# اختبار الدوال السابقة

# قائمة مترابطة جديدة
dll = DoublyLinkedList() 

# إنشاء القائمة المترابطة التالية
# 10<->8<->4<->2 
dll.push(2); 
dll.push(4); 
dll.push(8); 
dll.push(10); 

print "\n Original Linked List", 
dll.printList(dll.head) 

# حذف العقد من القائمة المترابطة المزدوجة
dll.deleteNode(dll.head) 
dll.deleteNode(dll.head.next) 
dll.deleteNode(dll.head.next) 
# القائمة المترابطة بعد التعديل:
# NULL<-8->NULL 
print "\n Modified Linked List", 
dll.printList(dll.head)

• جافا:

// صنف القائمة المترابطة المزدوجة 
public class DLL { 
	Node head; // رأس القائمة

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

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

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

	public void push(int new_data) 
	{ 
		/* 1. حجز موقع في الذاكرة
		* 2. إضافة البيانات */
		Node new_Node = new Node(new_data); 

		/* 3. NULL جعل ما يلي العقدة الجديدة رأسًا للقائمة وما يسبقها */ 
		new_Node.next = head; 
		new_Node.prev = null; 

		/* 4. تحويل ما يسبق عقدة رأس القائمة ليصبح العقدة الجديدة */ 
		if (head != null) 
			head.prev = new_Node; 

		/* 5. تحريك الرأس ليشير إلى العقدة الجديدة */ 
		head = new_Node; 
	} 

		// تطبع هذه الدالة محتويات القائمة المترابطة المزدوجة بدءًا من العقدة المعطاة 
 
	public void printlist(Node node) 
	{ 
		Node last = null; 

		while (node != null) { 
			System.out.print(node.data + " "); 
			last = node; 
			node = node.next; 
		} 

		System.out.println(); 
	} 

	/* تحذف هذه الدالة عقدة من القائمة المترابطة المزدوجة
head_ref --> مؤشر إلى مؤشر عقدة الرأس. 
del --> مؤشر إلى العقدة المراد حذفها. */
	void deleteNode(Node head_ref, Node del) 
	{ 

		// الشرط الأساسي
		if (head == null || del == null) { 
			return; 
		} 

		/* إن كانت العقدة المراد حذفها هي عقدة الرأس */
		if (head == del) { 
			head = del.next; 
		} 

		/* إن كانت العقدة المراد حذفها ليست العقدة الأخيرة فسنغير ما يليها */ 
		if (del.next != null) { 
			del.next.prev = del.prev; 
		} 

		/* إن كانت العقدة المراد حذفها ليست العقدة الأولى فسنغير ما يسبقها */ 
		if (del.prev != null) { 
			del.prev.next = del.next; 
		} 

		/* إفراغ الجزء المشغول بالعقدة المراد حذفها من الذاكرة */
		return; 
	} 

	// اختبار الدوال السابقة 
	public static void main(String[] args) 
	{ 
		// البدء بقائمة مترابطة مزدوجة جديدة
		DLL dll = new DLL(); 

		/* إنشاء القائمة المترابطة المزدوجة التالية:
	 10<->8<->4<->2 */
		dll.push(2); 
		dll.push(4); 
		dll.push(8); 
		dll.push(10); 

		System.out.print("Created DLL is: "); 
		dll.printlist(dll.head); 

		// حذف العقدة الأولى 
		dll.deleteNode(dll.head, dll.head); 
		/* القائمة المترابطة بعد التعديلات:
	  NULL<-8->NULL */

		System.out.print("\nList after deleting first node: "); 
		dll.printlist(dll.head); 

		// حذف العقدة الوسطى 
		dll.deleteNode(dll.head, dll.head.next); 

		System.out.print("\nList after Deleting middle node: "); 
		dll.printlist(dll.head); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Original Linked list 10 8 4 2 
 Modified Linked list 8

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

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

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

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

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

• C++‎:

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

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

/* دالة تعكس عقد القائمة المترابطة المزدوجة */
void reverse(Node **head_ref) 
{ 
	Node *temp = NULL; 
	Node *current = *head_ref; 
	
	/* تبديل المؤشرين السابق واللاحق لجميع العقد في القائمة المترابطة المزدوجة */
	while (current != NULL) 
	{ 
		temp = current->prev; 
		current->prev = current->next; 
		current->next = temp;			 
		current = current->prev; 
	} 
	
	/* قبل تغيير رأس القائمة يجري التحقق من كون القائمة فارغة أو أنّها تحتوي على عقدة واحدة فقط */
	if(temp != NULL ) 
		*head_ref = temp->prev; 
} 



/* دوال مساعدة */
/* تدرج هذه الدالة عقدة في مقدمة القائمة المترابطة المزدوجة */
void push(Node** head_ref, int new_data) 
{ 
	/* حجز موقع العقدة في الذاكرة */
	Node* new_node = new Node(); 

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

	/* NULL بما أنّ العقدة المضافة هي في بداية القائمة فإنّ ما يسبقها هو */
	new_node->prev = NULL; 

	/* link the old list off the new node */
	new_node->next = (*head_ref); 

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

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

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

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

/* اختبار الدوال السابقة */
int main() 
{ 
	/* قائمة مترابطة جديدة */
	Node* head = NULL; 
	
/* إنشاء القائمة المترابطة المزدوجة التالية:
	 10<->8<->4<->2 */
	push(&head, 2); 
	push(&head, 4); 
	push(&head, 8); 
	push(&head, 10); 
	
	cout << "Original Linked list" << endl; 
	printList(head); 
	
	/* قلب العناصر في القائمة المترابطة */
	reverse(&head); 
	
	cout << "\nReversed Linked list" << endl; 
	printList(head);		 
	
	return 0; 
}

• بايثون:

# عقدة في القائمة المترابطة المزدوجة
class Node: 
	
	# دالة بانية لإنشاء عقدة جديدة
	def __init__(self, data): 
		self.data = data 
		self.next = None
		self.prev = None

class DoublyLinkedList: 
	# دالة بانية لإنشاء قائمة مترابطة جديدة 
	def __init__(self): 
		self.head = None

	# دالة لقلب عناصر القائمة المترابطة المزدوجة
	def reverse(self): 
		temp = None
		current = self.head 
		
		# تبديل المؤشرين السابق واللاحق لجميع العقد في القائمة المترابطة المزدوجة
		while current is not None: 
			temp = current.prev 
			current.prev = current.next
			current.next = temp 
			current = current.prev 

		# قبل تغيير رأس القائمة يجري التحقق من كون القائمة فارغة أو أنّها تحتوي على عقدة واحدة فقط 
		if temp is not None: 
			self.head = temp.prev 
		
	# تدرج هذه الدالة عقدة في مقدمة القائمة المترابطة المزدوجة
	def push(self, new_data): 

		# 1.  حجز موقع العقدة في الذاكرة 
		# 2. إضافة البيانات  
		new_node = Node(new_data) 

		# 3. None جعل ما يلي العقدة الجديدة هو رأس القائمة وما يسبقها هو
		new_node.next = self.head 

		# 4. جعل العقدة الجديدة تسبق عقدة الرأس 
		if self.head is not None: 
			self.head.prev = new_node 

		# 5. تحريك رأس القائمة ليشير إلى العقدة الجديدة
		self.head = new_node 


	def printList(self, node): 
		while(node is not None): 
			print node.data, 
			node = node.next

# اختبار الدوال السابقة 
dll = DoublyLinkedList() 
dll.push(2); 
dll.push(4); 
dll.push(8); 
dll.push(10); 

print "\nOriginal Linked List"
dll.printList(dll.head) 

# قلب عناصر القائمة المترابطة المزدوجة
dll.reverse() 

print "\n Reversed Linked List"
dll.printList(dll.head)

• جافا:

class LinkedList { 

	static Node head; 

	static class Node { 

		int data; 
		Node next, prev; 

		Node(int d) { 
			data = d; 
			next = prev = null; 
		} 
	} 

	/* دالة تقلب عناصر القائمة المترابطة المزدوجة */
	void reverse() { 
		Node temp = null; 
		Node current = head; 

		/* تبديل المؤشرين السابق واللاحق لجميع العقد في القائمة المترابطة المزدوجة */
		while (current != null) { 
			temp = current.prev; 
			current.prev = current.next; 
			current.next = temp; 
			current = current.prev; 
		} 

		/* تبديل المؤشرين السابق واللاحق لجميع العقد في القائمة المترابطة المزدوجة */
		if (temp != null) { 
			head = temp.prev; 
		} 
	} 

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

	public void push(int new_data) 
	{ 
		/* 1. حجز موقع في الذاكرة
		* 2. إضافة البيانات */
		Node new_Node = new Node(new_data); 

		/* 3. NULL جعل ما يلي العقدة الجديدة رأسًا للقائمة وما يسبقها */ 
		new_Node.next = head; 
		new_Node.prev = null; 

		/* 4. تحويل ما يسبق عقدة رأس القائمة ليصبح العقدة الجديدة */ 
		if (head != null) 
			head.prev = new_Node; 

		/* 5. تحريك الرأس ليشير إلى العقدة الجديدة */ 
		head = new_Node; 
	} 

	// تطبع هذه الدالة محتويات القائمة المترابطة المزدوجة بدءًا من العقدة المعطاة 
 
	public void printlist(Node node) 
	{ 
		Node last = null; 

		while (node != null) { 
			System.out.print(node.data + " "); 
			last = node; 
			node = node.next; 
		} 

		System.out.println(); 
	} 

	public static void main(String[] args) { 
		LinkedList list = new LinkedList(); 

		/* إنشاء القائمة المترابطة المزدوجة التالية:
	 10<->8<->4<->2 */
		list.push(2); 
		list.push(4); 
		list.push(8); 
		list.push(10); 

		System.out.println("Original linked list "); 
		list.printList(head); 

		list.reverse(); 
		System.out.println(""); 
		System.out.println("The reversed Linked List is "); 
		list.printList(head); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Original linked list 
10 8 4 2 
The reversed Linked List is 
2 4 8 10

انظر أيضًا

• القوائم المترابطة Linked Lists.
• القوائم المترابطة الدائرية Circular Linked Lists.

مصادر

• صفحة Doubly Linked List Introduction and Insertion في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Delete a node in a Doubly Linked List في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Reverse a Doubly Linked List في توثيق بنى المعطيات في موقع GeeksforGeeks.