بناء Dynamic Array !

المقدمة

اليوم سنبدأ سلسلة جديدة وهي عن هياكل البيانات Data Structures
سأحاول في هذه السلسلة أن أجعلك تفهم هذه الهياكل وتستطيع استخدامها بشكل عملي ومفيد
وليس فقط نظريات وتعريفات عامة

هذه السلسلة قد تكون طويلة وستتضمن عدة مقالات

قبل أن نبدأ أريدك أن تعرف أن هذه الهياكل أو الـ Data Structures سهلة وليس بها أي صعوبة كما تظن
وتعلمها سهل وبسيط لكن المعضلة التي يواجهها الكثيرون هي أنهم لا يعرفون متى وكيف يتم استخدامها

لذا أحب أن أوضح بعض النقاط الهامة ولما تحتاج إلى تعلم الـ Data Structures

1. ما هي الـ Data Structures ؟
   • الـ Data Structures هي هياكل تستخدم لتخزين وتنظيم البيانات بشكل منظم ومرتب وسهل الوصول إليها
     وهي تساعدك في حل المشاكل والمهام بشكل أسرع وأكثر فعالية
   • كل Data Structure تخزن وتتعامل مع البيانات بشكل مختلف ولها استخداماتها الخاصة
2. لماذا تحتاج إلى تعلم الـ Data Structures ؟
   • فكرة تعلم الـ Data Structures هي لتجعلك تفكر بكيفية حل مشكلة عن طريق تنظيم البيانات بشكل معين
   • تجعلك تعرف عندما تريد تنفيذ شيء ليعمل بطريقة معينة تستطيع حينها أن تختار أو تبني الـ Data Structure المناسبة لهذا الشيء
   • طبعًا تجعلك منفتح وتفتح لك أفق جديد في البرمجة وتجعلك تفهم الأمور بشكل أفضل وكل هذا الكلمات الرنانة
3. بعض اللغات تقدم لك الـ Data Structures جاهزة فلما تحتاج إلى تعلمها ؟
   • الاجابة ستكون نفس اجابة السؤال السابق، لكن ...
   • أحيانًا عليك أن تفهم كيف بنيت الأشياء لتستطيع فهمها بشكل أفضل وتستطيع استخدامها بشكل أفضل
   • وتسطيع أن تفاضل بينها وتعرف عيوب ومميزات كل منها وتستطيع اختيار الأنسب لمشكلتك
   • أيضًا ماذا إن أردت أن تعدل شيء أو تبنيها بشكل مختلف أو تضيف شيء جديد إليها ؟
   • وماذا لو كانت اللغة لا تقدم لك هذه الـ Data Structures الجاهزة ؟ أو التي تريدها ليست متوفرة ؟

سنبدأ سلسلتنا الجديد بالحديث عن الأراي Array لكننا هنا لن نتكلم عنها بشكل عام
بل سنحاول أن ننشئ الأراي بأنفسنا

أولًا نظرة على الـ Static Array

الأراي تعد من أبسط وأسهل الهياكل التي يمكن أن تتعلمها وبالطبع شرحنا كل شيء عنها في مقالة المصفوفات في البرمجة، Arrays !
لكن هنا سنتكلم بشكل مختلف عن الأراي وسنحاول بناءها بأنفسنا ونرى كيف يمكننا أن نحولها إلى Dynamic Array
الأراي التي تكون حجمها ثابتًا ولا يمكنك تغيره ولا يمكنك إضافة عناصر جديدة إليها أو حذف عناصر منها تسمى Static Array
أما الأراي التي يمكنك تغيير حجمها وإضافة وحذف العناصر منها فتسمى Dynamic Array وهي التي سنحاول بناءها

أولًا الأراي هي Data Structure تحتوي على عناصر متتالية في الذاكرة، بمعنى أنها تخزن العناصر في مكان واحد وبشكل متتالي
وهذا يعني أنه يمكن الوصول إلى أي عنصر في الأراي بسهولة وبسرعة فائقة O(1)

                        memory (RAM)
            ذاكرة الجهاز التي تخزن فيها البيانات
        +-----------------------------------------------+
        |                                               |
        |         index: [0] [1] [2] [3] [4]            |
        |         arr = {12, 16, 24, 25, 28}            |
        |                                               |
        +-----------------------------------------------+

هذا شكل تخيلي، لاحظ أنه طالما أن العناصر متتالية في الذاكرة فإنه يمكن الوصول إليها بسهولة
لأنه ببساطة العنصر الثالث منطقيًا سيكون العنصر الذي بعدي بثلاثة خانات

الأمر أشبه أنك تعيش في حي وكل البيوت متتالية ومرقمة، فإذا أردت الذهاب إلى جارك الثالث فقط تذهب إلى البيت الثالث بشكل مباشر
الأمر مشابه تمامًا في الأراي كل عنصر فيها يملك عنوانًا محدد في الذاكرة memory address ويكون بالنظام السادس عشري Hexadecimal

                        memory (RAM)
            ذاكرة الجهاز التي تخزن فيها البيانات
        +------------------------------------------+
        |                                          |
        |  index:    0     1     2     3     4     |
        |  arr:      12    16    24    25    28    |
        |  address: 0x100 0x104 0x108 0x10C 0x110  |
        |                                          |
        +------------------------------------------+

هذا شكل تخيلي آخر، لاحظ أن كل عنصر يملك عنوانًا محددًا في الذاكرة
ولاحظ أيضًا أن العناصر متتالية وبين كل عنصر وآخر فرق ثابت 4 وهو عدد الـ bytes التي يحتاجها كل عنصر للتخزين
لأن الأرقام الصحيحة int تحتاج 4 bytes للتخزين

حسنا إذا أردنا هنا الذهاب للـ index الثالث فقط نقوم بالتالي

index = 3
size = 4 bytes

address = 0x100 + (index * size)
address = 0x100 + (3 * 4)
address = 0x100 + 12
address = 0x10C

هكذا نحصل على عنوان العنصر الثالث في الأراي 0x10C وهو العنصر 25
هكذا سيتم الوصول إلى أي عنصر في الأراي خلف الكواليس

إذا كنت تتعامل مع لغة مثل C أو C++ فستعرف أن الأراي ما هي إلا مؤشر pointer يشير إلى عنوان معين في الذاكرة
والـ Pointer يمكنك تخيله كمؤشر يشير إلى مكان معين في الذاكرة

