ما هي المصفوفة الديناميكية (Dynamic Array)؟ شرح عملي بالأمثلة
المصفوفة الديناميكية (Dynamic Array) هي مصفوفة تستطيع أن تكبر أو تصغر أثناء تشغيل البرنامج، بدلاً من أن يكون حجمها ثابتاً منذ لحظة إنشائها. أنت تضيف إليها عناصر دون أن تعرف عددها مسبقاً، وهي تتكفّل تلقائياً بحجز ذاكرة أكبر عند الحاجة. هذا بالضبط ما تقدّمه أدوات مثل std::vector في ++C وArrayList في جافا وList<T> في #C وlist في بايثون وVec في رست، وحتى مصفوفة Array في جافاسكربت. الفكرة واحدة في كل هذه اللغات، والفهم الصحيح لها يوفّر عليك أخطاء أداء يقع فيها كثير من المبرمجين.
كيف تعمل المصفوفة الديناميكية من الداخل؟
المفتاح لفهمها هو التمييز بين قيمتين تحتفظ بهما دائماً:
- الطول (Size/Length): عدد العناصر المستخدمة فعلياً.
- السعة (Capacity): حجم كتلة الذاكرة المحجوزة، وهي عادةً أكبر من الطول.
عند إنشاء المصفوفة تحجز كتلة ذاكرة متجاورة بسعة معيّنة. طالما أن الطول أقل من السعة، فإضافة عنصر جديد تعني ببساطة وضعه في الخانة الفارغة التالية، وهي عملية فورية. لكن عندما يمتلئ الطول ويساوي السعة ثم تحاول الإضافة، يحدث ما يلي:
- تُحجز كتلة ذاكرة جديدة أكبر (غالباً ضِعف السعة الحالية).
- تُنسخ كل العناصر القديمة إلى الكتلة الجديدة.
- تُحرَّر الكتلة القديمة، ثم يُضاف العنصر الجديد.
هذه العملية تُسمّى إعادة التخصيص (Reallocation)، وهي مكلفة لأنها تنسخ كل العناصر. السرّ في كفاءة المصفوفة الديناميكية هو أنها لا تكبّر نفسها خانةً واحدة في كل مرة، بل تضاعف السعة، فتصبح إعادة التخصيص حدثاً نادراً وليس متكرراً.
لماذا تُوصف الإضافة بأنها «سريعة» رغم النسخ؟
هنا يظهر مفهوم مهم اسمه التكلفة المُستهلَكة (Amortized Cost). صحيح أن عملية إضافة واحدة قد تُكلّف O(n) عندما تصادف لحظة إعادة التخصيص، لكن لأن مضاعفة السعة تجعل هذه اللحظات متباعدة، فإن متوسط تكلفة الإضافة موزّعاً على عدد كبير من العمليات يظل O(1) مُستهلَكة.
بعبارة أبسط: أضف ألف عنصر، ستحدث إعادة التخصيص بضع مرات فقط (عند 1، 2، 4، 8… وهكذا)، ومجموع النسخ يبقى قريباً من عدد العناصر نفسه. لهذا تُعتبر الإضافة في نهاية المصفوفة رخيصة عملياً.
انتبه: هذا الكلام يخص الإضافة في النهاية (append/push_back). أما الإدراج أو الحذف في بداية أو وسط المصفوفة فيتطلب إزاحة كل العناصر التي بعده، وتكلفته O(n) دائماً، وهذه نقطة ضعف حقيقية للمصفوفة الديناميكية.
مقارنة سريعة: مصفوفة ثابتة أم ديناميكية أم قائمة مترابطة؟
| المعيار | المصفوفة الثابتة | المصفوفة الديناميكية | القائمة المترابطة |
|---|---|---|---|
| تغيير الحجم وقت التشغيل | لا | نعم، تلقائياً | نعم |
| الوصول بالفهرس (index) | O(1) | O(1) | O(n) |
| الإضافة في النهاية | غير ممكن | O(1) مُستهلَكة | O(1) |
| الإدراج/الحذف في الوسط | O(n) | O(n) | O(1) بعد الوصول للعقدة |
| ترتيب الذاكرة | متجاور | متجاور | مبعثر (عقد مرتبطة) |
الخلاصة العملية: إذا كان همّك الأساسي الوصول السريع بالفهرس والإضافة في النهاية، فالمصفوفة الديناميكية هي الخيار الافتراضي الأفضل. أما إذا كنت تُدرج وتحذف كثيراً من المنتصف، ففكّر في القائمة المترابطة أو هيكل آخر مثل الطابور المزدوج (Deque).
أين تُستخدم فعلياً؟
المصفوفة الديناميكية ليست مجرد نظرية، بل هي اللبنة التي تُبنى عليها هياكل أخرى:
- المكدّس (Stack): الدفع والسحب يحدثان في النهاية، وهو ما تجيده المصفوفة الديناميكية تماماً.
- جداول التجزئة (Hash Tables): كثير من التطبيقات تخزّن الخانات (buckets) في مصفوفة ديناميكية تُعاد جدولتها (rehash) عند امتلائها.
- تجميع النتائج: أي حلقة تقرأ بيانات بحجم غير معروف مسبقاً (أسطر ملف، نتائج استعلام) تضعها عادةً في مصفوفة ديناميكية.
نصيحة عملية: احجز السعة مقدّماً
أكبر خطأ يقع فيه المبتدئ هو ترك المصفوفة تكبر مرة بعد مرة داخل حلقة ضخمة، فتتراكم عمليات إعادة التخصيص والنسخ. إذا كنت تعرف العدد التقريبي مسبقاً، احجز السعة دفعة واحدة:
- في ++C:
vec.reserve(1000); - في جافا:
new ArrayList<>(1000) - في #C:
new List<int>(1000)
هذا يلغي معظم عمليات إعادة التخصيص ويحسّن الأداء بشكل ملموس في الأكواد الحسّاسة. والخطأ المقابل: الاحتفاظ بمؤشّر (pointer) أو مرجع إلى عنصر داخل المصفوفة ثم الإضافة إليها؛ فقد تُعيد الإضافة تخصيص الذاكرة وتنقل العناصر إلى عنوان جديد، فيصبح مؤشّرك مُعلّقاً وغير صالح. هذه مشكلة شائعة تحديداً في ++C.
الأسئلة الشائعة
ما الفرق بين المصفوفة الديناميكية والمصفوفة العادية؟
المصفوفة العادية (الثابتة) يُحدَّد حجمها عند الإنشاء ولا يتغير، بينما الديناميكية تعيد حجز ذاكرة أكبر تلقائياً عند الحاجة. الديناميكية عملياً مبنية فوق مصفوفة ثابتة مع منطق يدير السعة نيابةً عنك.
هل تصغر السعة تلقائياً عند حذف العناصر؟
ليس دائماً. معظم اللغات لا تحرّر الذاكرة الزائدة تلقائياً عند الحذف حفاظاً على الأداء. إذا أردت تقليص السعة فعليك طلب ذلك صراحةً، مثل shrink_to_fit في ++C أو TrimExcess في #C.
هل الإضافة دائماً O(1)؟
لا، بل O(1) مُستهلَكة. الإضافة الواحدة قد تكلّف O(n) في لحظة إعادة التخصيص، لكن المتوسط على عدد كبير من العمليات يبقى ثابتاً بفضل مضاعفة السعة.
لماذا تُضاعَف السعة تحديداً؟
لأن نمو السعة بنسبة مئوية ثابتة (مثل الضِعف أو 1.5 ضِعف) هو ما يضمن أن يبقى متوسط تكلفة الإضافة O(1). لو زادت السعة بمقدار ثابت في كل مرة لأصبح المتوسط O(n)، وهو أداء سيّئ عند الأعداد الكبيرة.