ArrayList مقابل LinkedList مقابل المتجه

إن الهبوط في وظيفة هندسة البرمجيات أسهل بكثير مما يعتقد الناس. ولكن في بعض الحالات ، فشلت غالبية من أعمالي مع خبرة سنوات عديدة في هذه الخبرة ترشيحه. "ما المشكلة؟" السؤال يثور في رأسي.

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

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

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

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

أيهما أفضل ، ArrayList ، LinkedList أو Vector؟

قائمة

قبل الإجابة على السؤال ، من الجيد معرفة القائمة. القائمة هي أحد أنواع البيانات المجردة (ADT) التي تخزن عناصرها في تسلسل وتسمح لنا بإضافة عناصرها وإزالتها والوصول إليها باستخدام الفهرس. Array هي إحدى بنيات البيانات التي تنفذ قائمة ADT. في Array ، يمكننا إضافة عنصر وحذفه والحصول عليه باستخدام الفهرس. ArrayList و LinkedList و Vector هي مثال آخر على هياكل البيانات التي تنفذ قائمة ADT. بينما يكون Array بحجم ثابت بمجرد إعلانه ، فإن ArrayList و LinkedList و Vector يكون له حجم ديناميكي (يمكن تغيير حجمه). إذا تم إعلان الصفيف بطول 7 ، فسيكون طوله 7 حتى نهاية نطاقه. بينما يمكن لـ ArrayList و LinkedList و Vector تخزين البيانات قدر الإمكان ، حيث يكون الحد هو إجمالي الذاكرة المتوفرة.

إطار مجموعة جافا. المصدر: ويكيبيديا

في Java Collection Framework ، يتم تطبيق قائمة ADT كواجهة تسمى List ، و ArrayList و LinkedList & Vector هي فئة ملموسة تنفذ واجهة القائمة. نظرًا لأن هذه الفئات الملموسة تنفذ نفس الواجهة ، يجب أن يكون لهذه الفئات نفس الوظيفة لأن جميع الفئات غير التجريدية التي تنفذ واجهة ، تكون مطلوبة لتنفيذ جميع الأساليب المجردة التي تم الإعلان عنها في الواجهة.

كيف يتم تخزين البيانات

الاختلاف الأساسي في هياكل البيانات الثلاثة أعلاه هو الطريقة التي تخزن بها بياناتهم والتي تسبب أداء مختلفًا للعمليات المختلفة. في Java (والمستخدمة أيضًا في Kotlin) ، يستخدم ArrayList و Vector Array لتخزين عناصره ، بينما يخزن LinkedList عناصره في قائمة مزدوجة الارتباط.

في علوم الكمبيوتر ، تكون القائمة المرتبطة بشكل مضاعف عبارة عن بنية بيانات مرتبطة تتكون من مجموعة من السجلات المرتبطة بالتسلسل تسمى العقد. تحتوي كل عقدة على حقلين ، يسمى الارتباطات ، وهما مرجعان للعقدة السابقة والعقدة التالية في تسلسل العقد. - ويكيبيديا
ArrayList (أعلى) مقابل LinkedList (أسفل). المصدر https://dzone.com/storage/temp/895349-arraylist-linkedlistt.png

في LinkedList ، يمكن للعقدة الأولى معرفة العقدة الثانية. يمكن للعقدة الثانية معرفة العقدتين الأولى والثالثة. يمكن للعقدة الثالثة معرفة العقدتين الثانية والرابعة. وهكذا ، يمكن للعقدة معرفة العقدة السابقة والعقدة التالية. خاصة بالنسبة للعقدة الأولى في LinkedList ، لن تكون هناك عقدة سابقة وأيضًا العقدة الأخيرة في LinkedList لن تكون هناك عقدة أخرى.

إليك مقتطف الشفرة كيف يخزن ArrayList عناصره في Array.

/ **
 * مجموعة التخزين المؤقت التي عناصر ArrayList
 * مخزن. قدرة ArrayList هو طول هذا
 * مجموعة عازلة. أي ArrayList فارغة مع elementData ==
 * سيتم توسيع DEFAULTCAPACITY_EMPTY_ELEMENTDATA إلى
 * DEFAULT_CAPACITY عند إضافة العنصر الأول.
 * /
كائن عابر [] elementData ؛ // غير خاص لتبسيط المتداخلة
                                // وصول الطبقة

وهنا كيف تقوم شركة Vector بتخزين عناصرها أيضًا في Array.

/ **
 * مجموعة المخزن المؤقت الذي مكونات ناقل
 * مخزن. قدرة المتجه هو طول هذه المجموعة
 * العازلة ، وعلى الأقل كبيرة بما يكفي لاحتواء جميع ناقلات الأمراض
 * عناصر.
 *
 * 

أي عناصر صفيف تتبع العنصر الأخير في Vector  * لاغية.  *  * @ المسلسل  * / كائن محمي [] elementData ؛

في مقتطف الشفرة أعلاه ، يمكننا أن نرى أن كلاً من ArrayList و Vector يخزن عناصره في متغير اسمه elementDatawith Object [] كنوعه. لماذا كائن []؟ الكائن هو فئة فائقة من جميع الفئات في جافا. من خلال تعريف elementData بأنه Object [] ، يمكن لـ elementData تخزين أنواع مختلفة من العناصر ، ويمكن أن يكون String أو Integer أو Double أو Float أو فئة مخصصة مثل Pair و TextView وما إلى ذلك.