ملحوظة: على عكس بعض بعض السلاسل التي تقوم بشرح الـ Data Structures باستخدام لغة الـ C أو الـ C++ وتستخدم الـ Pointer للتعامل مع الذاكرة مباشرة
فأنا لن أقوم بذلك هنا، فلن أقوم بشرح Pointer لأنه متاح في لغات معينة فقط وليس في جميع اللغات وهذه السلسلة أريد أن تكون مفيدة للجميع ومركزة فقط على الـ Data Structures
بجانب ذلك الـ Pointer والتعامل مع الذاكرة مباشرة يكون خطيرًا وأنا لست الشخص المناسب لأقوم بشرحه والحديث عنه قد يحتاج إلى سلسلة من المقالات

لذلك في هذه السلسلة سنستخدم لغة TypeScript لتسهيل الأمور وتوضيحها بشكل أفضل دون الحاجة للـ Pointer

أولًا قبل أن نكمل لنأخذ نظرة بسيطة لمعرفة مما تتكون الأراي
في لغة الـ C أو الـ C++ إذا قمت بطباعة اسم الأراي فإنه سيعطيك عنوان العنصر الأول في الأراي

int arr[] = {12, 16, 24, 25, 28};

cout << arr; // 0x100

ستجده يطبع لك عنوان معين وهذا العنوان هو عنوان الـ index الأول في الأراي arr[0]
وهذا بسبب أن الأراي في الواقع ما هي إلا pointer يشير إلى عنوان معين في الذاكرة وهو عنوان أول عنصر في الأراي arr[0]

وإذا أردت قيمة هذا العنوان فقط قم بوضع * قبل اسم الأراي

cout << *arr; // 12

هكذا ستحصل على القيمة المتواجدة في هذا العنوان وهي 12 وهو العنصر الأول في الأراي

الأمر يمكنك تخيله هكذا:

        +--------+--------+--------+--------+--------+
        |   12   |   16   |   24   |   25   |   28   |
        +--------+--------+--------+--------+--------+
  arr -->  0x100    0x104    0x108    0x10C    0x110

حسنًا وإن أردت الذهاب إلى العنصر الذي يليه فقط قم بكتابة

cout << *(arr + 1); // 16

هكذا ستحصل على العنصر الثاني في الأراي وهو 16

        +--------+--------+--------+--------+--------+
        |   12   |   16   |   24   |   25   |   28   |
        +--------+--------+--------+--------+--------+
  arr -->  0x100    0x104    0x108    0x10C    0x110
          arr + 0  arr + 1  arr + 2  arr + 3  arr + 4

عندما تقوم بكتابة arr + 1 فإنه يعني أنك تريد الذهاب إلى العنصر الذي يليه وهو العنصر الثاني
بالتالي سيكون الناتج العنوان التالي وهو 0x104 لأن 0x100 + 4 byte = 0x104

وبعد ذلك نقوم بوضع * للحصول على قيمة العنصر الثاني في الأراي وهو 16

هكذا سيتم الوصول إلى أي عنصر في الأراي

ملحوظة: هذا بسبب أن الأراي في لغة الـ C أو الـ C++ هي Pointer والتي تشير عنوان في الذاكرة
ولكي تحصل على القيمة في هذا العنوان يجب عليك وضع * قبل الـ Pointer لتحصل على القيمة الموجودة في هذا العنوان الذي يشير إليه الـ Pointer

أظنك لمحت السر لماذا الـ index في الأراي يبدأ من الصفر دائمًا؟

من هذا الشكل الذي رأيناه سابقًا

        +--------+--------+--------+--------+--------+
        |   12   |   16   |   24   |   25   |   28   |
        +--------+--------+--------+--------+--------+
  arr -->  0x100    0x104    0x108    0x10C    0x110
          arr + 0  arr + 1  arr + 2  arr + 3  arr + 4

نستطيع تخيل الأراي والـ index بشكل مختلف وهو كالتالي

arr[0] = *(arr + 0)
arr[1] = *(arr + 1)
arr[2] = *(arr + 2)
arr[3] = *(arr + 3)
arr[4] = *(arr + 4)
... etc

هل عرفت السر ؟

طالما أن الأراي يحمل عنوان العنصر الأول فمنطقيًا أننا نستطيع الوصول إلى مباشرًة دون أن نجمع أي شيء
على عكس إذا أردنا الذهاب إلى العنصر الثاني كنا نضيف 1 للمؤشر وهكذا
لكن العنصر الأول فنحن لا نحتاج لإضافة شيء لأنه هو العنوان الأصلي الذي يقف عليه الأراي بالفعل

عيوب الـ Static Array

الـ Static Array ويطلق عليها أيضًا Fixed Array تعتبر بسيطة وسهلة الاستخدام وهي موجودة في معظم اللغات لكنها أيضًا لا تخلو من العيوب
من ضمن هذه العيوب:

• حجم الأراي ثابت: لا يمكنك تغيير حجم الأراي بعد إنشائها وهذا يعني أنه إذا كان حجم الأراي 10 فلا تستطيع تقليل أو زيادة بعد ذلك
• صعوبة إضافة عنصر جديد: لا يمكنك إضافة عنصر جديد إلى الأراي بسهولة لأن حجمها ثابت فالعناصر تكون ثابتة عند لحظة الإنشاء ولا يمكنك إضافة عنصر جديد إلى الأراي
• صعوبة حذف عنصر من الأراي: وبالمثل أيضًا لا يمكنك حذف عنصر من الأراي بسهولة
• تضيع الذاكرة: إذا كان حجم الأراي كبيرًا ولم تملأه بالكامل فإنه سيضيع الذاكرة لأنه يحجز مساحة كبيرة في الذاكرة ولكنك لا تستفيد منها

هذه بعض العيوب التي تواجهك عند استخدام الـ Static Array ولكن هذه العيوب يمكن تجاوزها بسهولة عند استخدام الـ Dynamic Array
لكن هذا لا يعني أن الـ Static Array لا تستخدم، بل تستخدم في العديد من الأمور والحالات ولكن عليك أن تعرف متى تستخدم الـ Static Array ومتى تستخدم الـ Dynamic Array
وأيضًا هذا لا يعني أن الـ Dynamic Array لا تحتوي على عيوب، بل لها عيوبها الخاصة والتي سنتعرف عليها فيما بعد

بناء الـ Dynamic Array

الآن بعد أن عرفنا الفرق بين الـ Static Array والـ Dynamic Array وعيوب الـ Static Array
لنلقي نظرة أونفكر كيف نستطيع بناء الـ Dynamic Array وكيف يمكننا تغيير حجم الأراي وإضافة وحذف العناصر منها بشكل ديناميكي
دون الحاجة للقلق من الحجم الثابت والعيوب التي تواجهنا عند استخدام الـ Static Array

