Java Academy · درس

المفاضلة بين LinkedList وArrayList

قارن أداء الإدراج والحذف والوصول العشوائي لاختيار نوع القائمة المناسب

المفاضلة بين LinkedList وArrayList درس مجاني في Java Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Java Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Java Academy 4 دروس في المجموع.

السؤال الأساسي

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

التركيب الداخلي لـ ArrayList

تخزن ArrayList العناصر في مصفوفة متجاورة. وعندما تمتلئ المصفوفة، تُستبدل بمصفوفة جديدة أكبر بمقدار 1.5×، وتُنقل إليها جميع العناصر.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

مراجعة التركيب الداخلي لـ LinkedList

يعيش كل عنصر في كائن Node خاص به، مع مؤشري prev وnext. ولا توجد ذاكرة متجاورة؛ إذ يمكن أن توجد العقد في أي مكان على heap.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

الوصول العشوائي: تتفوق ArrayList

تنفذ ArrayList.get(i) بتعقيد O(1)، إذ تصل مباشرةً إلى فهرس المصفوفة. أما LinkedList.get(i) فتعقيدها O(n)، إذ تجتاز ما يصل إلى n/2 عقدة.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

الإدراج في الرأس: تتفوق LinkedList

يتطلب الإضافة عند الفهرس 0 في ArrayList إزاحة جميع العناصر، بتعقيد O(n). أما LinkedList فتحدّث مؤشرين فقط، بتعقيد O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

الإدراج في الذيل: متقاربان تقريبًا

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

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

استخدام الذاكرة

ArrayList: نحو 8 بايتات لكل عنصر (مرجع واحد في المصفوفة). LinkedList: نحو 48 بايتًا لكل عنصر (كائن Node يحتوي على البيانات وprev وnext، بالإضافة إلى ترويسة الكائن). وبالنسبة إلى مجموعات البيانات الكبيرة، تستهلك ArrayList ذاكرة أقل بكثير.

أداء التكرار

يبلغ تعقيد التكرار التسلسلي (باستخدام for-each أو iterator) ‏O(n) في كلتا الحالتين. لكن تستفيد ArrayList من الجلب المسبق بواسطة ذاكرة التخزين المؤقت للمعالج، إذ تكون العناصر متجاورة في الذاكرة. أما عقد LinkedList فتتوزع في heap، مما يؤدي إلى فقدان البيانات في ذاكرة التخزين المؤقت.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

الإدراج والحذف في المنتصف

يتطلب كلاهما O(n) للعثور على الموضع. بعد العثور عليه، تُزيح ArrayList العناصر بتعقيد O(n)، بينما تفصل LinkedList العقدة بتعقيد O(1). لذلك تتفوق LinkedList عند إجراء تغييرات متكررة في المنتصف عندما يكون لديك iterator بالفعل؛ وإلا فهما متشابهتان.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

دليل اتخاذ القرار

اختر بناءً على العملية الأكثر تكرارًا:

ArrayList: الوصول العشوائي، والتكرار، والإضافة في الذيل — تغطي 90% من حالات الاستخدام
LinkedList: الإدراج أو الإزالة المتكررة في الرأس أو الذيل، وتنفيذ queue/deque/stack
ArrayDeque: إذا كنت تحتاج إلى طابور أو مكدس فقط، فهي أفضل من LinkedList

ملخص المقارنة المعيارية

نموذج ذهني للأداء:

get(i): ‏ArrayList بتعقيد O(1) مقابل LinkedList بتعقيد O(n)
add(0,x): ‏ArrayList بتعقيد O(n) مقابل LinkedList بتعقيد O(1)
add(x): كلاهما بمتوسط O(1)
iterator remove: كلاهما O(1) بعد تحديد الموضع
الذاكرة لكل عنصر: ‏ArrayList نحو 8B مقابل LinkedList نحو 48B

اختبار سريع

أنت تبني طابور مهام تُضاف المهام إلى نهايته وتُزال من بدايته ملايين المرات في الثانية. ما بنية البيانات الأنسب؟

مراجعة: LinkedList مقابل ArrayList

أهم النقاط:

يتفوّق ArrayList في الوصول العشوائي (O(1)) والتكرار الملائم لذاكرة التخزين المؤقت
يتفوّق LinkedList في عمليات الرأس/الذيل ذات التعقيد O(1)
الذاكرة: نحو 8B لكل عنصر في ArrayList، ونحو 48B لكل عنصر في LinkedList
بالنسبة إلى قوائم الانتظار والمكدسات، يُفضّل استخدام ArrayDeque بدلًا من LinkedList
يُعد ArrayList الخيار الافتراضي المناسب لمعظم السيناريوهات

الأسئلة الشائعة

هل درس «المفاضلة بين LinkedList وArrayList» مجاني؟

نعم — نص درس «المفاضلة بين LinkedList وArrayList» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Java Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Java Academy 4 دروس في المجموع.

ماذا ستتعلم في «المفاضلة بين LinkedList وArrayList»؟

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

هل أحتاج إلى خبرة سابقة لأبدأ Java Academy؟

لا تُشترط خبرة سابقة. Java Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.

كم من الوقت يستغرق درس «المفاضلة بين LinkedList وArrayList»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس Java Academy هذا؟

نعم. كل درس في Java Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

← العودة إلى Java Academy