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

تخيّل رحلة بحث عن كنز: كل ورقة تحمل قيمة ودليلاً يقود إلى الورقة التالية، والوصول إلى الخامسة يعني المرور واحدة تلو الأخرى. تلك هي 'القائمة المترابطة' — سلسلة من 'العُقَد'. الميزة: الإضافة أو الحذف في المنتصف بتعقيد O(1)، إذ يكفي أن تعيد توجيه دليل واحد. العيب: الوصول إلى موضع معيّن بطيء، O(n)، لأنّ

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

صنف (class): قالب لصندوق صغير له حقول. class Node يعرّف صندوقاً بحقلين: val (القيمة) و ‎next (مؤشّر إلى العقدة التالية)‎. Node(1) ينشئ صندوقاً كهذا، و self يعني ببساطة "هذا الصندوق".
قائمة مترابطة: بنية بيانات من عُقَد، كل منها يحمل قيمة ومؤشّر next إلى العقدة التالية؛ الإضافة/الحذف بجوار عقدة معروفة بتعقيد O(1)، لكن الوصول حسب الموضع بتعقيد O(n).
عقدة (node): لبنة بناء القائمة المترابطة: كائن صغير يحمل قيمة (val) ومؤشّراً (next) إلى العقدة التالية، أو None في النهاية.
محلية التخزين المؤقت (cache locality): مدى قُرب تخزين البيانات المستخدَمة معاً في الذاكرة؛ المصفوفة المتّصلة صديقة للـ cache، بينما عُقَد القائمة المترابطة المبعثرة أقل صداقة.