لماذا ArrayList و Vector باستخدام Array لتخزين بياناته؟ كما ذكرنا سابقًا ، على الرغم من استخدام ArrayList و Vector لصفيفات لتخزين بياناته ، فإن ArrayList و Vector لديه القدرة على الحصول على أحجام ديناميكية (يمكن تغيير حجمها). عندما يكون المصفوفة المستخدمة في ArrayList و Vector ممتلئة ، يمكن أن "تنمو" تلك لزيادة قدرتها. يزيد ArrayList و Vector من قدرته عن طريق إنشاء Array جديد بحجم أكبر من الحجم السابق ، ثم ينسخ جميع العناصر من Array القديم إلى Array الجديد باستخدام الأمر Arrays.copyOf. فيما يلي مقتطف شفرة للبرنامج على ArrayList لتوسيع سعته (المصدر: ArrayList.java).

/ **
  * يزيد من القدرة على ضمان أنه يمكن أن تعقد على الأقل
  * عدد العناصر المحددة بواسطة وسيطة الحد الأدنى للسعة.
  *
  *param minCapacity السعة الدنيا المطلوبة
  * /
  نمو الفراغ الخاص (int minCapacity) {
      / / رمز الفائض واعية
      int oldCapacity = elementData.length؛
      int newCapacity = oldCapacity + (oldCapacity >> 1)؛
      إذا (newCapacity - minCapacity <0)
          newCapacity = minCapacity ؛
      if (newCapacity - MAX_ARRAY_SIZE> 0)
          newCapacity = hugeCapacity (minCapacity) ؛
      // minCapacity عادة ما تكون قريبة من الحجم ، لذلك هذا هو الفوز:
      elementData = Arrays.copyOf (elementData ، newCapacity) ؛
  }

وهنا كيف تقوم شركة Vector بتوسيع قدرتها (المصدر: Vector.java)

نمو الفراغ الخاص (int minCapacity) {
    / / رمز الفائض واعية
    int oldCapacity = elementData.length؛
    int newCapacity = oldCapacity + ((capacityIncrement> 0)؟
                                     القدرةإدخال: oldCapacity) ؛
    إذا (newCapacity - minCapacity <0)
        newCapacity = minCapacity ؛
    if (newCapacity - MAX_ARRAY_SIZE> 0)
        newCapacity = hugeCapacity (minCapacity) ؛
    elementData = Arrays.copyOf (elementData ، newCapacity) ؛
}

يشبه تطبيق المتجهات تقريبًا ArrayList ، والفرق الوحيد هو أن جميع العمليات في Vector تتم مزامنتها مما يجعل أي طريقة تلامس محتويات Vector آمنة.

أيهما أفضل ، ArrayList ، LinkedList أو Vector؟ للإجابة على هذا السؤال ، يمكنك مقارنة أداء العمليات الشائعة داخل ArrayList و LinkedList. نظرًا لأن تطبيق ArrayList و Vector متطابق تقريبًا ، سيكون أداءهما أيضًا هو نفسه تقريبًا.

مقارنة الأداء بين ArrayList و LinkedList

من الجدول أعلاه ، يمكننا أن نرى أنه لا توجد رصاصة فضية لجميع العمليات. ArrayList متفوقة على LinkedList في الوصول العشوائي (الحصول). ArrayList أفضل من LinkedList لأن ArrayList يخزن عناصره في Array بينما يخزن LinkedList عناصره داخل العقدة المرتبطة. على سبيل المثال ، للحصول على العنصر الخامس ، يمكن لـ ArrayList و Vector الحصول على عنصره مباشرةً باستخدام الفهرس لأن ArrayList و Vector هو في الأساس صفيف ، في حين يجب أن يكون LinkedList متكرراً لاكتشاف العنصر الخامس ، لأنه في LinkedList ، يمكننا فقط معرفة الأول والعنصر الأخير فقط.

بالنسبة إلى insertFirst و deleteFirst ، يعتبر LinkedList أفضل من ArrayList. يتطلب ArrayList جهدًا كبيرًا لإضافة عنصر في البداية (الفهرس الأول) أو حذف العنصر الأول لأن ArrayList يجب أن يغير العناصر التالية بعد الإضافة أو الحذف. بينما تحتاج LinkedList فقط إلى استبدال / تعيين مؤشراتها. بالنسبة للوظائف الأخرى ، فإن كلا من ArrayList و LinkedList لهما نفس الأداء نسبياً.

أيهما أفضل ، ArrayList ، LinkedList أو Vector؟ تعتمد على احتياجاتك. إذا كنت تستخدم الوصول العشوائي (get) في كثير من الأحيان ، فسيكون ArrayList و Vector اختيارًا جيدًا. اختر Vector إذا كنت بحاجة إلى مجموعة آمنة لسلسلة العمليات. ولكن إذا قمت بإجراء إضافات أو عمليات حذف بشكل متكرر على الموضع الأول (الفهرس) ، فإن LinkedList هو الخيار الأفضل.

هناك ADT آخر يشيع استخدامه أثناء تطوير التطبيق مثل Set و Map و PriorityQueue. لمعرفة كيفية تخزين البيانات الخاصة بهم وكيفية عملها ومتى يتم استخدامها ، استمر في متابعة "الوسائط".