إطار المجموعات

LinkedList وواجهة List

15 دقيقة الدرس 3 من 14

LinkedList وواجهة List

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

واجهة List — العقد المشترك

تُطبّق كلٌّ من ArrayList وLinkedList الواجهة java.util.List<E>. تُحدّد هذه الواجهة العمليات التي يجب أن تدعمها كل مجموعة مرتّبة قابلة للفهرسة:

add(E e) / add(int index, E e) — إلحاق أو إدراج
get(int index) — الاسترجاع بالموضع
set(int index, E e) — الاستبدال بالموضع
remove(int index) / remove(Object o) — الحذف بالفهرس أو القيمة
size()، contains(Object o)، indexOf(Object o)
subList(int from, int to)، sort(Comparator<? super E> c)

البرمجة بالاعتماد على واجهة List بدلًا من الفئة المحددة هي من أساسيات مبادئ Java. تتيح لك استبدال التنفيذ لاحقًا دون لمس بقية الكود:

// أعلن كـ List — وليس ArrayList أو LinkedList
List<String> names = new ArrayList<>();
// يمكن التبديل إلى LinkedList في أي وقت — لا شيء آخر يتغيّر
// List<String> names = new LinkedList<>();

names.add("Alice");
names.add("Bob");
names.add(1, "Charlie"); // إدراج في الفهرس 1
System.out.println(names); // [Alice, Charlie, Bob]
System.out.println(names.get(0)); // Alice

أعلن المتغيّرات كـ List وليس ArrayList. توقيعات الدوال التي تقبل List<String> تعمل مع أي تنفيذ. أما التوقيعات التي تشترط ArrayList<String> فتُقيّدك بتنفيذ محدّد — وهو خطأ في الغالب.

كيف تعمل LinkedList داخليًا

LinkedList هي قائمة مرتبطة مزدوجة. كل عقدة تبدو تقريبًا هكذا:

// مفاهيمي — ليس الكود الفعلي لـ JDK
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

يحتفظ كائن القائمة بمراجع إلى العقدة الأولى والأخيرة فقط. للوصول إلى العقدة رقم k، يجب على Java المشي عبر السلسلة من أحد الطرفين — بتعقيد O(n). أما الإدراج أو الحذف عند عقدة معروفة فهو O(1): مجرد إعادة ربط ثلاثة مؤشرات.

import java.util.LinkedList;
import java.util.List;

LinkedList<Integer> scores = new LinkedList<>();
scores.add(10);
scores.add(20);
scores.add(30);

// إدراج في المقدمة — O(1)
scores.addFirst(5);
// إدراج في النهاية — O(1)
scores.addLast(35);

System.out.println(scores); // [5, 10, 20, 30, 35]

// حذف من المقدمة — O(1)
int head = scores.removeFirst();
System.out.println(head); // 5
System.out.println(scores); // [10, 20, 30, 35]

تُطبّق LinkedList أيضًا Deque<E>، ولهذا تكشف عن دوال مثل addFirst وaddLast وpeekFirst وpollLast وسواها — دوال لا تملكها ArrayList.

ArrayList مقابل LinkedList — جدول المفاضلة

هذه هي تعقيدات Big-O التي تقود قرار الاختيار:

الوصول العشوائي (get(i)): ArrayList بتعقيد O(1) مقابل LinkedList بتعقيد O(n). ArrayList تفوز بوضوح — تقفز مباشرة إلى فهرس المصفوفة الداخلية.
الإلحاق في النهاية (add(e)): كلاهما O(1) مُبسَّط. تُجري ArrayList تغيير الحجم أحيانًا؛ تُخصّص LinkedList عقدة جديدة دائمًا.
الإدراج/الحذف في المنتصف (add(i, e) / remove(i)): ArrayList بتعقيد O(n) لأن العناصر تتحرّك؛ LinkedList بتعقيد O(n) للوصول إلى الفهرس ثم O(1) لإعادة الربط. لا فائز واضح إلا إذا كان لديك مكرّر عند نقطة الإدراج.
الإدراج/الحذف في المقدمة: ArrayList بتعقيد O(n) (كل عنصر يتحرّك يمينًا)؛ LinkedList بتعقيد O(1). هذه الحالة الوحيدة التي تتفوّق فيها LinkedList على ArrayList بوضوح.
الذاكرة: ArrayList أكثر إحكامًا (مصفوفة واحدة). كل عقدة في LinkedList تُخصّص مرجعَين إضافيَّين، مما يرفع التكلفة لكل عنصر 3-4 أضعاف.

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

التكرار الفعّال على LinkedList

لا تستخدم أبدًا حلقات تعتمد على الفهرس مع LinkedList. كل استدعاء لـ get(i) يسير عبر السلسلة من الرأس، مما يحوّل تكرارًا بتعقيد O(n) إلى O(n²).

LinkedList<String> items = new LinkedList<>(List.of("a", "b", "c", "d"));

// خطأ — O(n²) لأن كل get(i) يسير من الرأس
for (int i = 0; i < items.size(); i++) {
    System.out.println(items.get(i));
}

// صحيح — حلقة for المحسّنة تستخدم المكرّر داخليًا — O(n)
for (String item : items) {
    System.out.println(item);
}

// صحيح أيضًا — مكرّر صريح
var it = items.listIterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

لا تستدع get(index) داخل حلقة على LinkedList أبدًا. هذا أحد أكثر أخطاء الأداء شيوعًا لدى مطوّري Java. استخدم دائمًا حلقة for المحسّنة أو Iterator / ListIterator صريحًا.

استخدام LinkedList كـ Deque

عندما تحتاج إلى طابور (FIFO) أو مكدّس (LIFO) مبني على هيكل مرتبط، فإن LinkedList خيار جاهز:

import java.util.Deque;
import java.util.LinkedList;

// استخدام كطابور: إضافة في الذيل، إزالة من الرأس
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
queue.offer("third");
System.out.println(queue.poll()); // first

// استخدام كمكدّس: دفع وسحب من الرأس
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // top

الخلاصة

تُحدّد واجهة List العقد؛ وتُمثّل ArrayList وLinkedList تنفيذَين ذوَي بنية داخلية مختلفة جدًا. افضّل ArrayList للقوائم متعددة الأغراض — أداؤها مع الذاكرة المؤقتة أفضل وهي أسرع للوصول العشوائي. استخدم LinkedList عند الحاجة إلى إدراج/حذف ثابت O(1) في المقدمة، أو عند الرغبة في واجهة Deque. أعلن المتغيّرات دائمًا كـ List (أو Deque) لتبقى قادرًا على تبديل التنفيذ.