متى يتم استخدام LinkedList على ArrayList في Java؟




collections linked-list (20)

لقد كنت دائماً واحداً فقط لاستخدام:

List<String> names = new ArrayList<>();

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

متى يجب استخدام LinkedList عبر ArrayList والعكس بالعكس؟


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

Array vs ArrayList vs LinkedList vs Vector يذهب أكثر في العمق ، كما يفعل Linked List .


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

بما أن المراجع إما 32 أو 64 بتة (حتى عندما تكون فارغة) على أنظمةها النسبية ، فقد قمت بتضمين 4 مجموعات من البيانات LinkedLists و ArrayLists 32 و 64 بت.

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

ملاحظة 2: (بفضل BeeOnRope) نظرًا لأن CompressedOops هو الإعداد الافتراضي الآن من منتصف JDK6 وما فوق ، فإن القيم أدناه لأجهزة 64 بت ستطابق بشكل أساسي نظيراتها ذات 32 بت ، ما لم تقم بطبيعة الحال بإيقاف تشغيلها.

تظهر النتيجة بوضوح أن LinkedList هو أكثر بكثير من ArrayList ، خاصة مع وجود عدد كبير جدًا من العناصر. إذا كانت الذاكرة عاملاً ، LinkedLists من LinkedLists .

اتبع المعادلات التي استخدمتها ، أعلمني إذا قمت بأي شيء خطأ وسأقوم بإصلاحه. "b" إما 4 أو 8 لأنظمة 32 أو 64 بت ، و "n" هو عدد العناصر. لاحظ أن سبب التعديلات هو أن جميع الكائنات في جافا سوف تشغل مساحة مضاعفة من 8 بايت بغض النظر عما إذا كانت كلها مستخدمة أم لا.

ArrayList :

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList :

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

نعم ، أعرف ، هذا سؤال قديم ، لكنني سأرمي سنتيّتين:

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

هناك حالة استخدام شائعة واحدة يتفوق فيها LinkedList ArrayList: قائمة انتظار. ومع ذلك ، إذا كان هدفك هو الأداء ، بدلاً من LinkedList ، فيجب أيضًا التفكير في استخدام ArrayBlockingQueue (إذا كان بإمكانك تحديد حد أعلى لحجم قائمة انتظارك مسبقًا ، ويمكن أن تتحمل تخصيص كل الذاكرة في المقدمة) ، أو تنفيذ CircularArrayList هذا . (نعم ، إنه من عام 2001 ، لذا ستحتاج إلى توطيده ، لكني حصلت على نسب أداء مماثلة لما هو مقتبس في المقال الآن في JVM الأخير)


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

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

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


ArrayList هو ما تريد. دائماً LinkedList علة (أداء).

لماذا تمتص LinkedList :

  • ويستخدم الكثير من كائنات الذاكرة الصغيرة ، وبالتالي يؤثر على الأداء عبر العملية.
  • الكثير من الأشياء الصغيرة سيئة للمكان cache-locality.
  • تتطلب أي عملية مفهرسة اجتياز ، أي لديه أداء O (n). هذا غير واضح في التعليمات البرمجية المصدر ، مما يؤدي إلى خوارزميات O (n) أبطأ مما لو تم استخدام ArrayList .
  • الحصول على أداء جيد أمر صعب.
  • حتى عندما يكون أداء كبير - O هو نفسه ArrayList ، فمن المحتمل أن يكون أبطأ بشكل ملحوظ على أي حال.
  • من المخجل رؤية LinkedList في المصدر لأنه من المحتمل أن يكون خيارًا خاطئًا.

ArrayListو LinkedListعلى حد سواء الأدوات List interfaceوالأساليب والنتائج تكاد تكون متطابقة. ومع ذلك هناك اختلافات قليلة بينهما مما يجعل واحد أفضل من الآخر اعتمادا على الشرط.

ArrayList Vs LinkedList

