CS210 - دليل دراسة القوائم والمصفوفات والمكررات

📊 المصفوفات

تعريف

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

يتم ترقيم خلايا المصفوفة A بـ 0، 1، 2، وهكذا.

هيكل المصفوفة

...

مفاهيم أساسية

🔑 طول وسعة المصفوفة

الطول/السعة: أقصى عدد من العناصر يمكن تخزينها في المصفوفة
في جافا: يتم الوصول إليها باستخدام a.length
يتم ترقيم الخلايا من 0 إلى a.length - 1
الوصول إلى الخلية بالفهرس k: a[k]

تعريف المصفوفات

الطريقة 1: الشكل الحرفي

elementType[] arrayName = {initialValue₀, initialValue₁, ..., initialValueₙ₋₁};

// مثال:
int[] a = {5, 7, 9, 10};
                

الطريقة 2: استخدام عامل 'new'

new elementType[length]

// مثال:
int[] numbers = new int[10];
String[] names = new String[3];
                

عمليات المصفوفة

✏️ إضافة عنصر في الفهرس i

العملية: لإضافة عنصر e في الفهرس i، ننقل العناصر من board[i] إلى board[n-1] للأمام

التعقيد الزمني: O(n) في أسوأ حالة (عندما i = 0)

// كود زائف للإضافة في الفهرس i
for (j = n-1; j >= i; j--)
    board[j+1] = board[j];
board[i] = e;
size++;
                    

🗑️ إزالة عنصر في الفهرس i

العملية: لإزالة عنصر في الفهرس i، ننقل العناصر من board[i+1] إلى board[n-1] للخلف

التعقيد الزمني: O(n) في أسوأ حالة (عندما i = 0)

// كود زائف للإزالة في الفهرس i
for (j = i; j < size-1; j++)
    board[j] = board[j+1];
board[size-1] = null;
size--;
                    

ملخص الأداء

العملية	التعقيد الزمني	ملاحظات
الوصول لعنصر في الفهرس i	O(1)	وصول مباشر عبر a[i]
الإدراج في الفهرس i	O(n)	يحتاج لنقل العناصر
الإزالة في الفهرس i	O(n)	يحتاج لنقل العناصر
البحث عن عنصر	O(n)	يجب فحص كل عنصر

🔗 القوائم المتصلة أحادية الاتجاه

تعريف

القائمة المتصلة أحادية الاتجاه هي هيكل بيانات ملموس يتكون من تسلسل عقد، يبدأ بمؤشر رأس. كل عقدة تخزن:

عنصرًا (البيانات)
رابطًا للعقدة التالية

يشير رابط العقدة الأخيرة إلى null.

⚠️ خصائص أساسية

يمكن التحرك للأمام فقط خلال القائمة
كل عقدة لها مرجع للعقدة التالية فقط
تشير العقدة الأخيرة إلى null
تحتاج مؤشر رأس للوصول إلى القائمة
غالبًا ما تتضمن مؤشر ذيل للإدراج الفعال في النهاية

تنفيذ فئة العقدة

private static class Node<E> {
    private E element;           // مرجع للعنصر
    private Node<E> next;       // مرجع للعقدة التالية
    
    public Node(E e, Node<E> n) {
        element = e;
        next = n;
    }
    
    public E getElement() { return element; }
    public Node<E> getNext() { return next; }
    public void setNext(Node<E> n) { next = n; }
}
                

العمليات الأساسية

➕ الإدراج في الرأس

الخطوات:

تخصيص عقدة جديدة
إدراج العنصر الجديد
جعل العقدة الجديدة تشير إلى الرأس القديم
تحديث الرأس ليشير إلى العقدة الجديدة

التعقيد الزمني: O(1)

public void addFirst(E element) {
    head = new Node<>(element, head);
    size++;
    if (size == 1)
        tail = head;  // حالة خاصة: العقدة الجديدة تصبح الذيل
}
                    

➕ الإدراج في الذيل

الخطوات:

تخصيص عقدة جديدة
إدراج العنصر الجديد
جعل العقدة الجديدة تشير إلى null
جعل العقدة الأخيرة القديمة تشير إلى العقدة الجديدة
تحديث الذيل ليشير إلى العقدة الجديدة

التعقيد الزمني: O(1)

public void addLast(E element) {
    Node<E> newest = new Node<>(element, null);
    if (isEmpty())
        head = newest;
    else
        tail.setNext(newest);
    tail = newest;
    size++;
}
                    

➖ الإزالة من الرأس

الخطوات:

تحديث الرأس ليشير إلى العقدة التالية
السماح لمجمع القمامة باستعادة العقدة الأولى السابقة

