تحليل الفرق بين ArrayList و LinkList في Java

الكاتب：Eve Cole وقت التحديث：2024-11-18 12:06:01

1. ينفذ ArrayList بنية بيانات تعتمد على المصفوفات الديناميكية، وينفذ LinkedList بنية بيانات تعتمد على القوائم المرتبطة.
2. للحصول على الوصول العشوائي وتعيينه، فإن ArrayList أفضل من LinkedList لأنه يمكن وضع ArrayList بشكل عشوائي، بينما يحتاج LinkedList إلى تحريك المؤشر إلى العقدة خطوة بخطوة. (فكر بالإشارة إلى المصفوفات والقوائم المرتبطة)
3. بالنسبة لعمليات الإضافة والحذف الجديدة والحذف، فإن LinedList أكثر فائدة، فهو يحتاج فقط إلى تعديل المؤشر، بينما يحتاج ArrayList إلى نقل البيانات لملء مساحة الكائن المحذوف.

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

واحد. تعقيد الوقت

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

لنفترض أن لدينا قائمة كبيرة، وقد تم فرز العناصر الموجودة فيها، وقد تكون هذه القائمة من نوع ArrayList أو LinkedList، والآن نقوم بإجراء بحث ثنائي في هذه القائمة. انظر البرنامج التالي:

انسخ رمز الكود كما يلي:

package com.mangocity.test;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.ArrayList;
استيراد java.util.Arrays؛
import java.util.Collections;
قائمة اختبار الفئة العامة ...{
int النهائي الثابت العام N = 50000؛
قيم القائمة الثابتة العامة؛
ثابت...{
عدد صحيح vals[]=عدد صحيح جديد[N];
عشوائي r=new Random();
ل(int i=0,currval=0;i<N;i++)...{
vals=new Integer(currval);
currval+=r.nextInt(100)+1;
}
value=Arrays.asList(vals);
}
قائمة زمنية طويلة ثابتة (قائمة lst)...{
بداية طويلة=System.currentTimeMillis();
ل(int i=0;i<N;i++)...{
int Index=Collections.binarySearch(lst,values.get(i));
إذا (الفهرس!=i)
System.out.println("***خطأ***");
}
إرجاع System.currentTimeMillis()-start;
}
الفراغ الثابت العام الرئيسي (String args[])...{
System.out.println("ArrayList تستهلك الوقت: "+timeList(new ArrayList(values)));
System.out.println("LinkedList تستهلك الوقت:"+timeList(new LinkedList(values)));
}
}

الإخراج الذي أحصل عليه هو: الوقت المستهلك في ArrayList: 15

الوقت المستهلك في القائمة المرتبطة: 2596

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

هل هذا يعني أن أداء ArrayList دائمًا أفضل من LinkedList؟ هذا ليس صحيحًا بالضرورة، ففي بعض الحالات يكون أداء LinkedList أفضل من ArrayList، وتكون بعض الخوارزميات أكثر كفاءة عند تنفيذها في LinkedList. على سبيل المثال، يكون الأداء أفضل عند استخدام الأسلوب Collections.reverse لعكس القائمة.

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

انسخ رمز الكود كما يلي:

package com.mangocity.test;
import java.util.*;
عرض قائمة الفئة العامة {
عدد صحيح نهائي ثابت N = 50000؛
قائمة زمنية طويلة ثابتة (قائمة القائمة) {
بداية طويلة=System.currentTimeMillis();
Object o = new Object();
ل(int i=0;i<N;i++)
list.add(0, o);
إرجاع System.currentTimeMillis()-start;
}
public static void main(String[] args) {
System.out.println("تستغرق قائمة ArrayList وقتًا: "+timeList(new ArrayList()));
System.out.println("القائمة المرتبطة تستغرق وقتًا:"+timeList(new LinkedList()));
}
}

في هذا الوقت، الإخراج الخاص بي هو: يأخذ ArrayList: 2463

يستغرق LinkedList: 15

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

اثنين. تعقيد الفضاء

توجد فئة داخلية خاصة في LinkedList، محددة على النحو التالي:

إدخال فئة ثابتة خاصة {
عنصر الكائن؛
الدخول التالي؛
الإدخال السابق؛
}

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

يستخدم ArrayList مصفوفة مدمجة لتخزين العناصر. سعة البداية لهذه المصفوفة هي 10. عندما يحتاج المصفوفة إلى النمو، يتم الحصول على السعة الجديدة وفقًا للمعادلة التالية: السعة الجديدة = (السعة القديمة*3)/2+. 1، وهذا يعني أن القدرة ستزداد بحوالي 50% في كل مرة. هذا يعني أنه إذا كان لديك كائن ArrayList يحتوي على عدد كبير من العناصر، فسوف ينتهي بك الأمر إلى إهدار الكثير من المساحة بسبب الطريقة التي يعمل بها ArrayList. إذا لم تكن هناك مساحة كافية لتخزين العنصر الجديد، فيجب إعادة تخصيص المصفوفة حتى يمكن إضافة العنصر الجديد. ستؤدي إعادة تخصيص المصفوفة إلى انخفاض كبير في الأداء. إذا كنا نعرف عدد العناصر التي ستحتوي عليها ArrayList، فيمكننا تحديد السعة من خلال المُنشئ. يمكننا أيضًا استخدام طريقة TrimToSize لإزالة المساحة الضائعة بعد تخصيص ArrayList.

ثلاثة. تلخيص

لكل من ArrayList وLinkedList مزايا وعيوب خاصة بهم من حيث الأداء، ولكل منهم تطبيقه الخاص، بشكل عام، يمكن وصفه على النحو التالي:

