هيكلة البيانات بواسطة القائمة المرتبطة Linked List

مفهوم القائمة المرتبطة Linked List:

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

• الرابط: يمكن لكل رابط في قائمة المرتبطة تخزين بيانات تسمى عنصر.

• التالي: يحتوي كل رابط في القائمة المرتبطة على عنوان للرابط التالي، ويسمى بـ (Next).

• القائمة المرتبطة: تحتوي القائمة على رابط لعنوان العنصر الأول، ويسمى بـ (First).

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

يمكن تصور القائمة المرتبطة كسلسلة من العُقد، حيث تشير كل عقدة إلى العقدة التالية، وتتكون كل عقدة من: عنصر بيانات، عنوان عقدة أخرى. و يتم تمثيلهم على النحو التالي:

وفقًا للتوضيح أعلاه، فيما يلي النقاط المهمة التي يجب مراعاتها:

• تحتوي القائمة المرتبطة على عنصر ارتباط (وهو أول عنصر)، ويسمى أولاً.

• يحمل كل رابط حقل أو حقول لتخزين البيانات، وحقل للرابط يسمى التالي.

• كل رابط مرتبط برابط العنصر التالي من خلال تخزين عنوان العنصر التالي في حقل التالي.

• يحمل الرابط في العنصر الأخير ارتباطًا فارغًا (null) دلالة على نهاية القائمة.

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

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

قائمة مرتبطة البسيطة: يمكن التنقل بين العناصر إلى الأمام فقط.

قائمة مرتبطة المُضاعفة: يمكن التنقل بين العناصر للأمام وللخلف.

قائمة مرتبطة دائرية: يحتوي العنصر الأخير على ارتباط بالعنصر الأول كعنصر تالي والعنصر الأول له ارتباط بالعنصر الأخير كما في السابق.

العمليات الأساسية على القائمة المرتبطة:

فيما يلي العمليات الأساسية التي تدعمها قائمة:

عملية الإدراج:

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

تخيل أننا ندخل العُقدة (B) وهي العقدة جديدة، بين (A) وهي العقدة اليسرى بالنسبة لـ (B)، وبين (C) وهي العقدة اليمنى بالنسبة لـ (B)،  أي أننا نشير إلى “التالي” الخاص بالعقدة (B) إلى العقدة (C):

B.next −> c;

ويجب أن تبدو هكذا:

الآن، يجب أن يشير “التالي” الخاص بالعقدة (A) الموجودة على اليسار إلى العقدة الجديدة (B):

A.next −> B;

سيضع هذا العقدة الجديدة في منتصف الاثنين، يجب أن تبدو القائمة الجديدة هكذا:

إدراج قائمة مرتبطة: يجب اتخاذ خطوات مماثلة إذا تم إدخال العقدة في بداية القائمة، وأثناء إدراجه في النهاية، يجب أن تشير العقدة الأخيرة “القديمة” من القائمة إلى العقدة الجديدة وستشير العقدة الجديدة إلى (NULL).

عملية الحذف:

حذف عنصر من القائمة، والحذف هو أيضًا عملية أكثر من خطوة واحدة، فيتم أولاً، تحديد موقع العقدة المستهدفة المراد إزالتها باستخدام خوارزميات البحث، ثم يجب أن يشير “التالي” للعقدة اليسرى (السابقة) إلى “التالي” للعقدة الهدف (المراد حذفها):

LeftNode.next −> TargetNode.next;

الآن، باستخدام الكود التالي، سنزيل ما تشير إليه العقدة المستهدفة:

TargetNode.next −> NULL;

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

وهناك عمليات أخرى مهمة تتم على القائمة المرتبطة، مثل:

عملية العرض: يعرض القائمة الكاملة.

عملية البحث: يبحث عن عنصر باستخدام المفتاح المحدد.

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

مزايا القائمة المرتبطة:

1. الحجم الديناميكي.

2. سهولة الإدراج والحذف.

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

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

2. مطلوب مساحة ذاكرة إضافية لمؤشر مع كل عنصر من عناصر القائمة.

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

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

2. عندما لا يلزم تعريف الحجم مسبقاً، ويقتصر حجم القائمة على حجم الذاكرة.

3. لا يمكن أن تكون العقدة الفارغة موجودة في القائمة المرتبطة.

4. يمكننا تخزين قيم بدائية أو الكائنات في القائمة المرتبطة بشكل فردي.

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

• تخصيص ذاكرة الديناميكية.

• نفذت في المكدس (stack)، وقائمة الانتظار (Queue).

• في وظيفة التراجع عن البرامج.

• في جداول التجزئة (Hash table)، والرسم البياني (graph).