التعقيد الزمني: O(1)

public E removeFirst() {
    if (isEmpty()) return null;
    E answer = head.getElement();
    head = head.getNext();
    size--;
    if (size == 0)
        tail = null;  // القائمة أصبحت فارغة
    return answer;
}
                    

⚠️ الإزالة من الذيل - ليست فعالة!

الإزالة من ذيل القائمة المتصلة أحادية الاتجاه ليست فعالة لأن:

لا توجد طريقة بوقت ثابت لتحديث الذيل للإشارة إلى العقدة السابقة
يجب اجتياز القائمة بالكامل للعثور على العقدة قبل الأخيرة
التعقيد الزمني: O(n)

ملخص الأداء

العملية	التعقيد الزمني	ملاحظات
الإدراج في الرأس	O(1)	مجرد تحديث مؤشر الرأس
الإدراج في الذيل	O(1)	مع مؤشر الذيل
الإزالة من الرأس	O(1)	مجرد تحديث مؤشر الرأس
الإزالة من الذيل	O(n)	يجب اجتياز للعثور على العقدة السابقة
الوصول لعنصر في الفهرس i	O(n)	يجب اجتياز من الرأس

🔗🔗 القوائم المتصلة ثنائية الاتجاه

تعريف

القائمة المتصلة ثنائية الاتجاه توفر هيكل بيانات أكثر تنوعًا يمكن اجتيازه للأمام والخلف. كل عقدة تخزن:

عنصرًا (البيانات)
رابطًا للعقدة السابقة
رابطًا للعقدة التالية

تستخدم عقد رأس وذيل وهمية خاصة (بدون بيانات).

⚠️ مزايا أساسية على القوائم أحادية الاتجاه

يمكن اجتيازها للأمام والخلف
يمكن إزالة الذيل بكفاءة - O(1)
يمكن الإدراج قبل عقدة معينة بكفاءة
أسهل في تنفيذ بعض العمليات

تنفيذ فئة العقدة

private static class Node<E> {
    private E element;           // مرجع للعنصر
    private Node<E> prev;       // مرجع للعقدة السابقة
    private Node<E> next;       // مرجع للعقدة التالية
    
    public Node(E e, Node<E> p, Node<E> n) {
        element = e;
        prev = p;
        next = n;
    }
    
    public E getElement() { return element; }
    public Node<E> getPrev() { return prev; }
    public Node<E> getNext() { return next; }
    public void setPrev(Node<E> p) { prev = p; }
    public void setNext(Node<E> n) { next = n; }
}
                

العقد الوهمية

🏁 عقد الرأس والذيل

الرأس: عقدة وهمية في البداية (لا تخزن بيانات)
الذيل: عقدة وهمية في النهاية (لا تخزن بيانات)
الغرض: تبسيط التنفيذ بإلغاء الحالات الخاصة للقوائم الفارغة
القائمة الفارغة لها header.next = trailer و trailer.prev = header

// منشئ للقائمة الفارغة
public DoublyLinkedList() {
    header = new Node<>(null, null, null);
    trailer = new Node<>(null, header, null);
    header.setNext(trailer);
}
                    

العمليات الأساسية

➕ الإدراج بين عقدتين

الخطوات:

إنشاء عقدة جديدة
ربط العقدة الجديدة بالسلف والخلف
ربط السلف بالعقدة الجديدة
ربط الخلف بالعقدة الجديدة

التعقيد الزمني: O(1)

private void addBetween(E element, Node<E> predecessor, Node<E> successor) {
    Node<E> newest = new Node<>(element, predecessor, successor);
    predecessor.setNext(newest);
    successor.setPrev(newest);
    size++;
}

// الإدراج في المقدمة (بعد الرأس)
public void addFirst(E element) {
    addBetween(element, header, header.getNext());
}

// الإدراج في النهاية (قبل الذيل)
public void addLast(E element) {
    addBetween(element, trailer.getPrev(), trailer);
}
                    

➖ إزالة عقدة

الخطوات:

الحصول على السلف والخلف للعقدة المراد إزالتها
ربط السلف بالخلف
ربط الخلف بالسلف
السماح بجمع القمامة للعقدة المزالة

التعقيد الزمني: O(1)

private E remove(Node<E> node) {
    Node<E> predecessor = node.getPrev();
    Node<E> successor = node.getNext();
    predecessor.setNext(successor);
    successor.setPrev(predecessor);
    size--;
    return node.getElement();
}

// إزالة العنصر الأول
public E removeFirst() {
    if (isEmpty()) return null;
    return remove(header.getNext());
}

