المصفوفات والقوائم المتصلة
تُعد المصفوفات والقوائم المتصلة الطريقتين الأساسيتين لتخزين تسلسل مرتب من العناصر: فالمصفوفات تضعها في ذاكرة متجاورة للوصول المفهرس بزمن ثابت، بينما تربط القوائم المتصلة العناصر عبر مؤشرات لإدراج وحذف منخفض التكلفة.
Definition
تخزن المصفوفة العناصر في مواقع ذاكرة متجاورة مفهرسة حسب الموضع، مما يسمح بالوصول العشوائي بزمن ثابت؛ بينما تخزن القائمة المتصلة العناصر في عقد منفصلة، تحتوي كل منها على مرجع إلى العقدة التالية (وربما السابقة)، مما يسمح بالإدراج أو الإزالة بزمن ثابت عند توفر مرجع للعقدة.
Scope
يغطي هذا الموضوع الهياكل الخطية القائمة على التسلسل وأنواع البيانات المجردة المبنية عليها — المصفوفات الثابتة والديناميكية، والقوائم المتصلة أحادية وثنائية الاتجاه، وأنواع البيانات المجردة للمكدس (stack) والصف (queue). ويقارن تكاليف الوصول والإدراج والحذف فيها، ويغطي تغيير حجم المصفوفة الديناميكية وتحليلها المطفأ، ويوضح عواقب تخطيط الذاكرة مثل التموضع في الذاكرة المخبئية (cache locality). ويستثني الهياكل الترابطية والهرمية التي تغطيها جداول التجزئة وأشجار البحث.
Core questions
- متى يتفوق التخزين المتجاور (المصفوفة) على التخزين المرتبط بالمؤشرات (القائمة)؟
- كيف تحقق المصفوفة الديناميكية إضافة بزمن ثابت مطفأ على الرغم من تغيير الحجم العرضي؟
- ما هي المفاضلات في التكلفة بين المصفوفات والقوائم المتصلة للإدراج والحذف والوصول؟
- كيف يتم تنفيذ المكدسات والصفوف فوق هذه الهياكل؟
- كيف يؤثر تخطيط الذاكرة على الأداء الفعلي من خلال سلوك الذاكرة المخبئية (cache)؟
Key concepts
- ذاكرة متجاورة
- وصول مفهرس
- تغيير حجم المصفوفة الديناميكية
- قوائم متصلة أحادية وثنائية الاتجاه
- مكدسات (LIFO)
- صفوف (FIFO)
- تكلفة مطفأة
- تموضع الذاكرة المخبئية
Key theories
- الوصول العشوائي مقابل الربط المتسلسل
- تدعم المصفوفات الوصول المفهرس بزمن O(1) ولكن الإدراج أو الحذف في المنتصف بزمن O(n)، بينما تدعم القوائم المتصلة الربط بزمن O(1) عند توفر عقدة ولكن الوصول حسب الموضع بزمن O(n)؛ ويعتمد الاختيار الصحيح على مزيج العمليات.
- النمو المطفأ للمصفوفات الديناميكية
- المصفوفة الديناميكية التي تضاعف سعتها عندما تمتلئ تقوم بنسخ O(n) عرضي ولكنها تُطفأ إلى O(1) لكل إضافة على أي تسلسل من العمليات، وذلك بطريقة التجميع أو الإمكانات.
Clinical relevance
تُعد المصفوفات والقوائم الركيزة الأساسية لكل برنامج تقريبًا: فالمصفوفات الديناميكية تنفذ أنواع القوائم/المتجهات الافتراضية في معظم اللغات، وتُعد الصفوف أساسًا للجدولة والبحث المتسع أولاً، وتُعد المكدسات أساسًا لإدارة استدعاءات الدوال وتقييم التعبيرات، وتُعد المفاضلة بين المصفوفة والقائمة قرارًا تصميميًا عمليًا روتينيًا يؤثر على الأداء.
History
تُعد المصفوفات من أقدم هياكل البيانات، وكانت موجودة في لغات البرمجة الأولى، وقد تم تقديم القوائم المتصلة لمعالجة الرموز والقوائم (خاصة في IPL لـ Newell و Shaw و Simon ولاحقًا في Lisp) في أواخر الخمسينيات. وقد أرسى معالجة Knuth المنهجية في كتابه The Art of Computer Programming تحليلها المعياري.
Key figures
- Donald Knuth
- Robert Sedgewick
Related topics
Seminal works
- knuth1997vol1
- cormen2009
Frequently asked questions
- لماذا نستخدم قائمة متصلة إذا كانت المصفوفات تدعم الوصول العشوائي السريع؟
- تسمح القوائم المتصلة بالإدراج أو الحذف في زمن ثابت عند توفر مرجع لعقدة، دون تحريك عناصر أخرى، وهو ما لا تستطيع المصفوفات فعله في المنتصف. وهي مفيدة عندما يتغير التسلسل بشكل متكرر ولا يكون الوصول العشوائي الموضعي ضروريًا.
- لماذا تُعتبر عمليات الإضافة إلى المصفوفة ذات زمن ثابت إذا كان تغيير الحجم ينسخ كل شيء؟
- يحدث تغيير الحجم نادرًا لأن السعة تتضاعف عادةً، لذا فإن إجمالي عمل النسخ على مدى n عملية إضافة يتناسب مع n. وعند توزيعه على جميع عمليات الإضافة، يعطي هذا تكلفة ثابتة مطفأة لكل إضافة على الرغم من أن عمليات تغيير الحجم الفردية هي O(n).