الفكرة وما فيها أنك تنشيء الأراي بحجم معين وعندما تمتلئ الأراي تقوم بإنشاء أراي جديدة بحجم أكبر ونقوم بنقل العناصر من الأراي القديمة إلى الأراي الجديدة

قد تعتقد أنك هكذا تستهلك المزيد من الذاكرة وتضيعها ولكن هذا ليس صحيحًا
لأنك تنشيء أراي بحجم أكبر وتنقل العناصر القديمة إليها
لكن انتبه نحن نقوم بهذ فقط عندما تمتلئ الأراي وليس في كل مرة تقوم بإضافة عنصر جديد

لنرى كيف ننشيء الـ Dynamic Array خطوة خطوة ونرى العيوب والمميزات وتناقش فيها
لنقوم هنا ببناء العديد من الدوال ونتناقش في كل دالة وماذا تفعل وكيف تعمل

إنشاء الـ Dynamic Array

الـ Dynamic Array تستخدم الـ Static Array في بناءها وفي لغات مثل C أو C++ يمكنك استخدام الـ Pointer لبناء الـ Dynamic Array
لكن هنا سنستخدم لغة TypeScript لتسهيل الأمور وتوضيحها بشكل أفضل

class DynamicArray {
  private arr: number[];
  private size: number;
  private capacity: number;
}

هنا قمنا بإنشاء كلاس DynamicArray وقمنا بإنشاء ثلاثة خصائص لهذا الكلاس

• arr: هنا سيتم تخزين العناصر في الأراي
• size: هنا سيتم تخزين عدد العناصر الموجودة في الأراي
• capacity: هنا سيتم تخزين حجم الأراي

أنتظر ! ما الفرق بين size و capacity ؟

فكرة الـ Dynamic Array هي أنها تحتوي على حجم ثابت وهو ما يسمى بالـ capacity
والـ size هو عدد العناصر الموجودة في الأراي
ويمكنني أن ابسطها لك بأن تتخيل أنك لديك برميل يتسع لـ 10 لتر ولديك فيه 5 لتر فقط، فالـ capacity هو 10 والـ size هو 5
الـ capacity هو الحجم الذي يمكن أن يتسع له البرميل والـ size هو الحجم الذي يحتويه البرميل
والآن عندما يمتلئ البرميل أي يكون size مساويًا لـ capacity هنا يمكنك احضار برميل جديد بحجم أكبر ونقوم بنقل الماء من البرميل القديم إلى البرميل الجديد

هذه هي الفكرة الأساسية التي سنطبقها على الـ Dynamic Array
الـ capacity هو الحجم الذي يمكن أن يتسع له الأراي والـ size هو عدد العناصر الموجودة في الأراي
وعندما يكون size مساويًا لـ capacity هنا سنقوم بإنشاء أراي جديدة بحجم أكبر ونقوم بنقل العناصر من الأراي القديمة إلى الأراي الجديدة

class DynamicArray {
  private arr: number[];
  private size: number;
  private capacity: number;

  constructor(capacity: number = 1) {
    this.arr = new Array(capacity);
    this.size = 0;
    this.capacity = capacity;
  }
}

const dynamicArray = new DynamicArray();

هنا قمنا بإنشاء الـ constructor والذي يقوم بإنشاء الأراي بحجم معين وهو الـ capacity وقيمته الافتراضية هي 1 ويمكنك تغييرها إذا أردت طبعًا
ولاحظ أننا قمنا بإنشاء الأراي بحجم capacity وقمنا بتعيين الـ size بـ 0 لأنه في البداية لا يوجد عناصر في الأراي
بمعنى أن سعة الأراي هي 1 ولكن العناصر الموجودة فيها حاليًا هي 0

يمكنك تخيل الأمر هكذا:

capacity = 1
size = 0

                    +--------+
  dynamicArray -->  |        |
                    +--------+

إضافة عنصر للـ Dynamic Array

الآن بعد أن قمنا بإنشاء الـ Dynamic Array وقمنا بتحديد الـ capacity والـ size والأراي نفسها
نريد وسيلة لإضافة عنصر جديد إلى الأراي وهنا سنقوم بإنشاء دالة push لهذا الغرض والتي ستكون دالة بسيطة تقوم بإضافة عنصر جديد إلى الأراي

class DynamicArray {
  private arr: number[];
  private size: number;
  private capacity: number;

  constructor(capacity: number = 1) {
    this.arr = new Array(capacity);
    this.size = 0;
    this.capacity = capacity;
  }

  public push(value: number): void {
    // size treat as index
    this.arr[this.size] = value;
    this.size++;
  }
}

const dynamicArray = new DynamicArray();
dynamicArray.push(12);

هنا قمنا بإنشاء دالة push والتي تقوم بإضافة عنصر جديد إلى الأراي
لكن لاحظ أننا قمنا بإضافة العنصر في الـ index الذي يساوي size
هذا بسبب أن الـ size يعمل كـ index للعناصر في الأراي، في الواقع هو كأنه الـ index الأخير في الأراي

يمكنك تخيل الأمر هكذا:

capacity = 1
size = 0
         index:         0
                    +--------+
  dynamicArray -->  |        |
                    +--------+

dynamicArray.push(12)  --> arr[size] --> arr[0] = 12

capacity = 1
size = 1
         index:         0
                    +--------+
  dynamicArray -->  |   12   |
                    +--------+

لاحظ في الشكل السابق أننا قمنا بإضافة العنصر 12 في الـ index الذي كان يساوي size وهو 0 والذي كان index لأخر عنصر في الأراي

زيادة حجم الـ Dynamic Array

لاحظ أننا قمنا بإضافة عنصر جديد إلى الأراي ولكن ماذا لو أردنا إضافة عنصر آخر؟

const dynamicArray = new DynamicArray();
dynamicArray.push(12);
dynamicArray.push(16);

هنا قمنا بإضافة عنصرين إلى الأراي ولكن هناك مشكلة وهي أن الأراي تحتوي على عنصرين ولكن الـ capacity لا تزال 1
بالتالي سيحدث مشكلة عند إضافة العنصر الثاني لأن الـ size سيكون 1 والـ capacity سيكون 1 وهذا يعني أن الأراي ممتلئة ولا يمكن إضافة عنصر جديد

capacity = 1
size = 1
         index:         0        1
                    +--------+
  dynamicArray -->  |   12   |   ?
                    +--------+

dynamicArray.push(16)  --> arr[size] --> arr[1] = 16 // Error

هنا مشكلة تحتاج لحل
تتذكر مثال البرميل عندما قلنا أنه عندما يمتلئ البرميل يمكننا إحضار برميل جديد بحجم أكبر ونقوم بنقل الماء من البرميل القديم إلى البرميل الجديد
هنا نريد عمل المثل وهو عندما تمتلئ الأراي نقوم بإنشاء أراي جديدة بحجم أكبر ونقوم بنقل العناصر من الأراي القديمة إلى الأراي الجديدة

