المصفوفات والقوائم المرتبطة: تكلفة الوصول والإضافة

الفرق الأساسي إيه؟

المصفوفة العادية ذات طول ثابت. أما حاوية مثل vector فتضيف إمكانية تغيير الحجم، وقد تحتاج عند التوسع إلى مساحة جديدة ونقل العناصر. لا تخلط الحالتين في المقارنة.

احسب العملية كاملة

كلمة «معروفة» مهمة. العثور على العقدة قد يحتاج زمنًا خطيًا، لذلك القول إن إضافة القائمة المرتبطة دائمًا ثابتة يهمل جزءًا من العمل.

مثال إضافة

القائمة الحالية 10 و20 و30، ونريد إضافة 15 بعد 10. في مصفوفة بها سعة كافية، يتحرك 20 و30 إلى اليمين ثم يوضع 15.

في القائمة المرتبطة، بعد الوصول لعقدة 10، نجعل الجديدة تشير إلى 20، ثم نجعل 10 تشير إلى الجديدة. النتيجة 10 و15 و20 و30.

لو الطلب هو «أضف بعد القيمة 10»، فاحسب تكلفة البحث أيضًا وحدد التصرف إذا لم توجد القيمة أو تكررت.

الذاكرة مهمة أيضًا

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

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

اختبر الحدود بالرسم

ارسم قائمة فارغة وأخرى بعقدة واحدة وثالثة بثلاث عقد. نفذ الإضافة في البداية وحذف أول عقدة، وراجع تغير الرأس وعدم فقد أي رابط.

وفي المصفوفة، ميّز عدد العناصر الحالي عن السعة المتاحة. وجود مكان محجوز لا يعني أنه عنصر فعلي في التسلسل.

اختار حسب الاستخدام

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

تدرس هذه المقارنات في هياكل البيانات بعد C++ في مسار جمال تك. الإجابة القوية تشرح الافتراضات، ولا تعلن أن نوعًا واحدًا أسرع في كل الظروف.