Algorithms/linked lists

لقوائم المترابطة هLinked Lists ي بنى معطيات خطية لا تخزّن فيها العناصر في مواقع متجاورة في الذاكرة.،تورتبط العناصر بعضها ببعض في القوائم المترابطة بواسطة المؤشرات وكما هو موضّح في الصورة التالية:

ويمكن القول أنّ القوائم المترابطة تتكوّن من عقد، وتحتوي كل عقدة منها على حقل بيانات وإشارة (رابطة) إلى العقدة التالية في القائمة.

لماذا تستخدم القوائم المترابطة

يمكن استخدام المصفوفات لتخزين البيانات الخطية التي تكون من النوع ذاته، ولكن يعيب المصفوفات ما يلي:

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

لنفرض -على سبيل المثال- أنّ لدينا قائمة من المعرّفات المرتبة في مصفوفة: id[] = [1000, 1010, 1050, 2000, 2040]‎.

لو أردنا إضافة معرّف جديد يحمل القيمة 1005 دون الإخلال بترتيب العناصر، فيتحتّم علينا حينئذٍ تحريك جميع العناصر التي تلي المعرّف 1000.

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

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

تختلف القوائم المترابطة عن المصفوفات بالنقاط التالية:

1. المصفوفة هي بنية معطيات تحتوي على مجموعة من عناصر ذات نوع متشابه، في حين أنّ القوائم المترابطة تُعدّ من بنى المعطيات غير البدائية والتي تحتوي على مجموعة من العناصر المترابطة وغير المرتبة والتي تدعى بالعقد.
2. تنتمي العناصر في المصفوفات إلى فهارس، بمعنى أنّه لغرض الوصول إلى العنصر الرابع في المصفوفة يجب كتابة اسم المتغير مع فهرسه أو موقعه ضمن أقواس مربعة.
3. أما في القوائم المترابطة فيجب البدء من الرأس ثم المرور على العناصر واحدًا تلو الآخر إلى حين الوصول إلى العنصر الرابع.
4. يمكن الوصول إلى عنصر ما في المصفوفة بسرعة، أما القوائم المترابطة فإنّ الوصول إلى العناصر فيها يأخذ وقتًا خطيًّا أكثر؛ ولهذا تكون القوائم المترابطة أبطأ قليلًا مقارنة بالمصفوفات.
5. تستهلك عمليات مثل الإضافة والحذف الكثير من الوقت في المصفوفات، ولكنّها تكون سريعة في القوائم المترابطة.
6. حجم المصفوفات ثابت، وذلك على عكس القوائم المترابطة التي تكون ذات حجم متغير وتمتاز بالمرونة والقابلية على تكبير أو تصغير حجمها حسب الحاجة.
7. تُسند المعلومات إلى الذاكرة عن استخدام المصفوفات في وقت التصريف compile time، أما عند استخدام القوائم المترابطة فإنّ الذاكرة تُحجز في وقت التشغيل أو التنفيذ runtime.
8. تخزن العناصر في المصفوفة بالترتيب، وتخزّن في القوائم المترابطة بصورة عشوائية.
9. تتطلب المصفوفات مقدارًا أقل من الذاكرة وذلك نظرًا لتخزين البيانات الفعلية ضمن الفهرس، أما القوائم المترابطة فتحتاج بالمقابل إلى مقدار أكبر من الذاكرة وذلك لحاجتها إلى تخزين عناصر إضافية للإشارة إلى العقد السابقة واللاحقة.
10. لا يمكن استخدام الذاكرة بكفاءة مع المصفوفات، وذلك على عكس القوائم المترابطة.

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

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

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

تمثّل القائمة المترابطة بواسطة مؤشر pointer إلى العقدة الأولى في القائمة المترابطة. تدعى العقدة الأولى بالرأس head، وإن كانت القائمة المترابطة فارغة، فإنّ قيمة الرأس تكون NULL.

تتكوّن كل عقدة في القائمة من جزئين:

1. البيانات.
2. مؤشر Pointer (أو إشارة Reference) إلى العقدة التالية.

يمكن تمثيل العقدة في لغة C باستخدام البنى structures. يبين المثال التالي عقدة قائمة مترابطة مع بيانات عددية.

struct Node 
{ 
  int data; 
  struct Node *next; 
};

• Java, C#‎

أما في لغتي Java و C#‎ فيمكن تمثيل القوائم المترابطة بواسطة صنف والعقد بواسطة صنف آخر منفصل، ويحتوي صنف القائمة المترابطة على إشارة إلى صنف العقدة.

// C#
class LinkedList 
{ 
	Node head; 

	class Node 
	{ 
		int data; 
		Node next; 
		
        // دالة بانية لإنشاء عقدة جديدة
		Node (int d) {data = d;} 
	} 
}

//Java
class LinkedList 
{ 
    Node head;
  
    // العقدة
    class Node 
    { 
        int data; 
        Node next; 
           
        // دالة بانية لإنشاء عقدة جديدة
        // أما القيمة العقدة اللاحقة فتهيئ تلقائيًا
        // null إلى القيمة
        Node(int d) {data = d;} 
    } 
}

• بايثون:

# Node class 
class Node: 
   
    # دالة لتهيئة كائن العقدة
    def __init__(self, data): 
        self.data = data  # إسناد البيانات
        self.next = None  # تهيئة العقدة التالية لتكون فارغة 
   
# صنف القائمة المترابطة
class LinkedList: 
     
    # دالة لتهيئة كائن القائمة المترابطة  
    def __init__(self):  
        self.head = None

مصادر

https://www.geeksforgeeks.org/data-structures/linked-list/

https://www.geeksforgeeks.org/linked-list-set-1-introduction/