class DynamicArray {
  // ...
  public push(value: number): void {
    // if the array is full then create a new array with double the size
    if (this.size == this.capacity) {
      this.capacity *= 2;
      const newArr = new Array(this.capacity);
      for (let i = 0; i < this.size; i++) {
        newArr[i] = this.arr[i];
      }
      this.arr = newArr;
    }

    this.arr[this.size] = value;
    this.size++;
  }
  // ...
}

هنا قمنا بإضافة شرط يقوم بالتحقق إذا كانت الأراي ممتلئة أم لا if (this.size == this.capacity)
وإذا كانت الأراي ممتلئة فسنقوم بإنشاء أراي جديدة بحجم أكبر لنقل الضعف this.capacity *= 2 يمكنك هنا تغيير القيمة 1.5 أو 3 أو أي قيمة تريدها لكن القيمة الشائعة هي ضعف الحجم

ثم لاحظ أننا ننشيء أراي جديدة بالحجم الجديدة const newArr = new Array(this.capacity)
ثم نقوم بعمل loop على الحجم القديم وهو this.size ونقوم بنقل العناصر من الأراي القديمة إلى الأراي الجديدة
ثم في النهاية نقوم بتعيين الأراي الجديدة إلى الأراي القديمة

هكذا عندما تمتلئ الأراي سيتم إنشاء أراي جديدة بحجم أكبر ونقوم بنقل العناصر من الأراي القديمة إلى الأراي الجديدة

          +--------+
  old --> |   12   |
          +--------+
              |
              | copy
              v
          +--------+--------+
  new --> |   12   |        |
          +--------+--------+

الآن عندما ننشئ الأراي ونضيف العنصر الأول والعنصر الثاني

dynamicArray.push(12);
dynamicArray.push(16);

عندما نقوم بإضافة العنصر الثاني سيتم زيادة حجم الأراي إلى 2 وسيتم نقل العنصر الأول إلى الأراي الجديدة كما هو شرحنا سابقًا

capacity = 2
size = 2
                    +--------+--------+
  dynamicArray -->  |   12   |   16   |
                    +--------+--------+

الآن يمكنك إضافة عنصر آخر وسيتم زيادة حجم الأراي إلى 4 وهكذا

dynamicArray.push(24);

capacity = 4
size = 3
                    +--------+--------+--------+--------+
  dynamicArray -->  |   12   |   16   |   24   |        |
                    +--------+--------+--------+--------+

هكذا يمكنك إضافة عناصر إلى الأراي بدون الحاجة للقلق لأن الأراي ستزيد حجمها تلقائيًا عندما تمتلئ

تحليل متى يتم نقل عناصر الأراي القديمة إلى أراي جديدة

لكن أليس نقل العناصر من الأراي القديمة إلى الأراي الجديدة مكلف في الأداء والسرعة ؟

عندما تنظر إلى دالة push ستجد أنها تقوم بعمل loop على الأراي القديمة وتقوم بنقل العناصر إلى الأراي الجديدة
وستظن للوهلة الأولى أنها هكذا ستكون بطيئة و O(n) ولكن هذا ليس صحيحًا

لأننا لا نقوم بنقل العناصر في كل مرة تقوم بإضافة عنصر جديد
بل نقوم بنقل العناصر فقط عندما تمتلئ الأراي وهذا لن يحدث كثيرًا

لنرى الجدول التالي الذي يوضح كم مرة يتم نقل العناصر بالنسبة لعدد العناصر الموجودة في الأراي

كما ترى في الجدول أن عدد مرات نقل العناصر نادر جدا ولن يحدث كثيرًا
حيث لو أنشأنا أراي جديدة أي حجمها 1 ثم أضفنا ألفين عنصر بشكل متتالي فسيتم نقل العناصر 10 مرات فقط
ولو أضفنا إثنين مليون عنصر فسيتم نقل العناصر 20 مرة فقط
وإذا نقلت إثنين مليار عنصر فسيتم نقل العناصر 30 مرة تقريبًا فقط

هنا لا نستطيع أن نقول أبدًا أن هذا سيكون بطيئًا لأن عملية نقل العناصر تحدث بشكل نادر تكاد تكون غير ملحوظة
لذا نستطيع القول أن دالة push ستكون سريعة حيث يمكنك القول أنها O(1)

القليل من مبدأ الـ Single Responsibility

الآن لاحظ أن دالة push بها implementation لشيئين وهما الإضافة وزيادة حجم الأراي

class DynamicArray {
  // ...
  public push(value: number): void {
    if (this.size == this.capacity) {
      this.capacity *= 2;
      const newArr = new Array(this.capacity);
      for (let i = 0; i < this.size; i++) {
        newArr[i] = this.arr[i];
      }
      this.arr = newArr;
    }

    this.arr[this.size] = value;
    this.size++;
  }
  // ...
}

وهذا يخالف أحد مبادئ الـ SOLID وهو Single Responsibility Principle
لذا نستطيع تقسيم هذه الدالة إلى دالتين واحدة تقوم بالإضافة والأخرى تقوم بزيادة حجم الأراي

class DynamicArray {
  // ...
  public push(value: number): void {
    if (this.size == this.capacity) {
      this.increaseCapacity();
    }

    this.arr[this.size] = value;
    this.size++;
  }

  private increaseCapacity(): void {
    this.capacity *= 2;
    const newArr = new Array(this.capacity);
    for (let i = 0; i < this.size; i++) {
      newArr[i] = this.arr[i];
    }
    this.arr = newArr;
  }
  // ...
}

هكذا أصبحت الدالة push تقوم بالإضافة فقط والدالة increaseCapacity تقوم بزيادة حجم الأراي
ودالة push تقوم فقط باستدعاء دالة increaseCapacity عندما تحتاجها فقط دون أن تشغل بالها بمسؤولية تفاصيل زيادة حجم الأراي كما كانت تفعل
الآن مسؤولية زيادة حجم الأراي أصبحت بحوزة الدالة increaseCapacity فقط ومن يريدها فسيستدعيها

هذا ما يعرف بمبدأ Single Responsibility Principle وهو أحد مبادئ الـ SOLID والذي يقول أن كل دالة يجب أن تقوم بمسؤولية واحدة فقط

ملحوظة عن الـ Garbage Collection في بعض اللغات

أخر شيء وهو فكرة الـ Garbage Collection
عندما نقوم بإنشاء أراي جديدة ونقوم بنقل العناصر من الأراي القديمة إلى الأراي الجديدة
تظل الأراي القديمة كما هي في الذاكرة ولم يتم حذفها وهذا يعني أنها تضيع الذاكرة