1) Search: ArrayListعملية البحث سريعة جدًا مقارنة بعملية LinkedListالبحث. get(int index)في ArrayListيعطي أداء O(1)بينما LinkedListهو الأداء O(n).

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

2) Deletion: LinkedListعملية إزالة يعطي O(1)الأداء في حين ArrayListيعطي أداء متغير: O(n)في أسوأ الحالات (أثناء إزالة العنصر الأول) وفي O(1)أفضل الحالات (في حين إزالة العنصر الأخير).

الاستنتاج: حذف عنصر LinkedList أسرع مقارنة ArrayList.

السبب: يحتفظ كل عنصر من عناصر LinkedList بمؤشرين (عناوين) يشير إلى العناصر المجاورة في القائمة. ومن ثم ، لا تتطلب عملية الإزالة سوى تغيير موقع المؤشر في العقدتين المجاورتين (عناصر) العقدة التي ستتم إزالتها. بينما في ArrayList جميع العناصر يجب أن يتم نقلها لملء المساحة التي تم إنشاؤها بواسطة عنصر إزالتها.

3) Inserts Performance: LinkedListإضافة طريقة يعطي O(1)الأداء في حين ArrayListيعطي O(n)في أسوأ الحالات. السبب هو نفسه كما هو موضح للإزالة.

4) Memory Overhead: ArrayListيحافظ على الفهارس وبيانات العنصر مع LinkedListالحفاظ على بيانات العنصر واثنين من المؤشرات للعقد المجاورة

وبالتالي استهلاك الذاكرة مرتفع في LinkedList نسبياً.

هناك بعض أوجه التشابه بين هذه الفئات وهي كالتالي:

  • كل من ArrayList و LinkedList هي تنفيذ واجهة القائمة.
  • كلاهما يحافظان على ترتيب الإدراج العناصر الذي يعني أثناء عرض عناصر ArrayList و LinkedList أن مجموعة النتائج سيكون لها نفس الترتيب الذي تم فيه إدخال العناصر في القائمة.
  • كلا هاتين الفئتين غير متزامنتين ويمكن جعلهما متزامنين بوضوح باستخدام طريقة Collections.synchronizedList.
  • و iteratorو listIteratorإرجاعها من قبل هذه الفئات هي fail-fast(إذا تم تعديل قائمة هيكليا في أي وقت بعد إنشاء مكرر، في أي حال من الأحوال إلا من خلال iterator'sإزالة الخاصة أو إضافة أساليب ومكرر سوف throwل ConcurrentModificationException).

متى يتم استخدام LinkedList ومتى يتم استخدام ArrayList؟

  • كما هو موضح أعلاه إدراج وإزالة العمليات تعطي أداء جيد (O(1))في LinkedListمقارنة ArrayList(O(n)).

    ومن ثم إذا كان هناك متطلب من إضافة وحذف متكررة في التطبيق ، فإن LinkedList هو أفضل خيار.

  • عمليات البحث ( get method) سريعة Arraylist (O(1))ولكن ليس فيهاLinkedList (O(n))

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


1) بنية البيانات الأساسية

الفرق الأول بين ArrayList و LinkedList يأتي مع حقيقة أن ArrayList مدعومة من قبل صفيف بينما يتم دعم LinkedList بواسطة LinkedList. هذا سيؤدي إلى مزيد من الاختلافات في الأداء.

2) يربط LinkedList Deque

هناك اختلاف آخر بين ArrayList و LinkedList أنه بالإضافة إلى واجهة القائمة ، فإن LinkedList يقوم أيضًا بتطبيق واجهة Deque ، والتي توفر أولًا عمليات الخروج لـ add () و poll () وعدة وظائف Deque أخرى. 3) إضافة عناصر في ArrayList إضافة عنصر في ArrayList هو عملية O (1) إذا لم يتم تشغيل re-size لـ Array ، وفي هذه الحالة يصبح O (log (n)) ، من ناحية أخرى ، إلحاق عنصر في LinkedList هي عملية O (1) ، لأنها لا تتطلب أي تنقل.