// إزالة العنصر الأخير - الآن فعالة!
public E removeLast() {
    if (isEmpty()) return null;
    return remove(trailer.getPrev());
}
                    

ملخص الأداء

العملية	التعقيد الزمني	ملاحظات
الإدراج في الرأس	O(1)	بعد عقدة الرأس
الإدراج في الذيل	O(1)	قبل عقدة الذيل
الإزالة من الرأس	O(1)	بعد عقدة الرأس
الإزالة من الذيل	O(1)	✅ الآن فعالة! يمكن الوصول للعقدة السابقة
الإدراج/الإزالة في عقدة معينة	O(1)	إذا كان لدينا مرجع للعقدة

⚖️ مقارنة المصفوفات مقابل القوائم المتصلة

📊 المصفوفات

المزايا:

✅ وصول عشوائي سريع - O(1)
✅ كفاءة في الذاكرة (لا مؤشرات إضافية)
✅ توطين أفضل للذاكرة المخبئية
✅ تنفيذ بسيط

العيوب:

❌ إدراج/حذف بطيء - O(n)
❌ حجم ثابت (أو تغيير الحجم مكلف)
❌ مساحة مهدرة إذا لم تكن ممتلئة

🔗 القوائم المتصلة

المزايا:

✅ إدراج/حذف سريع في مواقع معروفة - O(1)
✅ حجم ديناميكي
✅ لا توجد مساحة مهدرة
✅ سهل تقسيم/دمج القوائم

العيوب:

❌ وصول عشوائي بطيء - O(n)
❌ ذاكرة إضافية للمؤشرات
❌ توطين ضعيف للذاكرة المخبئية

متى نستخدم كلًا منها

استخدم المصفوفات عندما:

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

استخدم القوائم المتصلة عندما:

تحتاج إدراج/حذف متكرر
الحجم يتغير ديناميكيًا
لا تحتاج للوصول العشوائي
تنفذ رتلات، مكدسات، أو هياكل متسلسلة أخرى

📈 القوائم المصفوفية الديناميكية (مصفوفات قابلة للنمو)

مشكلة المصفوفات الثابتة

المصفوفات القياسية لها سعة ثابتة. ماذا لو لم نكن نعرف الحجم مسبقًا؟ ماذا لو احتجنا لنمو المصفوفة؟

الحل: المصفوفات الديناميكية

عندما تمتلئ المصفوفة، يمكننا:

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

استراتيجيات النمو

استراتيجية الزيادة الثابتة

زيادة الحجم بـثابت c

الحجم الجديد = الحجم القديم + c

التحليل:

استبدال المصفوفة k = n/c مرة
الوقت الإجمالي: n + c + 2c + 3c + ... + kc
T(n) = O(n + k²) = O(n²)
الوقت المتناسب لكل إضافة: O(n)

❌ غير فعال!

استراتيجية المضاعفة

مضاعفة الحجم كل مرة

الحجم الجديد = 2 × الحجم القديم

التحليل:

استبدال المصفوفة k = log₂ n مرة
الوقت الإجمالي: n + 1 + 2 + 4 + 8 + ... + 2^k
T(n) = n + 2^(k+1) - 1 = O(n)
الوقت المتناسب لكل إضافة: O(1)

✅ أفضل بكثير!

التنفيذ

public void add(int index, E element) {
    // التحقق إذا كانت المصفوفة ممتلئة
    if (size == data.length) {
        // مضاعفة السعة!
        E[] newData = (E[]) new Object[2 * data.length];
        for (int i = 0; i < size; i++)
            newData[i] = data[i];
        data = newData;
    }
    
    // نقل العناصر لعمل مساحة
    for (int i = size; i > index; i--)
        data[i] = data[i-1];
    
    data[index] = element;
    size++;
}
                

🎯 النقطة الأساسية: التحليل المتناسب

الوقت المتناسب هو متوسط الوقت لكل عملية عبر سلسلة من العمليات.

مع استراتيجية المضاعفة:

معظم عمليات الإدراج رخيصة (O(1))
أحيانًا لدينا عملية مكلفة (O(n)) عندما نغير الحجم
لكن تغيير الحجم يحدث نادرًا جدًا بحيث يكون المتوسط لا يزال O(1)!

ArrayList في جافا

java.util.ArrayList في جافا تنفذ مفهوم المصفوفة الديناميكية هذا:

تتوسع تلقائيًا عند الحاجة
توفر O(1) متناسب للإدراج في النهاية
توفر O(1) وصول بالفهرس
لا تزال O(n) للإدراج/الحذف في المنتصف