ملخص الأداء:

-	عملية إضافة ().	عملية حذف ().	عملية إدراج	عملية قيمة المؤشر	عملية قيمة التكرار
ArrayList/Vector/Stack	جيد	اختلاف	اختلاف	ممتاز	ممتاز
قائمة مرتبطة	جيد	جيد	جيد	اختلاف	ممتاز

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

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

3. لا يدعم LinkedList الوصول الفعال للعناصر العشوائية.

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

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

الفرق بين ArrayList و List في Java

جمع القائمة
قائمة ترث من واجهة المجموعة. القائمة عبارة عن مجموعة مرتبة. يمكن الحصول على/حذف/إدراج العناصر الموجودة في القائمة بناءً على الفهرس (الرقم التسلسلي: معلومات موضع العنصر في المجموعة).

على عكس مجموعة المجموعة، تسمح القائمة بالعناصر المكررة. بالنسبة لعناصر الكائن e1 وe2 التي تستوفي شروط e1.equals(e2)، فيمكن أن تتواجد في مجموعة القائمة في نفس الوقت. بالطبع، هناك أيضًا فئات تنفيذ القائمة التي لا تسمح بالعناصر المكررة.
في الوقت نفسه، توفر القائمة أيضًا طريقة listIterator () التي تُرجع كائن واجهة ListIterator. بالمقارنة مع واجهة Iterator، يضيف ListIterator طرقًا لإضافة العناصر وحذفها وتعيينها، ويمكنه أيضًا الانتقال للأمام أو للخلف.

العلاقة بين القائمة والمجموعة:
java.util.Collection[I]
+--java.util.List[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C]
+--java.util.Stack [C]

تتضمن فئات التنفيذ لواجهة القائمة بشكل أساسي ArrayList وLinkedList وVector وStack وما إلى ذلك.

العلاقة بين الأب والابن.
القائمة عبارة عن واجهة، ويرث ArrayList هذه الواجهة وينفذها.
عند استخدامه، عادةً ما أستخدم ArrayList ولم أستخدم القائمة مطلقًا. يمكنك استخدامه على النحو التالي: List list = new ArrayList();

واجهة التجميع
المجموعة هي واجهة المجموعة الأساسية. تمثل المجموعة مجموعة من الكائنات، أي عناصر المجموعة. تسمح بعض المجموعات بعناصر متطابقة والبعض الآخر لا يسمح بذلك. بعض النوع والبعض الآخر لا. لا توفر Java SDK الفئات التي ترث مباشرة من المجموعة. الفئات التي توفرها Java SDK كلها "واجهات فرعية" ترث من المجموعة، مثل القائمة والمجموعة.
يجب أن توفر جميع الفئات التي تنفذ واجهة المجموعة مُنشئين قياسيين: مُنشئ بدون معلمات لإنشاء مجموعة فارغة، ومنشئ معلمة مجموعة لإنشاء مجموعة جديدة. تحتوي مجموعة الإدخال على نفس العناصر. يسمح المنشئ الأخير للمستخدم بنسخ المجموعة.

كيفية التكرار من خلال كل عنصر في المجموعة؟ بغض النظر عن النوع الفعلي للمجموعة، فهي تدعم طريقة iterator()، والتي تُرجع مكررًا يمكن استخدامه للوصول إلى كل عنصر في المجموعة واحدًا تلو الآخر. الاستخدام النموذجي هو كما يلي:
Iterator it = Collection.iterator(); // احصل على مكرر
بينما(it.hasNext()) {
Object obj = it.next(); // احصل على العنصر التالي
}
الواجهتان المشتقتان من واجهة المجموعة هما List وSet.

واجهة القائمة:
القائمة عبارة عن مجموعة مرتبة باستخدام هذه الواجهة، يمكنك التحكم بدقة في موضع الإدراج لكل عنصر. يمكن للمستخدمين الوصول إلى العناصر الموجودة في القائمة باستخدام الفهرس (موضع العنصر في القائمة، يشبه مصفوفة منخفضة)، والذي يشبه مصفوفة Java.
على عكس المجموعة المذكورة أدناه، تسمح القائمة بنفس العناصر.
بالإضافة إلى طريقة iterator()‎ الضرورية لواجهة المجموعة، توفر List أيضًا طريقة listIterator()‎، والتي تُرجع واجهة ListIterator. وبالمقارنة مع واجهة Iterator القياسية، يحتوي ListIterator على المزيد من الإضافات () وطرق أخرى، مما يسمح بالإضافات. قم بحذف العناصر وتعيينها والانتقال للأمام أو للخلف.
الفئات الشائعة التي تنفذ واجهة القائمة هي LinkedList وArrayList وVector وStack.

فئة القائمة المرتبطة
يقوم LinkedList بتنفيذ واجهة القائمة ويسمح بالعناصر الفارغة. بالإضافة إلى ذلك، يوفر LinkedList طرقًا إضافية للحصول على وإزالة وإدراج في رأس LinkedList أو ذيله. تسمح هذه العمليات باستخدام LinkedList كمكدس أو قائمة انتظار أو deque.
لاحظ أن LinkedList لا يحتوي على طرق متزامنة. إذا وصلت عدة سلاسل رسائل إلى القائمة في نفس الوقت، فيجب عليها تنفيذ مزامنة الوصول بنفسها. أحد الحلول هو إنشاء قائمة متزامنة عند إنشاء القائمة:
قائمة القائمة = Collections.synchronizedList(new LinkedList(...));

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

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