4) إزالة عنصر من الموضع

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

5) متكررة عبر ArrayList أو LinkedList

Iteration هي عملية O (n) لكل من LinkedList و ArrayList حيث n عبارة عن عدد من العناصر.

6) استرداد العنصر من موقف

عملية get (index) هي O (1) في ArrayList بينما هي O (n / 2) في LinkedList ، حيث تحتاج إلى اجتياز ذلك الإدخال. على الرغم من أن O O في N (2) هو O فقط (n) لأننا نتجاهل الثوابت هناك.

7) الذاكرة

يستخدم LinkedList كائن مجمّع ، إدخال ، وهو فئة متداخلة ثابتة لتخزين البيانات والعقدين التالي والسابق بينما يقوم ArrayList بتخزين البيانات في صفيف فقط.

لذا متطلبات الذاكرة تبدو أقل في حالة ArrayList من LinkedList باستثناء الحالة حيث يؤدي Array عملية re-size عند نسخ المحتوى من صفيف إلى آخر.

إذا كان Array كبيرًا بما فيه الكفاية ، فقد يستغرق الأمر الكثير من الذاكرة عند هذه النقطة ويؤدي إلى جمع القمامة ، مما قد يؤدي إلى بطء وقت الاستجابة.

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

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

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

في رأيي ، استخدم ArrayList عبر LinkedList لمعظم الغرض العملي في Java.


TL ؛ DR بسبب بنية الكمبيوتر الحديثة ، ArrayListسيكون أكثر كفاءة بشكل ملحوظ تقريبا لأي حالة استخدام محتملة - وبالتالي LinkedListيجب تجنبها باستثناء بعض الحالات الفريدة والقوية للغاية.

من الناحية النظرية ، يحتوي LinkedList على O (1) لـ add(E element)

كما أن إضافة عنصر في منتصف القائمة يجب أن يكون فعالاً للغاية.

الممارسة مختلفة للغاية ، حيث أن LinkedList عبارة عن بنية بيانات معطيات كاشية . من أداء POV - هناك حالات قليلة جدًا LinkedListيمكن أن يكون فيها أداء أفضل من ذاكرة التخزين المؤقت ArrayList .

فيما يلي نتائج اختبار قياس الأداء لإدراج عناصر في مواقع عشوائية. كما ترون - والقائمة مجموعة إذا كفاءة أكثر من ذلك بكثير، على الرغم من الناحية النظرية وكل إدراج في منتصف القائمة تتطلب "التحرك" لل ن في وقت لاحق عناصر من مجموعة (قيم أقل وأفضل):

العمل على أجهزة الجيل اللاحق (مخابئ أكبر وأكثر كفاءة) - النتائج أكثر حاسمة:

يستغرق LinkedList المزيد من الوقت لإنجاز نفس المهمة. source شفرة المصدر

هناك سببان رئيسيان لهذا:

  1. بشكل رئيسي - LinkedListيتم تشتت عقد العقد بشكل عشوائي عبر الذاكرة. RAM ("ذاكرة الوصول العشوائي") ليست عشوائية حقا ، وهناك حاجة إلى جلب كتل من الذاكرة إلى ذاكرة التخزين المؤقت. تستغرق هذه العملية وقتًا ، وعندما تحدث هذه الجلبات بشكل متكرر - يجب استبدال صفحات الذاكرة في ذاكرة التخزين المؤقت طوال الوقت -> ذاكرة التخزين المؤقت يفتقد -> ذاكرة التخزين المؤقت ليست فعالة. ArrayListيتم تخزين العناصر على الذاكرة المستمرة - وهذا هو بالضبط ما هو الأمثل لعمارة وحدة المعالجة المركزية الحديثة ل.

  2. الثانوية LinkedList المطلوبة للاحتفاظ بالمؤشرات الخلفية / الخلفية ، مما يعني 3 أضعاف استهلاك الذاكرة لكل قيمة مخزنة مقارنة بـ ArrayList.

