ملخص

مراجعة النقاط الرئيسية

المصفوفات والقوائم المترابطة بنيتا بيانات أساسيتان، تمثّلان طريقتين مختلفتين لتخزين البيانات في ذاكرة الحاسوب: التخزين المتجاور والتخزين المتناثر. ونقاط قوتهما وضعفهما متكاملة.
تدعم المصفوفات الوصول العشوائي وتستهلك ذاكرة أقل؛ غير أن إدراج العناصر وحذفها غير فعّال، والطول غير قابل للتغيير بعد التهيئة.
تحقق القوائم المترابطة إدراج العقد وحذفها بكفاءة عبر تعديل المراجع (المؤشرات)، ويمكنها تعديل الطول بمرونة؛ غير أن الوصول إلى العقد غير فعّال واستهلاك الذاكرة أعلى. وتشمل أنواع القوائم المترابطة الشائعة القوائم المترابطة المفردة والقوائم المترابطة الدائرية والقوائم المترابطة المزدوجة.
القائمة مجموعة مرتبة من العناصر تدعم الإدراج والحذف والبحث والتعديل، وتُنفَّذ عادةً استناداً إلى مصفوفات ديناميكية. وهي تحتفظ بمزايا المصفوفات مع السماح بتعديل الطول بمرونة.
أدى ظهور القوائم إلى تحسين الجدوى العملية للمصفوفات تحسيناً كبيراً، غير أنه قد يهدر بعض المساحة من الذاكرة.
أثناء تنفيذ البرنامج، تُخزَّن البيانات أساساً في الذاكرة. وتوفّر المصفوفات كفاءة مساحة أعلى، بينما تقدّم القوائم المترابطة مرونة أكبر في استخدام الذاكرة.
توفّر ذاكرة التخزين المؤقت (cache) وصولاً سريعاً للبيانات إلى المعالج عبر آليات مثل أسطر التخزين المؤقت والجلب المسبق والتموضع المكاني والزمني، مما يحسّن كفاءة تنفيذ البرنامج تحسيناً كبيراً.
لأن معدل إصابة ذاكرة التخزين المؤقت في المصفوفات أعلى، فهي عموماً أكثر كفاءة من القوائم المترابطة. وعند اختيار بنية بيانات، ينبغي الاختيار المناسب وفقاً للمتطلبات والسيناريوهات المحددة.

أسئلة وأجوبة

س: هل تخزين المصفوفة على المكدس مقابل تخزينها على الكومة يؤثر في كفاءة الزمن وكفاءة المساحة؟

تُخزَّن المصفوفات على المكدس وعلى الكومة معاً في مساحة ذاكرة متجاورة، لذا فإن كفاءة عمليات البيانات متطابقة تقريباً. غير أن للمكدس والكومة خصائصهما الخاصة، مما يؤدي إلى الفروق التالية.

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

س: لماذا تشترط المصفوفات أن تكون العناصر من النوع نفسه، بينما لا تشدد القوائم المترابطة على هذا الشرط؟

تتكوّن القوائم المترابطة من عقد، وتتصل العقد عبر المراجع (المؤشرات)، ويمكن لكل عقدة تخزين أنواع مختلفة من البيانات، مثل int وdouble وstring وobject وغيرها.

في المقابل، يجب أن تكون عناصر المصفوفة من النوع نفسه حتى يمكن تحديد مواقعها بحساب الإزاحات. فمثلاً، إذا احتوت مصفوفة على نوعي int وlong معاً، وكان كل عنصر يشغل 4 بايتات و8 بايتات على التوالي، فلا يمكن استخدام الصيغة التالية لحساب الإزاحة، لأن المصفوفة تحتوي على "حجمي عنصر" مختلفين.

# عنوان العنصر = العنوان الأساسي للمصفوفة (عنوان العنصر الأول) + حجم العنصر * فهرس العنصر

س: بعد حذف العقدة P، هل نحتاج إلى تعيين P.next إلى None؟

لا حاجة إلى تعديل P.next. فمن منظور القائمة المترابطة، لن نصادف P بعد الآن عند الاجتياز من العقدة الرأسية إلى العقدة الذيلية. وهذا يعني أن العقدة P أُزيلت من القائمة المترابطة، ولا يهم إلى أين تشير العقدة P في هذه الحالة—فلن يؤثر ذلك في القائمة المترابطة.

من منظور الخوارزميات وحل المسائل، لا بأس في إبقاء المؤشر متصلاً ما دام منطق البرنامج صحيحاً. ومن منظور تنفيذ المكتبات القياسية، يكون فصل المؤشر صراحةً أكثر أماناً ووضوحاً. وإذا لم يُفصل ولم تُستَعد العقدة المحذوفة بشكل سليم، فقد يؤثر ذلك في استعادة العقد التالية لها.

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

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

س: في مخطط "تعريف القائمة المترابطة وطرق تخزينها"، هل تشغل عقدة المؤشر الزرقاء الفاتحة عنوان ذاكرة واحداً بمفردها، أم تتشارك بالتساوي مع قيمة العقدة؟

هذا المخطط تمثيل نوعي؛ أما التمثيل الكمي فيتطلب التحليل وفقاً للحالة المحددة.

تشغل أنواع مختلفة من قيم العقد مساحات مختلفة، مثل int وlong وdouble وكائنات الأمثلة وغيرها.
تعتمد كمية مساحة الذاكرة التي تشغلها متغيرات المؤشرات على نظام التشغيل وبيئة الترجمة المستخدمة، وهي عادةً 8 بايتات أو 4 بايتات.

س: هل إضافة عنصر في نهاية قائمة ما تكون دائماً بتعقيد $O(1)$ ؟

