كلاهما يخزن تسلسلات، لكن لديهما ملفات تكلفة معاكسة. المصفوفة عبارة عن ذاكرة متجاورة بفهرسة O(1)؛ قائمة الربط عبارة عن عقد متناثرة مرتبطة بمؤشرات، مع إدراج/حذف O(1) في النهايات لكن بدون فهرسة.
كلاهما يخزن تسلسلات، لكن لديهما ملفات تكلفة معاكسة. المصفوفة عبارة عن ذاكرة متجاورة بفهرسة O(1)؛ قائمة الربط عبارة عن عقد متناثرة مرتبطة بمؤشرات، مع إدراج/حذف O(1) في النهايات لكن بدون فهرسة.
| العملية | المصفوفة (ديناميكية) | قائمة الربط |
|---|
| الوصول بالفهرس | O(1) | O(n) |
| البحث | O(n) | O(n) |
| الإدراج/الحذف في البداية | O(n) | O(1) |
| الإدراج/الحذف في النهاية | O(1)摊销 | O(1) مع tail ptr |
| الإدراج/الحذف في المنتصف | O(n) | O(n) بحث + O(1) splice |
| النفقات العامة للذاكرة | منخفضة | عالية (مؤشر لكل عقدة) |
| محلية الذاكرة المؤقتة | ممتازة | ضعيفة |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
في الممارسة العملية، المصفوفات تفوز معظم الوقت لأن محلية الذاكرة المؤقتة تفوق الفروقات Big-O للأحجام النموذجية.
معرفة كلاهما تتيح لك تبرير اختيارك في المقابلات بدلاً من الافتراض الأعمى — وشرح السبب في أن "الإدراج O(1)" نادراً ما يتفوق على مصفوفة متجاورة.