ADT: What vs How
ADT (نوع البيانات المجرد): يحدد العمليات (Operations) المتاحة (مثل add, remove, get) دون تحديد كيفية تنفيذها.
The List ADT
- مجموعة مرتبة من العناصر.
- عمليات: insert, delete, find, printList.
- يمكن تنفيذها بطريقتين رئيسيتين: Array أو Linked List.
Java Collections API
في جافا، List هي الـ Interface (ADT)، بينما ArrayList و LinkedList هي الـ Implementation (التطبيق الفعلي).
ArrayList vs LinkedList
| العملية (Operation) | ArrayList (مصفوفة) | LinkedList (مؤشرات) | التعليل |
|---|---|---|---|
| get(index) | $O(1)$ | $O(N)$ | المصفوفة وصول مباشر، القائمة تحتاج للمرور عقدة عقدة. |
| add(end) | $O(1)$ Amortized | $O(1)$ | كلاهما سريع في الإضافة للنهاية. |
| add(front) | $O(N)$ | $O(1)$ | المصفوفة تحتاج لإزاحة كل العناصر (Shift). |
| Storage | متصلة (Contiguous) | مبعثرة (Dispersed) | المصفوفة صديقة للكاش (Cache Friendly). |
Under the Hood: Nodes
Doubly Linked List Structure
كل عقدة تحتوي على: البيانات (Data)، مؤشر للسابق (Prev)، ومؤشر للتالي (Next).
The Power of Iterators
لماذا نستخدم Iterator؟
عند استخدام حلقة for مع LinkedList والوصول بـ get(i)، يصبح التعقيد $O(N^2)$ (كارثة!).
الـ Iterator يحتفظ بموقع العنصر الحالي، مما يجعل المرور على القائمة $O(N)$ فقط.
Iterator<Integer> itr = list.iterator();
while (itr.hasNext()) {
Integer x = itr.next();
if (x % 2 == 0) itr.remove();
}
ConcurrentModificationException
إذا قمت بحذف عنصر من القائمة (list.remove) أثناء استخدام حلقة (for-each)، سيحدث هذا الخطأ.
الحل: استخدم iterator.remove().
ArrayList Resizing
عندما تمتلئ المصفوفة في ArrayList، يتم إنشاء مصفوفة جديدة بضعف الحجم (2x) ونسخ العناصر.
هذه العملية مكلفة $O(N)$، لكنها تحدث نادراً، لذا نقول أن الإضافة هي $O(1)$ Amortized.