📍 القوائم الموضعية

ما هي القائمة الموضعية؟

القائمة الموضعية هي نوع بيانات مجرد يوفر تجريدًا عامًا للتسلسل مع القدرة على تحديد موقع العنصر.

الموضع يعمل كعلامة أو رمز داخل القائمة، مستقل عن فهرس العنصر.

🎯 مفاهيم أساسية

الموضع غير متأثر بالتغييرات في أماكن أخرى في القائمة
يصبح غير صالح فقط إذا تم حذفه صراحةً
يدعم الإدراج/الحذف الفعال في أي موضع
التنفيذ الطبيعي: قائمة متصلة ثنائية الاتجاه

واجهة الموضع

public interface Position<E> {
    // إرجاع العنصر المخزن في هذا الموضع
    E getElement() throws IllegalStateException;
}
                

طرق نوع البيانات المجرد للقائمة الموضعية

طرق الوصول

الطريقة	الوصف	التعقيد
`first()`	إرجاع موضع العنصر الأول (أو null إذا فارغة)	O(1)
`last()`	إرجاع موضع العنصر الأخير (أو null إذا فارغة)	O(1)
`before(p)`	إرجاع الموضع مباشرة قبل p (أو null)	O(1)
`after(p)`	إرجاع الموضع مباشرة بعد p (أو null)	O(1)
`isEmpty()`	إرجاع true إذا كانت القائمة لا تحتوي على عناصر	O(1)
`size()`	إرجاع عدد العناصر في القائمة	O(1)

طرق التحديث

الطريقة	الوصف	التعقيد
`addFirst(e)`	إدراج عنصر في المقدمة، وإرجاع موضعه	O(1)
`addLast(e)`	إدراج عنصر في المؤخرة، وإرجاع موضعه	O(1)
`addBefore(p, e)`	إدراج عنصر مباشرة قبل الموضع p	O(1)
`addAfter(p, e)`	إدراج عنصر مباشرة بعد الموضع p	O(1)
`set(p, e)`	استبدال العنصر في الموضع p، وإرجاع العنصر القديم	O(1)
`remove(p)`	إزالة وإرجاع العنصر في الموضع p	O(1)

مثال للاستخدام

PositionalList<String> list = new LinkedPositionalList<>();

// بناء القائمة: (A, B, C)
Position<String> p1 = list.addLast("A");
Position<String> p2 = list.addLast("B");
Position<String> p3 = list.addLast("C");

// الإدراج قبل B: (A, X, B, C)
Position<String> p4 = list.addBefore(p2, "X");

// الوصول للجيران
list.after(p1);    // إرجاع موضع X
list.before(p2);   // إرجاع موضع X

// إزالة X: (A, B, C)
list.remove(p4);
                    

🔄 المكررات

ما هو المكرر؟

المكرر هو نمط تصميم برمجي يجرد عملية المسح خلال تسلسل من العناصر، عنصرًا واحدًا في كل مرة.

واجهة المكرر

public interface Iterator<E> {
    // إرجاع true إذا كان هناك عنصر واحد على الأقل
    boolean hasNext();
    
    // إرجاع العنصر التالي في التسلسل
    E next();
    
    // اختياري: يزيل العنصر الأخير المُرجع
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
}
                

واجهة القابل للتكرار

المجموعات تنفذ واجهة القابل للتكرار، التي توفر طريقة للحصول على مكرر:

public interface Iterable<E> {
    // إرجاع مكرر على عناصر النوع E
    Iterator<E> iterator();
}
                    

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

الطريقة التقليدية

List<String> names = new ArrayList<>();
// ... إضافة عناصر ...

// الحصول على مكرر
Iterator<String> iter = names.iterator();

// التكرار خلال العناصر
while (iter.hasNext()) {
    String name = iter.next();
    System.out.println(name);
}
                

حلقة for-each (سكر نحوي)

حلقة for-each في جافا هي سكر نحوي لاستخدام المكررات:

// هذا التركيب الأنيق...
for (String name : names) {
    System.out.println(name);
}

// ...مكافئ لهذا:
Iterator<String> iter = names.iterator();
while (iter.hasNext()) {
    String name = iter.next();
    System.out.println(name);
}
                    

🎯 فوائد أساسية للمكررات

التجريد: نفس الواجهة لهياكل بيانات مختلفة
المرونة: يمكن وجود عدة مكررات على نفس المجموعة
الأمان: يمكن إزالة العناصر بأمان أثناء التكرار
البساطة: حلقة for-each توفر تركيبًا نظيفًا

تنفيذ مكرر

مثال: مكرر لـ ArrayList

