ما هي قائمة الربط الفردية (Singly Linked List) ومتى تستخدمها؟

Question

Accepted Answer

**قائمة الربط الفردية** هي سلسلة من **العقد** (nodes)، حيث تحتفظ كل عقدة بقيمة ومؤشر إلى **العقدة التالية** (next node). بخلاف المصفوفة، فإن العقد ليست متجاورة — يمكن أن تكون موجودة في أي مكان في الذاكرة، متصلة بواسطة المراجع.

## البنية

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## مثال

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## التعقيد الحسابي

| العملية | الوقت |
|---|---|
| الإدراج/الحذف في البداية | O(1) |
| الوصول حسب الفهرس | O(n) |
| البحث | O(n) |

## المقارنات

- **المميزات:** إدراج/حذف O(1) في البداية؛ النمو دون إعادة تخصيص؛ لا توجد سعة مهدرة.
- **العيوب:** لا يوجد وصول عشوائي؛ كل عقدة تحمل حمل المؤشر؛ محلية ذاكرة تخزين مؤقت سيئة (ذاكرة متناثرة).

## لماذا يهم

تتفوق قوائم الربط عندما تقوم بإضافة أو إزالة متكررة في الأطراف ونادرا ما تقوم بالفهرسة في المنتصف — على سبيل المثال، كأساس للمكدسات والطوابير وقوائم الجوار.

فهم معالجة المؤشرات هنا أساسي لفهم الأشجار والرسوم البيانية والعديد من مسائل المقابلات.

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