هنا يأتي دور الـ Garbage Collection والذي يقوم بحذف الأراي القديمة بعد أن تأكد أنها لم تعد مستخدمة ولم يعد هناك أي مراجعات لها
وهناك العديد من اللغات التي تدعم خاصية الـ Garbage Collection وتقوم بحذف الأشياء التي لم تعد مستخدمة مثل JavaScript و TypeScript و Java وغيرها

لكن بعض اللغات لا تدعم الـ Garbage Collection وعليك أن تقوم بحذف الأشياء يدويًا بنفسك لذا عليك أن تعرف هذا الأمر جيدًا وتعرف هل اللغة التي تستخدمها تدعم هذا الأمر أم لا
مثل لغة C و C++ لا تدعم الـ Garbage Collection وعليك أن تقوم بحذف الأشياء يدويًا بنفسك
لذا في دالة increaseCapacity عندما تحاول بناءها في لغة C++ سيكون شكلها هكذا

class DynamicArray {
  // ...
  void increaseCapacity() {
    this->capacity *= 2;
    int* newArr = new int[this->capacity];
    for (int i = 0; i < this->size; i++) {
      newArr[i] = this->arr[i];
    }
    delete[] this->arr; // delete the old array from the memory
    this->arr = newArr;
  }
  // ...
};

هنا في لغة C++ قمنا بحذف الأراي القديمة من الذاكرة يدويًا باستخدام delete[] this->arr

حذف عنصر من نهاية الـ Dynamic Array

تتذكر دالة push التي قمنا بإنشائها والتي تقوم بإضافة عنصر جديد إلى الأراي من نهاية الأراي
سنقوم ببناء أختها الصغرى وهي دالة pop والتي تقوم بحذف عنصر من نهاية الأراي

وفكرتها أنها تقوم بحذف العنصر الأخير من الأراي وتقوم بتقليل الـ size بـ 1
لذا كل ما عليك فعله هو تقليل الـ size بـ 1 هكذا كأنك تقوم بحذف العنصر الأخير

class DynamicArray {
  // ...
  public pop(): number {
    if (this.size == 0) {
      throw new Error('Array is empty');
    }

    this.size--;
    return this.arr[this.size];
  }
  // ...
}

بالطبع يجب أن نتأكد أن الأراي ليست فارغة وإلا سيتم رمي Exception
كيف تحذف عنصر في أراي فارغة من الأساس ؟

الآن كما تلاحظ كل ما فعلناه هو تقليل الـ size بـ 1 وإرجاع العنصر الأخير

لتوضيح عملية الحذف بشكل أفضل، دعونا نرسم شكلاً توضيحياً:

capacity = 4
size = 4
              0        1        2        3
          +--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |
          +--------+--------+--------+--------+

pop() --> size = size - 1 ---> size = 3

capacity = 4
size = 3

              0        1        2
          +--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |        |
          +--------+--------+--------+--------+

لاحظ أننا هنا عندما أردنا أن نحذف العنصر الأخير من الأراي فأننا فقط قمنا بتقليل الـ size بـ 1
كأننا نقول أن العنصر الأخير خرج من حدود الأراي
كأنه خرج من حسبة الـ size وبالطبع الـ capacity لم يتغير ولا تزال تساوي 4
لذا يمكنك أن تقول أن حجم الأراي لم يتغير ولكن الأراي لم تعد تحتوي على العنصر الأخير

لكن لماذا نرجع العنصر الأخير بعد حذفه ؟

بصراحة لا يوجد سبب معين يمكنك أن ترجع العنصر الأخير أو لا ترجع أي شيء
الأمر يعود لك ولماذا تريد أن ترجع العنصر الأخير أو لا ترجع شيء
لكن الخيار الأكثر شيوعًا هو أن ترجع العنصر الأخير لأنه يمكن أن يكون مفيدًا في بعض الأحيان

تقليل حجم الـ Dynamic Array

هنا لدينا فكرة وهي أننا عندما نحذف عنصر من نهاية الأراي فإننا نقوم بتقليل الـ size بـ 1
ماذا يحدث إذا حذفنا العديد من عناصر الأراي ؟
بمعنى لنترض أن الـ capacity كانت 100 قمنا بحذف 90 عنصر من الأراي الآن الـ size ستكون 10 والـ capacity ستكون 100
هنا الأراي تحتوي على 10 عناصر فقط واصبح لدينا 90 خانة فارغة غير مكتملة

لما نحتفظ بـ 90 خانة فارغة غير مكتملة ؟
لما لا نضع عناصر الأراي في أراي أصغر بحجمها الحالي ؟
عكس ما كنا نفعله عندما نزيد حجم الأراي نقوم بنقل العناصر من الأراي القديمة إلى الأراي الجديدة
الآن نريد تقليل حجم الأراي

هنا سنقوم بإنشاء دالة decreaseCapacity والتي تقوم بتقليل حجم الأراي إلى الـ size الحالي

class DynamicArray {
  // ...
  private decreaseCapacity(): void {
    this.capacity = this.size;
    const newArr = new Array(this.capacity);
    for (let i = 0; i < this.size; i++) {
      newArr[i] = this.arr[i];
    }
    this.arr = newArr;
  }
  // ...
}

لاحظ أن دالة decreaseCapacity تقوم بتقليل الـ capacity إلى نفس حجم الـ size الحالي وتقوم بإنشاء أراي جديدة بحجم الـ size الحالي وتقوم بنقل العناصر من الأراي القديمة إلى الأراي الجديدة

لكن السؤال يكرر نفسه متى سيتم تنفيذ هذه الدالة ؟
تذكر أن دالة increaseCapacity تنفذ عندما تمتلئ الأراي وتحتاج لزيادة حجمها
لكن هنا مع دالة decreaseCapacity متى سيتم تنفيذها ؟

الاجابة بسيطة وهي عندما يكون الـ size أقل من نصف حجم الـ capacity

class DynamicArray {
  // ...
  public pop(): number {
    if (this.size == 0) {
      throw new Error('Array is empty');
    }

    const deletedValue = this.arr[this.size - 1];
    this.size--;

    if (this.size < this.capacity / 2) {
      this.decreaseCapacity();
    }

    return deletedValue;
  }
  // ...
}

هنا قمنا بإضافة شرط جديد يقوم بالتحقق إذا كان الـ size أقل من نصف الـ capacity فسيتم تنفيذ دالة decreaseCapacity

لنرى شكل تخيلي لهذه الدالة