private class ArrayIterator implements Iterator<E> {
    private int current = 0;  // فهرس العنصر التالي
    
    public boolean hasNext() {
        return current < size;
    }
    
    public E next() {
        if (!hasNext()) 
            throw new NoSuchElementException();
        return data[current++];
    }
}

// في فئة ArrayList
public Iterator<E> iterator() {
    return new ArrayIterator();
}
                    

📝 ملخص شامل

مقارنة التعقيد الزمني

العملية	المصفوفة	القائمة المتصلة أحادية	القائمة المتصلة ثنائية
الوصول بالفهرس	O(1)	O(n)	O(n)
الإدراج في الرأس	O(n)	O(1)	O(1)
الإدراج في الذيل	O(n)	O(1)	O(1)
الإزالة من الرأس	O(n)	O(1)	O(1)
الإزالة من الذيل	O(n)	O(n)	O(1)
الإدراج في المنتصف	O(n)	O(n)*	O(n)*

* O(1) إذا كان الموضع معروفًا مسبقًا

🎓 نقاط أساسية

1. المصفوفات

الأفضل لـ: الوصول العشوائي والمجموعات ذات الحجم الثابت
الضعف: إدراج/حذف بطيء
الذاكرة: متجاورة، توطين جيد للذاكرة المخبئية

2. القوائم المتصلة أحادية الاتجاه

الأفضل لـ: الوصول التسلسلي، عمليات متكررة على الرأس
الضعف: لا يمكن إزالة الذيل بكفاءة، لا اجتياز للخلف
الذاكرة: متناثرة، مساحة إضافية لمؤشر التالي

3. القوائم المتصلة ثنائية الاتجاه

الأفضل لـ: الاجتياز ثنائي الاتجاه، العمليات في كلا الطرفين
الضعف: ذاكرة أكثر (مؤشران لكل عقدة)
الذاكرة: متناثرة، مساحة إضافية لمؤشري السابق والتالي

4. المصفوفات الديناميكية (ArrayList)

تدمج سرعة وصول المصفوفات مع تغيير الحجم الديناميكي
استراتيجية المضاعفة تعطي O(1) متناسب للإدراج في النهاية
أفضل قائمة للأغراض العامة في جافا

5. القوائم الموضعية

تحدد مواضع مجردة مستقلة عن الفهارس
تُنفذ طبيعيًا مع القوائم المتصلة ثنائية الاتجاه
جميع العمليات في O(1) إذا كان الموضع معروفًا

6. المكررات

توفر طريقة موحدة لاجتياز المجموعات
تمكن من حلقات for-each
تسمح باجتيازات متعددة متزامنة

💡 نصائح الدراسة وأسئلة التدريب

🎯 ما يجب معرفته

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

أسئلة التدريب

السؤال 1: عمليات المصفوفات

س: لماذا إدراج عنصر في منتصف المصفوفة هو O(n)؟

ج: لأننا نحتاج لنقل جميع العناصر بعد نقطة الإدراج موقعًا واحدًا لليمين. في أسوأ حالة (الإدراج في الفهرس 0)، ننقل n عنصرًا.

السؤال 2: ميزة القوائم المتصلة

س: متى تكون القائمة المتصلة أفضل من المصفوفة؟

ج: عندما تحتاج لإدراج/حذف متكرر ولا تحتاج للوصول العشوائي. القوائم المتصلة يمكنها الإدراج/الحذف في وقت O(1) إذا كان لديك الموضع، بينما تحتاج المصفوفات لوقت O(n) لنقل العناصر.

السؤال 3: ثنائية مقابل أحادية الاتجاه

س: ما الميزة الأساسية للقائمة المتصلة ثنائية الاتجاه على أحادية الاتجاه؟

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

السؤال 4: المصفوفات الديناميكية

س: لماذا استراتيجية المضاعفة للمصفوفات الديناميكية أفضل من الزيادة بثابت؟

ج: المضاعفة تعطي O(1) وقتًا متناسبًا لكل إدراج (إجمالي O(n) لـ n إدراج)، بينما الزيادة بثابت تعطي O(n) وقتًا متناسبًا (إجمالي O(n²) لـ n إدراج). المضاعفة تقلل تردد عمليات تغيير الحجم المكلفة.

السؤال 5: استخدام المكررات

س: ماذا يعني "قابل للتكرار" في جافا؟

ج: الفئة قابلة للتكرار إذا نفذت واجهة Iterable، مما يعني أنها توفر طريقة iterator() تُرجع كائن Iterator. هذا يسمح باستخدام الفئة في حلقات for-each.