بناء Dynamic Array !
السلام عليكم ورحمة الله وبركاته
الفهرس
- المقدمة
- أولًا نظرة على الـ Static Array
- عيوب الـ Static Array
- بناء الـ Dynamic Array
- إنشاء الـ Dynamic Array
- إضافة عنصر للـ Dynamic Array
- زيادة حجم الـ Dynamic Array
- تحليل متى يتم نقل عناصر الأراي القديمة إلى أراي جديدة
- القليل من مبدأ الـ Single Responsibility
- ملحوظة عن الـ Garbage Collection في بعض اللغات
- حذف عنصر من نهاية الـ Dynamic Array
- تقليل حجم الـ Dynamic Array
- احضار عنصر من الـ Dynamic Array
- تعديل قيمة عنصر في الـ Dynamic Array
- استراحة قصيرة
- إضافة عنصر في أي مكان في الـ Dynamic Array
- حذف عنصر من أي مكان في الـ Dynamic Array
- عيوب الدالتين insertAt و deleteAt
- الختام
المقدمة
اليوم سنبدأ سلسلة جديدة وهي عن هياكل البيانات Data Structures
سأحاول في هذه السلسلة أن أجعلك تفهم هذه الهياكل وتستطيع استخدامها بشكل عملي ومفيد
وليس فقط نظريات وتعريفات عامة
هذه السلسلة قد تكون طويلة وستتضمن عدة مقالات
قبل أن نبدأ أريدك أن تعرف أن هذه الهياكل أو الـ Data Structures
سهلة وليس بها أي صعوبة كما تظن
وتعلمها سهل وبسيط لكن المعضلة التي يواجهها الكثيرون هي أنهم لا يعرفون متى وكيف يتم استخدامها
لذا أحب أن أوضح بعض النقاط الهامة ولما تحتاج إلى تعلم الـ Data Structures
- ما هي الـ
Data Structures
؟- الـ
Data Structures
هي هياكل تستخدم لتخزين وتنظيم البيانات بشكل منظم ومرتب وسهل الوصول إليها
وهي تساعدك في حل المشاكل والمهام بشكل أسرع وأكثر فعالية - كل
Data Structure
تخزن وتتعامل مع البيانات بشكل مختلف ولها استخداماتها الخاصة
- الـ
- لماذا تحتاج إلى تعلم الـ
Data Structures
؟- فكرة تعلم الـ
Data Structures
هي لتجعلك تفكر بكيفية حل مشكلة عن طريق تنظيم البيانات بشكل معين - تجعلك تعرف عندما تريد تنفيذ شيء ليعمل بطريقة معينة تستطيع حينها أن تختار أو تبني الـ
Data Structure
المناسبة لهذا الشيء - طبعًا تجعلك منفتح وتفتح لك أفق جديد في البرمجة وتجعلك تفهم الأمور بشكل أفضل وكل هذا الكلمات الرنانة
- فكرة تعلم الـ
- بعض اللغات تقدم لك الـ
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 | 0 |
2 | 1 |
4 | 1 |
8 | 2 |
16 | 3 |
32 | 4 |
64 | 5 |
128 | 6 |
256 | 7 |
512 | 8 |
1024 | 9 |
2048 | 10 |
... | ... |
2097152 | 20 |
4194304 | 21 |
... | ... |
1073741824 | 29 |
2147483648 | 30 |
كما ترى في الجدول أن عدد مرات نقل العناصر نادر جدا ولن يحدث كثيرًا
حيث لو أنشأنا أراي جديدة أي حجمها 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