<![CDATA[
مقدمة
في علم الحاسوب، القائمة المرتبطة المضاعفة هي بنية بيانات مرتبطة تتكون من مجموعة من السجلات المرتبطة تسلسليًا تسمى العقد. تحتوي كل عقدة على حقلين: حقل بيانات وحقلين “رابطين” يشيران إلى العقدة التالية والعقدة السابقة في التسلسل. يسمح هذا الهيكل بالاجتياز في كلا الاتجاهين عبر القائمة، بدءًا من أي عقدة.
تُعتبر القوائم المرتبطة المضاعفة أكثر مرونة من القوائم المرتبطة المفردة، حيث تسمح بالوصول إلى العناصر السابقة بسهولة. ومع ذلك، فإنها تتطلب مساحة ذاكرة أكبر بسبب الحاجة إلى الحفاظ على مؤشرين لكل عقدة.
بنية القائمة المرتبطة المضاعفة
تتكون القائمة المرتبطة المضاعفة من سلسلة من العقد، حيث تحتوي كل عقدة على ثلاثة مكونات رئيسية:
- البيانات: تمثل المعلومات المخزنة في العقدة. يمكن أن تكون أي نوع من البيانات، مثل الأعداد الصحيحة، أو النصوص، أو الكائنات.
- التالي (Next): مؤشر يشير إلى العقدة التالية في القائمة. إذا كانت العقدة هي الأخيرة في القائمة، فإن هذا المؤشر يشير إلى قيمة فارغة (NULL).
- السابق (Previous): مؤشر يشير إلى العقدة السابقة في القائمة. إذا كانت العقدة هي الأولى في القائمة، فإن هذا المؤشر يشير إلى قيمة فارغة (NULL).
تحتوي القائمة أيضًا على مؤشر يسمى “الرأس” (Head) يشير إلى العقدة الأولى في القائمة. إذا كانت القائمة فارغة، فإن الرأس يشير إلى قيمة فارغة (NULL).
العمليات الأساسية على القائمة المرتبطة المضاعفة
تتضمن العمليات الأساسية التي يمكن إجراؤها على القائمة المرتبطة المضاعفة ما يلي:
- الإضافة (Insertion): إضافة عقدة جديدة إلى القائمة. يمكن إضافة العقدة في بداية القائمة، أو في نهايتها، أو في موضع معين داخل القائمة.
- الحذف (Deletion): حذف عقدة من القائمة. يمكن حذف العقدة من بداية القائمة، أو من نهايتها، أو من موضع معين داخل القائمة.
- البحث (Search): البحث عن عقدة معينة في القائمة بناءً على قيمتها.
- الاجتياز (Traversal): زيارة جميع العقد في القائمة، إما بالترتيب الأمامي (من الرأس إلى الذيل) أو بالترتيب العكسي (من الذيل إلى الرأس).
- العرض (Display): عرض بيانات العقد الموجودة في القائمة.
تنفيذ العمليات
الإضافة:
لإضافة عقدة جديدة إلى القائمة، يجب أولاً إنشاء العقدة الجديدة وتعيين قيم البيانات والمؤشرات الخاصة بها. ثم، يتم تحديث المؤشرات الخاصة بالعقد المجاورة لإدراج العقدة الجديدة في المكان المناسب.
الحذف:
لحذف عقدة من القائمة، يجب أولاً العثور على العقدة المراد حذفها. ثم، يتم تحديث المؤشرات الخاصة بالعقد المجاورة لتجاوز العقدة المحذوفة وإعادة ربط القائمة.
البحث:
للبحث عن عقدة في القائمة، يتم اجتياز القائمة بدءًا من الرأس ومقارنة قيمة البيانات في كل عقدة بالقيمة المراد البحث عنها. إذا تم العثور على تطابق، يتم إرجاع العقدة. وإلا، يتم إرجاع قيمة فارغة (NULL).
الاجتياز:
يمكن اجتياز القائمة في كلا الاتجاهين باستخدام المؤشرات “التالي” و “السابق”. يبدأ الاجتياز الأمامي من الرأس ويستمر حتى الوصول إلى نهاية القائمة. ويبدأ الاجتياز العكسي من الذيل ويستمر حتى الوصول إلى الرأس.
مزايا وعيوب القوائم المرتبطة المضاعفة
المزايا:
- المرونة: تسمح القوائم المرتبطة المضاعفة بالاجتياز في كلا الاتجاهين، مما يجعلها أكثر مرونة من القوائم المرتبطة المفردة.
- سهولة الحذف: يمكن حذف العقد بسهولة من القائمة دون الحاجة إلى اجتياز القائمة بأكملها.
- سهولة الإدراج: يمكن إدراج العقد بسهولة في أي مكان في القائمة.
العيوب:
- استهلاك الذاكرة: تتطلب القوائم المرتبطة المضاعفة مساحة ذاكرة أكبر من القوائم المرتبطة المفردة بسبب الحاجة إلى الحفاظ على مؤشرين لكل عقدة.
- التعقيد: يمكن أن تكون عمليات الإدراج والحذف أكثر تعقيدًا من العمليات المقابلة في القوائم المرتبطة المفردة.
تطبيقات القوائم المرتبطة المضاعفة
تُستخدم القوائم المرتبطة المضاعفة في مجموعة متنوعة من التطبيقات، بما في ذلك:
- إدارة الذاكرة: يمكن استخدام القوائم المرتبطة المضاعفة لتتبع تخصيص وإلغاء تخصيص الذاكرة.
- تنفيذ هياكل البيانات الأخرى: يمكن استخدام القوائم المرتبطة المضاعفة لتنفيذ هياكل بيانات أخرى، مثل المكدسات والطوابير.
- تطبيقات الوسائط المتعددة: يمكن استخدام القوائم المرتبطة المضاعفة لتخزين قوائم التشغيل في تطبيقات الوسائط المتعددة.
- محركات البحث: تُستخدم في فهرسة الكلمات والعبارات لتسريع عمليات البحث.
- أنظمة التشغيل: تُستخدم في إدارة العمليات والمهام.
مثال عملي (بشفرة زائفة)
يوضح المثال التالي كيفية إضافة عقدة إلى نهاية قائمة مرتبطة مضاعفة:
// تعريف هيكل العقدة
Node {
data: نوع البيانات
next: مؤشر إلى العقدة التالية
prev: مؤشر إلى العقدة السابقة
}
// دالة إضافة عقدة إلى نهاية القائمة
addNodeToEnd(head: مؤشر إلى رأس القائمة, data: نوع البيانات) {
newNode = إنشاء عقدة جديدة
newNode.data = data
newNode.next = NULL
if (head == NULL) { // القائمة فارغة
head = newNode
newNode.prev = NULL
} else {
current = head
while (current.next != NULL) { // الوصول إلى آخر عقدة
current = current.next
}
current.next = newNode
newNode.prev = current
}
}
مقارنة بين القوائم المرتبطة المفردة والمضاعفة
الفرق الرئيسي بين القوائم المرتبطة المفردة والمضاعفة يكمن في وجود المؤشر “السابق” في القوائم المرتبطة المضاعفة. هذا المؤشر يسمح بالاجتياز العكسي للقائمة، مما يوفر مرونة أكبر في بعض العمليات. ومع ذلك، يضيف أيضًا تعقيدًا واستهلاكًا إضافيًا للذاكرة.
الجدول التالي يلخص الاختلافات الرئيسية:
| الميزة | القائمة المرتبطة المفردة | القائمة المرتبطة المضاعفة |
|---|---|---|
| اتجاه الاجتياز | اتجاه واحد (إلى الأمام) | اتجاهين (إلى الأمام والخلف) |
| استهلاك الذاكرة | أقل | أكثر |
| تعقيد العمليات | أبسط | أكثر تعقيدًا |
| سهولة الحذف | أصعب (يتطلب اجتيازًا للعثور على العقدة السابقة) | أسهل (العقدة السابقة معروفة) |
اعتبارات الأداء
يعتمد أداء القوائم المرتبطة المضاعفة على نوع العملية التي يتم تنفيذها. بشكل عام، تكون عمليات الإدراج والحذف في القوائم المرتبطة المضاعفة أسرع من المصفوفات، خاصةً عندما يتم إدراج أو حذف العناصر في منتصف التسلسل. ومع ذلك، فإن الوصول إلى عنصر معين في القائمة المرتبطة المضاعفة يتطلب اجتياز القائمة بدءًا من الرأس أو الذيل، مما قد يستغرق وقتًا أطول من الوصول المباشر إلى عنصر في مصفوفة.
خاتمة
القائمة المرتبطة المضاعفة هي بنية بيانات قوية ومرنة تسمح بالاجتياز في كلا الاتجاهين. على الرغم من أنها تتطلب مساحة ذاكرة أكبر وأكثر تعقيدًا من القوائم المرتبطة المفردة، إلا أنها توفر مزايا كبيرة في بعض التطبيقات، مثل إدارة الذاكرة وتطبيقات الوسائط المتعددة. إن فهم بنية وعمليات القوائم المرتبطة المضاعفة أمر ضروري لأي مبرمج يسعى إلى تطوير تطبيقات فعالة.