القوائم المتصلة المتداخلة (Intrusive linked lists) هي نوع من القوائم المتصلة التي تكون فيها روابط الربط مُضمَّنةً داخل البنية نفسها التي يجري ربطها.
في التنفيذ المعتاد للقائمة المترابطة، تحتوي عقدة القائمة على مؤشر بيانات يشير إلى البيانات المترابطة، ومؤشر "التالي" (next pointer) يشير إلى العقدة التالية في القائمة.
في تنفيذ القائمة المتصلة المتداخلة (intrusive linked list)، تحتوي عقدة القائمة على مؤشر يشير إلى العقدة التالية، ولكنها لا تحتوي على مؤشر للبيانات؛ وذلك لأن القائمة تكون مضمّنةً داخل الكائن المرتبط نفسه.
تكون عقدة القائمة (list node) مضمّنة داخل الكائن الذي يحتويها.تشير عقدة القائمة هذه إلى عقدة قائمة أخرى مضمّنة في الكائن المرتبط (linked object).
يتم حساب العنوان الأساسي للكائن المرتبط عن طريق طرح قيمة الإزاحة (offset) الخاصة بعضو القائمة من عنوان الذاكرة الخاص بكائن القائمة المرتبطة.
بعد كل هذه العمليات الحسابية على المؤشرات، ربما تتساءل: لماذا قد يلجأ أي شخص عاقل إلى استخدام قائمة مرتبطة "متداخلة" (intrusive linked list) بدلاً من القائمة المرتبطة العادية؟
لماذا نستخدم القوائم المرتبطة المتداخلة؟
هناك سببان رئيسيان لتفضيل القوائم المتداخلة على القوائم المرتبطة غير المتداخلة (non-intrusive):
- عدد أقل من عمليات تخصيص الذاكرة.
- انخفاض معدل "اضطراب الذاكرة المخبئية" (cache thrashing).
كما تعاني القوائم المرتبطة المتداخلة بشكل أقل من مشكلة اضطراب الذاكرة المخبئية؛ فالتنقل عبر عقدة قائمة غير متداخلة يتطلب الوصول إلى محتوى العقدة (dereferencing) ثم الوصول إلى بيانات القائمة، بينما تتطلب القوائم المتداخلة الوصول فقط إلى عقدة القائمة التالية.
قبل استعراض كيفية إدارة العمليات (processes) باستخدام القوائم المرتبطة في نظام Linux، يجب عليك فهم القوائم المرتبطة المزدوجة (doubly linked lists) والقوائم المرتبطة الدائرية (circular linked lists).
ليست هناك تعليقات:
إرسال تعليق