إذا تجاوزت الإضافة طول القائمة، فيجب توسيع القائمة أولاً قبل الإضافة. حيث يخصص النظام كتلة ذاكرة جديدة وينقل جميع عناصر القائمة الأصلية إليها، وفي هذه الحالة يصبح التعقيد الزمني $O(n)$ .

س: "أدى ظهور القوائم إلى تحسين الجدوى العملية للمصفوفات تحسيناً كبيراً، لكنه قد يؤدي إلى بعض هدر مساحة الذاكرة"—هل تشير هذه المساحة المهدرة إلى الذاكرة التي تشغلها متغيرات إضافية مثل السعة والطول ومعامل التوسّع؟

لهذا الهدر في المساحة جانبان رئيسيان: من جهة، تحدد القوائم عادةً طولاً ابتدائياً قد لا نحتاج إلى استغلاله كاملاً؛ ومن جهة أخرى، ولمنع التوسّع المتكرر، يكون التوسّع عادةً بضرب معامل، مثل $\times 1.5$ . ونتيجة لذلك، توجد مواضع فارغة كثيرة لا نستطيع عادةً ملأها بالكامل.

س: في Python، بعد تهيئة n = [1, 2, 3]، تكون عناوين هذه العناصر الثلاثة متجاورة، لكن عند تهيئة m = [2, 1, 3] نجد أن معرّف (id) كل عنصر غير متصل، بل هو نفسه الموجود في n. وبما أن عناوين هذه العناصر غير متجاورة، فهل لا يزال m مصفوفة؟

إذا استبدلنا عناصر القائمة بعقد قائمة مترابطة n = [n1, n2, n3, n4, n5]، فعادةً تكون كائنات العقد الخمسة هذه متناثرة أيضاً في الذاكرة. غير أنه بمعطى فهرس قائمة ما، لا يزال بإمكاننا الحصول على عنوان ذاكرة العقدة في زمن $O(1)$ ، وبالتالي الوصول إلى العقدة المقابلة. وهذا لأن المصفوفة تخزّن مراجع إلى العقد، لا العقد نفسها.

وخلافاً لكثير من اللغات، تُغلَّف الأعداد في Python كائنات، ولا تخزّن القوائم الأعداد نفسها، بل مراجع إلى الأعداد. لذلك نجد أن الأعداد نفسها في مصفوفتين لها المعرّف نفسه، ولا يلزم أن تكون عناوين ذاكرة هذه الأعداد متجاورة.

س: تحتوي C++ STL على std::list الذي ينفّذ قائمة مترابطة مزدوجة بالفعل، لكن يبدو أن بعض كتب الخوارزميات لا تستخدمه مباشرةً. فهل هناك قيد ما؟

من جهة، نفضّل غالباً استخدام المصفوفات لتنفيذ الخوارزميات، ولا نلجأ إلى القوائم المترابطة إلا عند الضرورة، ويرجع ذلك أساساً إلى سببين.

الحِمْل المكاني: بما أن كل عنصر يتطلب مؤشرين إضافيين (واحداً للعنصر السابق وآخر للعنصر التالي)، يستهلك std::list عادةً مساحة أكبر من std::vector.
عدم ملاءمة ذاكرة التخزين المؤقت: بما أن البيانات لا تُخزَّن بشكل متجاور، يكون استغلال ذاكرة التخزين المؤقت في std::list أقل. وعموماً، يتمتع std::vector بأداء أفضل.

ومن جهة أخرى، تتركز الحالات التي تكون فيها القوائم المترابطة ضرورية أساساً في الأشجار الثنائية والرسوم البيانية. أما المكدسات والطوابير فتستخدم عادةً stack وqueue الموفّرين في لغة البرمجة، لا القوائم المترابطة.

س: هل تُنشئ العملية res = [[0]] * n قائمة ثنائية الأبعاد تكون فيها كل [0] مستقلة؟

لا، ليست مستقلة. ففي هذه القائمة الثنائية الأبعاد، تكون جميع [0] في الواقع مراجع إلى الكائن نفسه. وإذا عدّلنا عنصراً واحداً، سنجد أن جميع العناصر المقابلة تتغير تبعاً لذلك.

وإذا أردنا أن تكون كل [0] في القائمة الثنائية الأبعاد مستقلة، يمكننا استخدام res = [[0] for _ in range(n)] لتحقيق ذلك. ومبدأ هذا النهج هو تهيئة $n$ من كائنات القوائم [0] المستقلة.

س: هل تُنشئ العملية res = [0] * n قائمة تكون فيها كل قيمة صحيحة 0 مستقلة؟

في هذه القائمة، تشير جميع الأصفار الصحيحة إلى الكائن نفسه. وهذا لأن Python تستخدم آلية تخزين مؤقت للأعداد الصحيحة الصغيرة (عادةً من -5 إلى 256) لتكثير إعادة استخدام الكائنات وتحسين الأداء.

ومع أنها تشير جميعاً إلى الكائن نفسه، لا يزال بإمكاننا تعديل كل عنصر في القائمة بشكل مستقل. وهذا لأن الأعداد الصحيحة في Python "كائنات غير قابلة للتغيير". وعندما نعدّل عنصراً، فإننا في الواقع نحول ذلك العنصر ليشير إلى كائن مختلف، بدلاً من تغيير الكائن الأصلي نفسه.

غير أنه عندما تكون عناصر القائمة "كائنات قابلة للتغيير" (مثل القوائم أو القواميس أو أمثلة الأصناف)، فإن تعديل عنصر يغيّر الكائن نفسه مباشرةً، وستتغير جميع العناصر التي تشير إلى ذلك الكائن بالتغيير نفسه.

السابق ذاكرة الوصول العشوائي وذاكرة التخزين المؤقت * التالي تمارين