ما هي القائمة المرتبطة (Linked List)؟ شرح مبسّط مع أنواعها ومتى تستخدمها

القائمة المرتبطة (Linked List) هي بنية بيانات تُخزّن العناصر في سلسلة من «العُقَد» (Nodes)، بحيث تحمل كل عقدة قيمتها الخاصة بالإضافة إلى مؤشّر (Pointer) يدلّ على مكان العقدة التالية في الذاكرة. الفكرة الجوهرية أن العناصر ليست متجاورة فيزيائيًا كما في المصفوفة، بل موزّعة في أماكن مختلفة من الذاكرة ويربط بينها المؤشّرات. هذا التصميم البسيط هو ما يمنحها مرونتها الشهيرة في الإضافة والحذف، وهو أيضًا مصدر أبرز عيوبها كما سنرى.

كيف تعمل القائمة المرتبطة عمليًا؟

تخيّل قطارًا: كل عربة تحمل الركّاب (البيانات) وتحمل أيضًا خطّافًا يربطها بالعربة التالية (المؤشّر). أنت لا تعرف موقع العربة الأخيرة مباشرة؛ للوصول إليها تبدأ من العربة الأولى (تُسمّى الرأس Head) وتتنقّل عبر الخطّافات واحدة تلو الأخرى.

كل عقدة إذًا تتكوّن من جزأين:

1. البيانات (Data): القيمة المخزّنة، سواء كانت رقمًا أو نصًا أو كائنًا كاملًا.
2. المؤشّر (Next): عنوان العقدة التالية. آخر عقدة يشير مؤشّرها إلى «لا شيء» (null) للدلالة على نهاية القائمة.

نقطة يخطئ فيها المبتدئون كثيرًا: لا يوجد «فهرس رقمي» تصل به مباشرة إلى العنصر رقم 5 كما في المصفوفة. الوصول دائمًا يبدأ من الرأس ويمشي خطوة بخطوة.

أنواع القوائم المرتبطة

1. القائمة الأحادية (Singly Linked List)

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

2. القائمة المزدوجة (Doubly Linked List)

كل عقدة تحمل مؤشّرين: واحد للعقدة التالية وآخر للعقدة السابقة. هذا يتيح التنقّل في الاتجاهين ويُسهّل الحذف، لكنه يستهلك ذاكرة أكبر بسبب المؤشّر الإضافي. معظم قوائم التشغيل ونظام «التراجع/الإعادة» (Undo/Redo) تعتمد على هذا النوع.

3. القائمة الدائرية (Circular Linked List)

هنا يشير مؤشّر العقدة الأخيرة إلى الرأس بدل «null»، فتتكوّن حلقة مغلقة. مفيدة في السيناريوهات المتكرّرة مثل توزيع المعالج على العمليات (Round-Robin) أو عرض الشرائح المتكرّر.

القائمة المرتبطة أم المصفوفة؟

هذا هو السؤال الحقيقي وراء معظم عمليات البحث. الاختيار يعتمد على نوع العمليات الأكثر تكرارًا في تطبيقك:

المعيار	القائمة المرتبطة	المصفوفة (Array)
الوصول لعنصر بالفهرس	بطيء — O(n)	فوري — O(1)
الإضافة/الحذف في البداية	سريع — O(1)	بطيء — O(n)
الإضافة/الحذف في المنتصف	O(1) بعد الوصول للموقع	بطيء — O(n)
الحجم	ديناميكي، ينمو ويتقلّص	ثابت غالبًا (أو يتوسّع بتكلفة)
استهلاك الذاكرة	أعلى (مؤشّرات إضافية)	أقل واقتصادي
كفاءة الذاكرة المؤقتة (Cache)	ضعيفة	ممتازة

نصيحة من واقع الممارسة: الـ Big-O لا يحكي القصة كاملة

على الورق، تبدو القائمة المرتبطة أسرع في الإضافة والحذف. لكن في الأجهزة الحديثة تلعب «ذاكرة الكاش» (CPU Cache) دورًا حاسمًا. لأن عناصر المصفوفة متجاورة في الذاكرة، يجلبها المعالج دفعة واحدة فتصبح المرور عليها سريعًا جدًا. أما عُقَد القائمة المرتبطة فمبعثرة، فيضطر المعالج للقفز بين مواقع متباعدة، وهذا يبطئ الأداء الفعلي حتى لو بدا التعقيد النظري أفضل.

الخلاصة العملية: لا تختر القائمة المرتبطة لمجرّد أن كتاب الخوارزميات مدحها. في كثير من الحالات الواقعية تتفوّق المصفوفة الديناميكية (مثل ArrayList في جافا أو vector في C++ أو list في بايثون) حتى في عمليات الإدراج، ما لم يكن الإدراج والحذف المتكرّر في المقدمة أو الوسط هو جوهر عملك.

أين تُستخدم القوائم المرتبطة فعليًا؟

• بناء هياكل أخرى: المكدّس (Stack) والطابور (Queue) يُبنيان بسهولة فوق القائمة المرتبطة.
• إدارة الذاكرة: بعض أنظمة التشغيل تتعقّب كتل الذاكرة الحرّة عبر قوائم مرتبطة.
• الجداول التجزيئية (Hash Tables): تُستخدم القوائم لمعالجة التصادمات (Chaining).
• الأنظمة التي تتطلّب إدراجًا وحذفًا كثيفًا دون معرفة الحجم مسبقًا.

الأسئلة الشائعة

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

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

لماذا الوصول لعنصر معيّن بطيء (O(n))؟ لأنه لا يوجد فهرس مباشر؛ يجب أن تبدأ من الرأس وتتنقّل عبر المؤشّرات عقدة بعقدة حتى تصل للعنصر المطلوب.

متى أفضّل القائمة المزدوجة على الأحادية؟ عندما تحتاج التنقّل في الاتجاهين أو الحذف السريع لعقدة تعرف موقعها، مثل أنظمة التراجع والإعادة أو مشغّلات الوسائط التي تنتقل للخلف والأمام.