زمن التشغيل للقوائم المترابطة

تحليل زمن التشغيل في القوائم المنفَّذة باستخدام القائمة المترابطة

تمهيد نظري

يقصد بمصطلح زمن التشغيل (Time Complexity) مقدار الموارد الزمنية التي يستهلكها خوارزمٌ لتنفيذ مهمةٍ ما، معبرًا عنه عادةً كـ دالةٍ في حجم البيانات 𝐧. وفي الهياكل الخطِّيّة، ولا سيّما القوائم، يكتسب هذا التحليل أبعادًا حاسمة لأنّ الأداء يرتبط مباشرةً بترتيب التعليمات وطريقة الوصول إلى العُقد. وبخلاف القوائم المتجاورة (Array‑based Lists) التي تعتمد على موقعٍ متّصل في الذاكرة، فإن القائمة المترابطة (Linked List) تُمثِّل البيانات على شكل عقد غير متلاصقة يُشير كلٌّ منها إلى التالية؛ الأمر الذي يغيِّر كليًّا نمط الوصول، وبالتالي دوال التعقيد.

البنية الداخليّة للقائمة المترابطة

تتكوَّن العقدة (Node) من:

* الأحجام استرشادية وقد تختلف باختلاف لغة البرمجة أو المُعالج.

هذا التصميم يجعل الإضافة والحذف عملياتٍ ذات كفاءةٍ موضعية، لكنه يفرض عقوبةً على عمليات البحث المباشر بسبب غياب العناوين المتجاورة.

تحليل شامل لعمليات القائمة المترابطة

1. الإدراج عند الرأس

• الخطوات: إنشاء عقدة → ربطها بالرأس الحالي → تحديث الرأس

• التعقيد: 𝐎(1)

• التفسير: لا يلزم اجتياز أي عقد؛ جميع المؤشِّرات المطلوبة متاحةٌ فورًا.

2. الإدراج عند الذيل

• أ) بدون مؤشِّر إلى الذيل: اجتياز القائمة كاملة ثم إضافة العقدة → 𝐎(𝐧)

• ب) مع حفظ مؤشِّر إلى الذيل: تحديث مؤشِّر الذيل مباشرةً → 𝐎(1)

3. الإدراج في موضعٍ وسط

• يتطلب اجتيازًا حتى الموضع‑1 ثم ربط العقدة الجديدة → 𝐎(𝐤) حيث 𝐤 هو ترتيب الموضع، وبأسوأ حال 𝐎(𝐧).

4. الحذف عند الرأس

• فك ارتباط الرأس وتحديث المؤشر → 𝐎(1)

5. الحذف عند الذيل

• إن لم يُحتفَظ بمؤشِّر للأب قبل الأخير، يلزم اجتياز القائمة → 𝐎(𝐧)

6. الحذف وسط القائمة

• اجتياز حتى الموضع‑1 ثم ضبط المؤشر → 𝐎(𝐤) وبأسوأ حال 𝐎(𝐧)

7. البحث الخطي

• فحص تسلسلي لكل عقدة حتى التطابق أو نهاية القائمة → 𝐎(𝐧)

8. طول القائمة

• أ) مع عدّاد طول مُحدَّث آنيًّا: 𝐎(1)

• ب) بدون عدّاد: اجتياز كامل → 𝐎(𝐧)

مقارنة مع القوائم المتجاورة

يوضح الجدول الآتي الفروقات الجوهرية بين الهيكلين من منظور زمن التشغيل ومتطلّبات الذاكرة:

أثر إدارة الذاكرة المخبأة (Cache)

على الرغم من تشابه بعض الدوال النظرية، فإن الأداء العملي يختلف جذريًّا بسبب المحلّيات المكانية (Spatial Locality). في القوائم المتجاورة، تُحمَّل مجموعة سجلات متجاورة دفعةً واحدة إلى الذاكرة المخبأة، بينما تتشتت عُقد القائمة المترابطة عبر الذاكرة؛ ما يزيد نسب أخطاء المخبأ (Cache Misses) ويضاعف الزمن الفعلي. تُظهر القياسات المعملية أن برنامجًا بسيطًا للبحث الخطي في مصفوفة قد يتفوّق بزمنٍ يصل إلى 5‑7 مرّات على نظيره في قائمةٍ مترابطة بالحجم نفسه، رغم تطابق التعقيد 𝐎(𝐧).

تحسينات وتقنيات متقدّمة

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

تُضيف مؤشّرًا عكسيًّا (prev) يسمح بالاجتياز ثنائي الاتجاه ويحسّن حذف الذيل إلى 𝐎(1)، لكن يضاعف استهلاك الذاكرة ويعقّد عمليات الدمج.

2. قائمة الانتقال (Skip List)

طبقة فهرسة علوية تربط عُقدًا متباعدة بخطوات لوغاريتمية، ما يخفض البحث إلى 𝐎(log 𝐧) ومتوسط الإضافة والحذف إلى 𝐎(log 𝐧) مع محافظة على بساطة الإدراج الخطي في المستوي الأساسي.

3. قائمة غير متزامنة مقفلة (Lock‑Free)

في المعالجات متعددة الأنوية، تؤمّن عمليات CAS (Compare‑and‑Swap) تناسقًا بدون أقفال تقليدية، فتقلّل تأخر الخيوط (Thread Latency) وتمنع التوقّف المتبادَل (Deadlock).

4. تخصيص عقد بالدفعات (Node Pooling)

بدل استدعاء المُجمِّع كل مرة، تُخصَّص كتلة عناقيد وتُدار داخليًّا، ما يخفض كلفة التخصيص ويُحسِّن تماسك المخبأ.

السيناريوهات التطبيقية المثالية للقوائم المترابطة

• محرّكات المُصوِّرات النصيّة حيث تتكرّر عمليات الإدراج والحذف في مواضع أوّل القائمة.

• تنفيذ جداول الانتظار ذات الأولوية عند دمج عقد واردة باستمرار.

• المترجمات في إدارة لائحة الرموز القابلة للتوسُّع أثناء التحليل الدلالي.

في المقابل، لا تُوصَى القائمة المترابطة للبنى التي تتطلّب وصولًا عشوائيًّا متكررًا، كالمعالجة الرقمية للإشارات أو الحوسبة العلمية المصفوفية.

قياسٌ تجريبي

طبقًا لاختبارات أُجرِيت بلغة ++C على جهازٍ بمعالج ‎Intel i7‑12700‎، 16 GB DDR5، أُنشِئت قوائم بأحجام من $10^3$ إلى $10^7$ عنصر. أظهرت النتائج المتوسّطة:

تتوافق الفجوة المتزايدة مع ازدياد ضربات الـ Cache Miss مع نمو الحجم.

اعتبارات التصميم البرمجي

1. إخفاء التفاصيل عبر كائن يحوي واجهة (API) غنية يحول دون إساءة استخدام المؤشّرات.

2. تتبّع الشذوذ بتحققٍ داخلي من سلامة المؤشّرات بعد كل عملية في طور التصحيح.

3. تأمين التزامن باستراتيجية تناسب نموذج التنفيذ (أقفال دقيقة، أقفال قراءة/كتابة، أو عدم وجود أقفال).

خاتمة

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

المصادر

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 3rd ed., MIT Press, 2009.

2. Sedgewick, R. & Wayne, K. Algorithms, 4th ed., Addison‑Wesley, 2011.