تمارين

الإجابة

1. مع الفهرس المبدوء من الصفر، يكون فهرس العنصر الرابع 3، لذا يمكن للمصفوفة الوصول إلى arr[3] مباشرةً.

2. يجب أن تبدأ القائمة المترابطة الأحادية من الرأس. ومسار الوصول فيها هو A → B → C → D، وهو يتطلب ثلاث حركات عبر next.

3. تستطيع المصفوفة تحديد موقع عنصر مباشرةً من عنوانها الابتدائي وفهرسه، لذا يكون التعقيد الزمني للوصول حسب الموضع $O(1)$. وللوصول إلى العقدة رقم $k$، يجب أن تبدأ القائمة المترابطة الأحادية من العقدة الرأسية وتتبع next عدد $k-1$ مرة، وهو ما يستغرق زمن $O(n)$ في أسوأ الحالات.

   وتتعلق هذه المقارنة بالوصول حسب الموضع فقط؛ وهي لا تعني أن القوائم المترابطة أبطأ في كل عملية.

الإجابة

1. تحرّك المصفوفة D أولاً موضعاً واحداً إلى اليمين، ثم تحرّك C موضعاً واحداً إلى اليمين، وأخيراً تضع X عند الفهرس 2، فتنتج [A, B, X, C, D].

2. يشير B.next في الأصل إلى C. عيّن أولاً X.next = B.next، فيشير X إلى C؛ ثم عيّن B.next = X. وتكون النتيجة A → B → X → C → D. وإذا طُمس B.next أولاً دون حفظ الرابط الأصلي، فقد يصبح C غير قابل للوصول.

3. بمجرد معرفة موقع B، لا يغيّر الإدراج في القائمة المترابطة سوى رابطين ويستغرق زمن $O(1)$. أما إذا وجب إيجاد B أولاً انطلاقاً من الرأس، فقد يستغرق ذلك البحث وحده زمن $O(n)$.

الإجابة

1. يستوعب الموضع الفارغ الأخير D. وتصبح المحتويات الآن [A, B, C, D]، مع size = 4 وcapacity = 4، فلا حاجة إلى توسيع السعة.

2. لا يوجد موضع فارغ عند إلحاق E، لذا يجب إنشاء مصفوفة جديدة بسعة 8. وتُنسخ العناصر الأربعة الموجودة A, B, C, D إليها قبل إضافة E. وتكون النتيجة size = 5 وcapacity = 8.

3. المصفوفة الأصلية نفسها لا تنمو. وإنما تنشئ القائمة مصفوفة جديدة أكبر، وتنسخ العناصر الموجودة إليها، ثم تستخدم المصفوفة الجديدة كتخزين أساسي لها. ومن منظور المستخدم، تكون السعة قد نمت.