DynamicIntArray ، راجع للشغل ، هو عقد تنفيذ ArrayList مخصص Int(نوع بدائي) وليس كائنات - وبالتالي يتم تخزين جميع البيانات في مكان قريب - وبالتالي أكثر كفاءة.

من العناصر الأساسية التي يجب تذكرها هي أن تكلفة جلب كتلة الذاكرة ، أكثر أهمية من تكلفة الوصول إلى خلية ذاكرة واحدة. هذا هو السبب في أن القارئ 1MB من الذاكرة المتسلسلة يصل إلى 400 مرة أسرع من قراءة هذا الكم من البيانات من كتل ذاكرة مختلفة:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

المصدر: أرقام اختفاء كل مبرمج يجب أن يعرف

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

ملاحظة: هذا هو معيار مرجعي من C ++ Std lib ، ولكن تجربتي السابقة أظهرت أن C ++ و Java متشابهان للغاية. مصدر الرمز

إن نسخ الجزء الأكبر من الذاكرة المتسلسلة هو عملية تم تحسينها بواسطة وحدات المعالجة المركزية الحديثة - تغيير النظرية وجعلها في الواقع ، مرة أخرى ، ArrayList/ Vectorأكثر فعالية بكثير

الاعتمادات: يتم إنشاء جميع المعايير المنشورة هنا بواسطة Kjell Hedström . يمكن العثور على المزيد من البيانات على مدونته


ArrayList و LinkedList لها إيجابيات وسلبيات خاصة بهم.

يستخدم ArrayList عنوان الذاكرة المتجاورة مقارنة بـ LinkedList الذي يستخدم المؤشرات باتجاه العقدة التالية. لذلك عندما تريد البحث عن عنصر في ArrayList يكون أسرع من القيام بتكرار n مع LinkedList.

من ناحية أخرى ، يكون الإدراج والحذف في LinkedList أسهل بكثير لأنك تحتاج فقط إلى تغيير المؤشرات بينما يشير ArrayList إلى استخدام عملية shift لأي إدخال أو حذف.

إذا كانت لديك عمليات استرجاع متكررة في تطبيقك ، استخدم ArrayList. إذا كان لديك الإدراج المتكرر والحذف استخدام LinkedList.


جوشوا بلوخ ، مؤلف LinkedList:

هل يستخدم أي شخص في الواقع LinkedList؟ لقد كتبت ذلك ، ولم أستخدمه أبدًا.

الرابط: https://twitter.com/joshbloch/status/583813919019573248

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


لقد قرأت الردود ، ولكن هناك سيناريو واحد حيث أستخدم دائمًا LinkedList عبر ArrayList وأريد مشاركته لسماع الآراء:

في كل مرة كان لدي طريقة تقوم بإرجاع قائمة من البيانات التي تم الحصول عليها من DB أنا دائما استخدام LinkedList.

كان السبب المنطقي هو أنه لأنه من المستحيل معرفة عدد النتائج بالضبط التي سأحصل عليها ، لن تكون هناك ذاكرة مهدرة (كما هو الحال في ArrayList مع وجود فرق بين السعة والعدد الفعلي للعناصر) ، ولن يكون هناك وقت ضائع في محاولة مضاعفة القدرة.

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


يعتمد ذلك على العمليات التي ستقوم بها أكثر في القائمة.

ArrayListأسرع للوصول إلى قيمة مفهرسة. هو أسوأ بكثير عند إدراج أو حذف الكائنات.

لمعرفة المزيد ، اقرأ أي مقال يتحدث عن الفرق بين المصفوفات والقوائم المرتبطة.


