الدرس الثاني (٣)

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

الفكرة الأساسية

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

الشرح

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

مثال محلول خطوة بخطوة

لديك قائمة مترابطة تضم العقد: 12 و99، وتريد إدراج العنصر 37 كعنصر ثانٍ بينهما. اتبع الخطوات التالية:

1. أنشئ العقدة الجديدة التي تحمل القيمة 37.
2. اربط مؤشر العقدة الجديدة (الثانية) لكي يشير إلى عنوان العقدة الثالثة التي تحمل القيمة 99.
3. اربط مؤشر العقدة الأولى التي تحمل القيمة 12 لكي يشير إلى عنوان العقدة الجديدة التي تحمل القيمة 37. هكذا تصبح القائمة مؤلفة من ثلاثة عناصر متسلسلة: 12 تليها 37 تليها 99، دون الحاجة لتغيير مواقع عناصر المنتصف في الذاكرة.

أخطاء شائعة

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

سؤالان للتدريب مع الإجابة

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