capacity = 10
size = 4
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  old --> |   12   |   16   |   24   |   32   |        |         |        |         |       |       |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
              |        |        |        |
              |        |        |        |
              v        v        v        v
          +--------+--------+--------+--------+
  new --> |   12   |   16   |   24   |   32   |
          +--------+--------+--------+--------+

capacity = 4 // new capacity
size = 4

كما ترى في الشكل السابق عندما وصل عدد العناصر في الأراي إلى 5 وهو أقل من نصف الـ capacity
تم تنفيذ دالة decreaseCapacity وتم تقليل حجم الأراي إلى 4 وتم نقل العناصر من الأراي القديمة إلى الأراي الجديدة

بالطبع عندما يزيد يتم إضافة عنصر جديد إلى الأراي سيتم تنفيذ increaseCapacity وسيتم زيادة حجم الأراي مرة أخرى إلى 8 وهكذا ثم 16 ثم 32 وهكذا

تتذكر الجدول الذي قمنا بإنشائه سابقًا والذي يوضح عدد مرات نقل العناصر بالنسبة لعدد العناصر الموجودة في الأراي ؟
دالة pop سينطبق عليها نفس الشيء بمعنى أنه لن سيتم تنفيذ decreaseCapacity في كل مرة تقوم بحذف عنصر من الأراي بل سيتم تنفيذها مرة واحدة فقط عندما يكون الـ size أقل من نصف الـ capacity

لذا هنا مثل الـ increaseCapacity لن يتم تنفيذها كثيرًا ولن تلاحظ أنها تنفذ كثيرًا
بالتالي لا تقلق من أداء الدالة decreaseCapacity لأنها لن تنفذ كثيرًا بل في الواقع دالة pop ستكون سريعة جدًا بل ستكون O(1) مثلها مثل دالة push

احضار عنصر من الـ Dynamic Array

حسنًا بعد ما أنشأنا الأراي وأضفنا العناصر إليها وزيادة حجم الأراي وغيرها من الأمور الآن نريد أن نحضر عنصر من الأراي وهنا سنقوم بإنشاء دالة get تقوم بإحضار العنصر من الأراي
يمكنك أن تسمي الدالة كما تشاء بعض اللغات تستخدم get وبعضها تستخدم at وبعضها تستخدم elementAt وهكذا

class DynamicArray {
  // ...
  public get(index: number): number {
    if (index < 0 || index >= this.size) {
      throw new Error('Index out of range');
    }

    return this.arr[index];
  }
  // ...
}

هنا قمنا بإنشاء دالة get والتي تقوم بإحضار العنصر من الأراي بالـ index المحدد
لكن طبعًا يجب أن نراعي أن الـ index لا يتعدى حدود الأراي
بالتالي قمنا بإضافة شرط يقوم بالتحقق إذا كان الـ index أقل من 0 أو أكبر من size فسيتم رمي Exception

دالة بسيطة وسهلة ولا يوجد بها شيء معقد أو كلام كثير يقال عنها

تعديل قيمة عنصر في الـ Dynamic Array

الآن بعد أن قمنا بإحضار العنصر من الأراي نريد أن نقوم بتعديل قيمة أي عنصر في الأراي
سواء كان في البداية أو في النص أو في النهاية

class DynamicArray {
  // ...
  public set(index: number, value: number): void {
    if (index < 0 || index >= this.size) {
      throw new Error('Index out of range');
    }

    this.arr[index] = value;
  }
  // ...
}

الأمر مشابه للـ get ولكن هنا نقوم بتعديل قيمة لذا دالة set هنا تقوم بأخذ index و value وتقوم بتعديل القيمة في الـ index المحدد
بالطبع يجب أن نتأكد أن الـ index لا يتعدى حدود الأراي وإلا سيتم رمي Exception مثل ما فعلنا في الـ get

استراحة قصيرة

الآن انتهينا من الدوال الأساسية
وهي push و pop و get و set وهي أننا الآن نستطيع أن نضيف ونحذف ونحصل على العناصر ونقوم بتعديل قيمتها
بالطبع هناك دوال مساعدة مثل increaseCapacity و decreaseCapacity نستخدمها بشكل داخلي في الأراي وليس من المستخدم

هناك أيضًا دوال صغيرة نسينا أن نبنيها وهي مهمة جدًا مثل isEmpty و isFull و getCapacity و getSize

class DynamicArray {
  // ...
  public isEmpty(): boolean {
    return this.size == 0;
  }

  public isFull(): boolean {
    return this.size == this.capacity;
  }

  public getCapacity(): number {
    return this.capacity;
  }

  public getSize(): number {
    return this.size;
  }
  // ...
}

الآن أصبح لدينا Dynamic Array تقوم بما نريده بشكل سلسل وبسرعة وأداء عالي وممتاز
لكن هل هذا كل شيء ؟ هل فعلا الـ Dynamic Array هي الأفضل ؟ والخالية من العيوب والحل المثالي لكل مشاكلنا ؟

الإجابة بالطبع ... لا

هناك بعض الدوال التي لم ننشئها بعد وتعد أهم شيء وهي التي تحدث الفارق
وهي امكانية إضافة وحذف عناصر من منتصف أو أول الأراي

دعونا نحاول بناءها ونرى عيوبها ونتناقش فيها

إضافة عنصر في أي مكان في الـ Dynamic Array

لنبدأ بإنشاء دالة تسمى insertAt والتي ستقوم بإضافة عنصر في index معين داخل الأراي وهذه الدالة ستأخذ index وقيمة value
لنفكر قليلًا كيف يمكننا أن نقوم بإضافة عنصر في منتصف الأراي ؟ أو في أي مكان آخر ؟

لنفترض أننا نملك الأراي التالية:

capacity = 10
size = 5
              0        1        2        3        4
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   48   |        |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

ونريد أن نضيف القيمة 40 في الـ index رقم 2
لكن الـ index رقم 2 تحتوي على قيمة بالفعل، ماذا نفعل هل نستبدلها أم ماذا ؟
لا لن نستبدلها لأننا نريد إضافة قيمة وليس استبدال أو تغير قيمة
لذا لكي نضع القيمة 40 في الـ index رقم 2 يجب أن نقوم بنقل العناصر التي على يمين الـ index رقم 2 بمقدار 1 لليمين
يعني نقوم بازاحة العناصر نحو اليمين

capacity = 10
size = 5
              0        1        2        3        4
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   48   |        |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

insertAt(2, 40)
1 - Move all elements that after index 2 to the right
2 - Put 40 in the index 2

                                            (1)
                                 --- Move to the right --->
              0        1        2  --->  3  --->  4  --->  5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   24   |   32   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

                          (2) Put 40 here
                                |
                                v
              0        1        2        3        4       5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   40   |   24   |   32   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