ArrayList يمتد AbstractList وينفذ واجهة القائمة. ArrayList هو مجموعة ديناميكية.
يمكن القول أنه تم إنشاؤه بشكل أساسي للتغلب على عيوب صفائف

فئة LinkedList يمتد AbstractSequentialList ويقوم بتنفيذ واجهة قائمة و Deque و Queue.
أداء
arraylist.get()هو O (1) في حين أن linkedlist.get()O (n)
arraylist.add()هو O (1) و linkedlist.add()0 (1)
arraylist.contains()هو O (n) و linkedlist.contains()O (n)
arraylist.next()هو O (1) و linkedlist.next()O (1)
arraylist.remove()هو O (n) بينما linkedlist.remove()is O (1)
In arraylist
iterator.remove()is O (n)
while in linkedlist
iterator.remove()is O (1)


أحد الاختبارات التي رأيتها هنا لا تجري سوى الاختبار مرة واحدة. ولكن ما لاحظته هو أنك تحتاج إلى إجراء هذه الاختبارات عدة مرات وفي النهاية سوف تتقارب أوقاتها. أساسا JVM يحتاج إلى الاحماء. بالنسبة لحالة الاستخدام الخاصة بي ، احتجت لإضافة / إزالة عناصر إلى آخر ينمو إلى حوالي 500 عنصر. في اختباراتي LinkedListخرجت بشكل أسرع ، مع وجود رابط مرتبط LinkedListبنحو 50،000 NS والقدوم ArrayListإلى حوالي 90،000 NS ... اعط أو خذ. انظر الكود أدناه.

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}

إحدى السمات الهامة للقائمة المرتبطة (التي لم أقرأها في إجابة أخرى) هي مجموعة من قائمتين. مع صفيف هذا هو O (n) (+ overhead لبعض عمليات إعادة التخصيص) مع قائمة مرتبطة هذه فقط O (1) أو O (2) ؛-)

هام : بالنسبة لجافا ، LinkedListهذا غير صحيح! ترى هل هناك طريقة CONCAT سريع لقائمة مرتبطة في جافا؟


إذا كان رمز لديه add(0)و remove(0)، واستخدام LinkedListوانها أجمل addFirst()و removeFirst()الأساليب. خلاف ذلك ، استخدم ArrayList.

وبطبيعة الحال، Guava الصورة ImmutableList هو أفضل صديق.


بالإضافة إلى الحجج الجيدة الأخرى المذكورة أعلاه ، يجب أن تلاحظ واجهة ArrayListتطبيق RandomAccess، في حين LinkedListتنفذ Queue.

لذلك ، فإنها بطريقة ما تعالج مشاكل مختلفة قليلاً ، مع اختلاف الكفاءة والسلوك (انظر قائمة طرقها).


تكون عملية الحصول على (i) في ArrayList أسرع من LinkedList ، لأن:
ArrayList: تنفيذ مجموعة كبيرة من واجهة القائمة
LinkedList: تنفيذ قائمة Doubly المرتبطة من واجهات List و Deque

العمليات التي تسجل في القائمة ستجتاز القائمة من البداية أو النهاية ، أيهما أقرب إلى الفهرس المحدد.


كل من إزالة () وإدراج () لها كفاءة وقت التشغيل من O (n) لكل من ArrayLists و LinkedLists. ومع ذلك ، فإن السبب وراء وقت المعالجة الخطي يأتي من سببين مختلفين تمامًا:

في ArrayList ، تحصل على العنصر في O (1) ، ولكن في الواقع إزالة أو إدراج شيء يجعله O (n) لأن كل العناصر التالية تحتاج إلى تغيير.

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

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

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


هنا هو التدوين كبير-O في كل ArrayListو LinkedListوأيضا CopyOnWrite-ArrayList:

ArrayList

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

قائمة متصلة

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

على أساس هذه عليك أن تقرر ما تختار. :)





linked-list