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

قارن في السلسلة

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

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

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

إعلان المصفوفة

يمكن إعلان المصفوفة على النحو التالي:

 data_type name of the array[no of elements] 

للإعلان عن مصفوفة، نحتاج أولاً إلى تحديد نوع المصفوفة ثم اسم المصفوفة. داخل الأقواس المربعة، نحتاج إلى تحديد عدد العناصر التي يجب أن تحتويها المصفوفة.

دعونا نفهم من خلال مثال.

 int a[5]; 

في الحالة المذكورة أعلاه، أعلنا عن مجموعة من 5 عناصر مع ' أ اسم ان عدد صحيح نوع البيانات.

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

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

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

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

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

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

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

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

2. تكلفة إدخال عنصر

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

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

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

النمل مقابل مخضرم

إدراج عنصر في النهاية

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

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

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

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

جافا Localdatetime

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

القائمة المرتبطة الناتجة هي:

سهولة الاستعمال

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

ديناميكية في الحجم

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

3. متطلبات الذاكرة

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

مساحة الذاكرة = 7*4 = 28 بايت

حيث 7 هو عدد العناصر في المصفوفة و4 هو عدد البايتات من نوع عدد صحيح.

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

com.webdriver

مساحة الذاكرة = 8*4 = 32 بايت

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

دعونا نلقي نظرة على الاختلافات بين المصفوفة والقائمة المرتبطة في شكل جدول.