capacity = 10
size = 6

لاحظ أننا عندما قمنا بإضافة القيمة 40 في الـ index رقم 2 قمنا أولًا بنقل العناصر التي على يمين الـ index رقم 2 بمقدار 1 لليمين
ثم قمنا بوضع القيمة 40 في الـ index رقم 2

هذا ما سنفعله داخل الدالة insertAt

class DynamicArray {
  // ...
  public insertAt(index: number, value: number): void {
    if (index < 0 || index > this.size) {
      throw new Error('Index out of range');
    }

    if (this.size == this.capacity) {
      this.increaseCapacity();
    }

    for (let i = this.size; i > index; i--) {
      this.arr[i] = this.arr[i - 1];
    }

    this.arr[index] = value;
    this.size++;
  }
  // ...
}

تقريبًا كل شيء داخل الدالة مفهوم وبسيط ما عادا الـ for loop التي قد يستصعبها البعض
لذا سنتفقدها ونرى ما الذي تفعله لأنها لب الدالة وهي المسؤولة عن ازاحة العناصر نحو اليمين

ستلاظ أولًا أنها تبدأ من الـ index الأخير وهو الـ this.size وتنتهي عند الـ index الذي تريد الإضافة فيه
بالتالي تظل تنقص الـ i بـ 1 حتى تصل إلى الـ index الذي تريد الإضافة فيه
ومع كل لفة تقوم بنقل العنصر الذي في الـ index السابق وهو arr[i - 1] إلى الـ index الحالي وهو arr[i]

لنرى كيف يتم هذا خطوة خطوة بشكل توضيحي

أولًا لدينا الأراي التالية:

capacity = 10
size = 5
              0        1        2        3        4
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   48   |        |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

ونريد الآن أن نضيف القيمة 40 في الـ index رقم 2 لذا سنستدعي الدالة insertAt(2, 40)

الآن سنحلل الخطوات التي ستتخذها الـ for loop لفة لفة
أولًا بالطبع قيمة i ستكون 5 والـ index الذي نريد الإضافة فيه هو 2
لذا سنبدأ باللفة الأولى
كل ما سنقوم به هو تنفيذ الكود التالي arr[i] = arr[i - 1] والذي سنقل العنصر نحول اليمين
بمعنى أنه طالما i قيمتها الحالية بـ 5 فسنقوم بنقل القيمة arr[4] إلى الـ index الذي يليه وهو arr[5]

i = size = 5
index = 2
                                                           i
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   48   |        |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

arr[i] = arr[i - 1] ---> arr[5] = arr[4] ---> arr[5] = 48

                                                           i
              0        1        2        3        4  --->  5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   48   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

كما ترى في الرسمة السابقة تم نقل القيمة 48 إلى الـ index الذي يليه وهو 5
الآن نحتاج لانقاص قيمة i ليذهب إلى 4 ونقل القيمة 32 إلى الـ index الذي يليه وهو 4 وهكذا

i--
i = 4
index = 2
                                                  i
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   48   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

arr[i] = arr[i - 1] ---> arr[4] = arr[3] ---> arr[4] = 32

                                                  i
              0        1        2        3  --->  4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   32   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

وهكذا في اللفة الثانية بما أن i ذهب إلى 4 كل ما فعلناه هو تنفيذ الكود arr[i] = arr[i - 1] مجددًا arr[4] = arr[3]
وبالتالي تم نقل القيمة 32 التي كانت في arr[3] إلى arr[4]

الآن نكرر العملية وننقص قيمة i ليساوي 3

i = 3
index = 2
                                         i
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   32   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

arr[i] = arr[i - 1] ---> arr[3] = arr[2] ---> arr[3] = 24

                                         i
              0        1        2  --->  3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   24   |   32   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

تم نقل القيمة 24 التي كانت في arr[2] إلى arr[3]
ثم نكرر العملية وننقص قيمة i ليساوي 2

i = 2
index = 2

i == index --> exit the loop

              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   24   |   32   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

هنا تنتهي الـ for loop لأن i أصبح يساوي الـ index الذي نريد الإضافة فيه وهو 2
ولاحظ أن كل العناصر تم ازاحتها نحو اليمين بالفعل
الآن يمكننا بكل آمان اسناد القيمة 40 التي نريدها في الـ index رقم 2

arr[index] = value ---> arr[2] = 40
size++

size = 6
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   40   |   24   |   32   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

capacity = 10
size = 6

هذا ما يحدث داخل الدالة insertAt وهي تقوم بنقل العناصر نحو اليمين وتضع القيمة في الـ index المحدد
أرجو أن يكون الرسومات وضحت سير العملية
ستلاحظ أن في كل لفة من الـ for loop يتم نقل العنصر الذي في الـ index السابق إلى الـ index الحالي كما تلاحظ هنا arr[i] = arr[i - 1]
ثم يتم انقاص قيمة الـ i لينقل العنصر التالي وهكذا حتى يصل إلى الـ index المحدد ثم يخرج من الـ for loop ويضع القيمة في الـ index المحدد
ثم بالطبع يزيد الـ size بـ 1

حذف عنصر من أي مكان في الـ Dynamic Array

الآن بعد أن قمنا بإضافة عنصر في أي مكان في الأراي نريد أن نقوم بحذف عنصر من أي مكان في الأراي
لنفكر قليلًا كيف يمكننا أن نقوم بحذف عنصر من الأراي ؟ الأمر مشابه إلى حد كبير للدالة السابقة
لكن هنا الدالة والتي سنسميها deleteAt ستقوم بأخذ index وحذف العنصر الموجود في الـ index المحدد والدالة كل ما ستفعله هي نقل العناصر نحو اليسار بدلاً من اليمين

لنفترض أننا نملك الأراي التالية:

capacity = 10
size = 6
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   40   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

ولنفترض أننا نريد حذف العنصر في الـ index رقم 2

لحذف هذا العنصر، سنقوم بالخطوات نقل جميع العناصر التي تلي الـ index رقم 2 نحو اليسار بمقدار واحد
وبالطبع نقوم بتقليل الـ size بمقدار 1 لأننا قمنا بحذف عنصر

دعونا نرى كيف ستبدو هذه العملية:

capacity = 10
size = 6
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   40   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

deleteAt(2)

1 - Move all elements after index 2 to the left
2 - Decrease size by 1

                                            (1)
                                 <--- Move to the left ---
              0        1        2  <---  3  <---  4  <---  5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   32   |   40   |   48   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

(2) Decrease size by 1

capacity = 10
size = 5
              0        1        2        3        4
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   32   |   40   |   48   |        |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

