ما الفرق بين المصفوفة والقائمة المرتبطة

المصفوفة والقائمة المرتبطة هما طريقتان لتنظيم البيانات في الذاكرة، قبل فهم الاختلافات بين المصفوفة والقائمة المرتبطة، ننظر أولاً إلى مفهومي المصفوفة والقائمة المرتبطة.

ما هي المصفوفة؟

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

ما هي القائمة المرتبطة؟

القائمة المرتبطة هي مجموعة العُقد التي يتم تخزينها بشكل عشوائي، تتكون كل عقدة من حقلين، وهما البيانات والرابط، هنا، البيانات هي القيمة المخزنة في تلك العقدة، والرابط هو المؤشر الذي يحمل عنوان العقدة التالية.

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

الاختلافات الرئيسية بين المصفوفة والقائمة المرتبطة:

تكلفة الوصول إلى عنصر:

في حالة وجود مصفوفة، بغض النظر عن حجم المصفوفة، تستغرق المصفوفة وقتًا ثابتًا للوصول إلى عنصر، في المصفوفة، يتم تخزين العناصر بطريقة متجاورة، لذلك إذا عرفنا العنوان الأساسي للعنصر، فيمكننا بسهولة الحصول على عنوان أي عنصر في المصفوفة، نحتاج إلى إجراء عملية حسابية بسيطة للحصول على عنوان أي عنصر في المصفوفة، لذا، فإن الوصول إلى العنصر في المصفوفة هو “O(1)” من حيث تعقيد الوقت.

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

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

تكلفة إدراج عنصر:

يمكن أن يكون هناك ثلاثة سيناريوهات في الإدراج:

1. إدخال العنصر في البداية:

لإدخال العنصر الجديد في البداية، نحتاج أولاً إلى إزاحة العنصر نحو اليمين لإنشاء مساحة في الموضع الأول، لذا، فإن تعقيد الوقت سيكون متناسبًا مع حجم القائمة، إذا كان (n) هو حجم المصفوفة ، فإن التعقيد الزمني سيكون “O(n)”.

في حالة القائمة المرتبطة، لإدراج عنصر في بداية القائمة المرتبطة، سننشئ عقدة جديدة، ويضاف عنوان العقدة الأولى إلى العقدة الجديدة، بهذه الطريقة، تصبح العقدة الجديدة العقدة الأولى، لذا، فإن تعقيد الوقت لا يتناسب مع حجم القائمة، سيكون التعقيد الزمني ثابتًا، أي “O(1)”.

2. إدخال عنصر في النهاية:

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

لإدراج عنصر في نهاية القائمة المرتبطة، يتعين علينا اجتياز القائمة بأكملها، إذا كانت القائمة المرتبطة تتكون من (n) من العناصر، فإن تعقيد الوقت سيكون “O(n)”.

3. إدخال عنصر في المنتصف:

لنفترض أننا نريد إدخال العنصر في الموضع (x) من المصفوفة؛ نحن بحاجة إلى تحويل عناصر “n/2” نحو اليمين، لذلك، فإن تعقيد الوقت يتناسب مع عدد العناصر، سيكون التعقيد الزمني هو “O(n)” للحالة المتوسطة.

في حالة القائمة المرتبطة، يتعين علينا الانتقال إلى الموضع الذي يتعين علينا إدراج العنصر الجديد فيه، وعلى الرغم أنه لا يتعين علينا إجراء أي نوع من التغيير، لكن الوقت المستغرق للوصول للموقع “n/2” يتناسب مع عدد “n” من العناصر، وسيكون التعقيد الزمني للحالة المتوسطة هو “O(n)”.

كنتيجة لما سبق فإنه عند الحديث عن:

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

• ديناميكية في الحجم: القائمة المرتبطة متغيرة في الحجم بينما المصفوفة ثابتة، هنا، لا يعني الثابت أنه لا يمكننا تحديد الحجم في وقت التشغيل، لكن لا يمكننا تغييره بمجرد تحديد الحجم.

متطلبات الذاكرة:

نظرًا لأن العناصر الموجودة في مصفوفة تخزن في كتلة واحدة متجاورة من الذاكرة، فإن المصفوفة ذات حجم ثابت، لنفترض أن لدينا مصفوفة بالحجم (7)، والمصفوفة تتكون من (4) عناصر ثم باقي المساحة غير مستخدمة، الذاكرة التي تحتلها العناصر السبعة هو (مساحة الذاكرة = 7 * 4 = 28 بايت)، حيث أن (7) هو عدد العناصر في المصفوفة، و(4) هو عدد البايت من نوع عدد صحيح.

في حالة القائمة المرتبطة، لا توجد ذاكرة غير مستخدمة ولكن الذاكرة الإضافية تشغلها متغيرات المؤشر، إذا كانت البيانات من نوع عدد صحيح، فإن إجمالي الذاكرة التي تشغلها عقدة واحدة هو (8) بايت، أي (4) بايت للبيانات و (4) بايت لمتغير المؤشر، إذا كانت القائمة المرتبطة تتكون من (4) عناصر، فإن مساحة الذاكرة التي تشغلها القائمة المرتبطة ستكون (مساحة الذاكرة = 8 * 4 = 32 بايت).

و ستكون القائمة المرتبطة خيارًا أفضل إذا كان حجم جزء البيانات أكبر، افترض أن البيانات (16) بايت، ستكون مساحة الذاكرة التي تشغلها المصفوفة (16 * 7 = 112 بايت) بينما تشغل القائمة المرتبطة (20 * 4 = 80)، هنا حددنا (20) بايت على أنها (16) بايت لحجم البيانات بالإضافة إلى (4) بايت لمتغير المؤشر، إذا كنا نختار الحجم الأكبر للبيانات، فستستهلك القائمة المرتبطة ذاكرة أقل، خلاف ذلك، فإنه يعتمد على العوامل التي نعتمدها لتحديد الحجم.