الآن، دعونا نقوم بتنفيذ هذه العملية في الكود، سنقوم بإنشاء دالة تسمى deleteAt والتي ستأخذ الـ index التي ستحذفه

class DynamicArray {
  // ...
  public deleteAt(index: number): void {
    if (index < 0 || index >= this.size) {
      throw new Error('Index out of range');
    }

    for (let i = index; i < this.size - 1; i++) {
      this.arr[i] = this.arr[i + 1];
    }

    this.size--;

    if (this.size < this.capacity / 2) {
      this.decreaseCapacity();
    }
  }
  // ...
}

كالعادة كل شيء واضح لكن الـ for loop قد يستصعبها بعض الأشخاص في تتبعها أو تخيلها

لكن أشك أنك استوعبتها بمجرد قراءها واستطعت تخيلها بسبب الشرح السابق
لكن الفرق أنها تزيح العناصر نحو اليسار بدلاً من اليمين

لنرى كيف تعمل هذه الـ for loop خطوة بخطوة بشكل توضيحي
لنتخيل أننا نريد حذف العنصر الذي في الـ index رقم 2 لذا سنقوم بتنفيذ الدالة deleteAt(2)

تذكر أن الأراي الحالية كالتالي:

capacity = 10
size = 6
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   24   |   32   |   40   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

في اللفة الأولى قيمة i ستبدأ من 2 وهو الـ index الذي نريد حذفه
ثم سنقوم بنقل القيمة arr[i] إلى arr[i + 1] حتى تصل إلى أخر عنصر في الأراي

i = 2
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   32   |   32   |   40   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
                                ٨        ٨
                                |        |
                              arr[i] = arr[i+1]

الآن في اللفة الأولى كما تلاحظ عندما كانت قيمة i تساوي 2 قمنا بنقل القيمة arr[i] إلى arr[i + 1] وهذا يعني أن القيمة arr[3] ستصبح arr[2]
الآن كما تلاحظ القيمة arr[2] قيمتها اصبحت 32 بدلاً من 24 القيمة التي كانت فيها من قبل
هكذا كأننا حذفنا القيمة القديمة 24 وقمنا بنقل القيمة 32 التي كانت على يمينها arr[3] إليها

الآن نزيد قيمة i لتتصبح 3 ونكمل اللفة التالية وازاحة بقية العناصر نحو اليسار

i = 3
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   32   |   40   |   40   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
                                          ٨        ٨
                                          |        |
                                        arr[i] = arr[i+1]

لاحظ أن القيمة arr[3] قيمتها اصبحت 40 بدلاً من 32 القيمة التي كانت فيها من قبل
الآن نزيد قيمة i لتتصبح 4 ونكمل اللفة التالية

i = 4
              0        1        2        3        4        5
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   32   |   40   |   48   |   48   |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
                                                  ٨        ٨
                                                  |        |
                                                arr[i] = arr[i+1]

الآن قمنا بنقل القيمة arr[4] إلى arr[3] وهكذا
الآن قمنا بنقل كل القيم التي كانت على يمين الـ index رقم 2 نحو اليسار
وهنا تكون الـ for loop قد انتهت وصلت لنهايتها لأن i في اللفة التالي ستساوي size - 1

الآن الانتهاء من نقل العناصر نقوم بانقاص قيمة الـ الـ size بـ 1 لأننا قمنا بحذف عنصر

size--
size = 5
              0        1        2        3        4
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  arr --> |   12   |   16   |   32   |   40   |   48   |        |        |        |        |        |
          +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

عيوب الدالتين insertAt و deleteAt

الآن بعد أن قمنا ببناء الدالتين insertAt و deleteAt وتعرفنا على كيفية عملهما وكيفية تنفيذهما
نأتي الآن للحديث عن بعض العيوب التي بهما

أظن أنك بالفعل استنتجت مبكرًا ما الذي سأقوله تاليًا
برغم من أن الـ Dynamic Array تعتبر حلاً جيدًا وفعالًا لمشكلة الـ Static Array
وتبدو بأنها الحل المثالي لكي شيء إلا أن عملتي إضافة أو حذف عناصر من منتصف الأراي مكلف جدًا

لأن كلتا الدالتين تقومان بنقل وعمل ازاحة لكل العناصر في كل مرة تريد إضافة أو حذف عنصر
لنتخيل أنك تريد لديك أراي مكونة من 100 عنصر
وتريد إضافة عنصر في بداية الأراي في الـ index رقم 0
ستقوم حينها بعمل for loop تلف 100 لفة لتزيح 100 عنصر وتنقلهم
ولو أردنا إضافة 10 عناصر ؟ سنكرر الـ for loop عدد 10 مرات بمعنى 1000 لفة
ونفس الأمر ينطبق على الحذف

لذا هذه العملية تعتبر مكلفة جدًا وتأخذ وقت طويل للقيام بها
ونقول أن دالة insertAt و deleteAt هكذا يعتبران O(n) حيث n هو عدد العناصر في الأراي
وهذا يعني أن الوقت الذي تستغرقه الدالتين يتناسب بشكل مباشر مع عدد العناصر في الأراي

فلو كان عدد العناصر 10000 فستحتاج لكيف تضيف أو تحذف عنصر إلى عشر ألف لفة في كل مرة

الختام

هذا كل شيء أود شرحه لك عن الـ Dynamic Array
الآن لديك فهم جيد لكيفية عمل الـ Dynamic Array وكيف يمكنك بناءه بنفسك
وتعرف كيف فكر الآخرون في حل مشكلة الـ Array الثابتة وكيف تمكنوا من تحسينها وتطويرها
وكيف توصلوا إلى بناء الـ Dynamic Array الذي يعتبر حلاً سهلًا وبسيطًا وفعالًا لمشكلة الـ Static Array التقليدية

وتعلمنا وبنينا دوال مختلفة تساعدنا على تحقيق الهدف

الغرض والفائدة التي أريدك أن تخرج منها أنك اصبحت تفكر في كيفية بناء شيء ما يساعدك في حل مشكلة كانت لديك
بالطبع لا يوجد شيء مثالي وعرفنا عيوب الـ Dynamic Array برغم من كل مميزاتها

بالطبع في المقالات التالية سنتعرف ونبني Data Structure مختلفة عن الـ Dynamic Array وتتغلب على العيوب التي لديها وبالطبع مع بعض العيوب

عليك أن تعرف أن معظ اللغات البرمجية تأتي مع الـ Dynamic Array مدمجة فيها
مثل ArrayList في Java و vector و array في C++
وفي لغة JavaScript لدينا الـ Array الاعتيادية الخاصة بها تعتبر Dynamic Array