الدرس 13 · الوحدة 7: اختيار تركيب بيانات لحل مشكلة
القائمة المترابطة
نبني بأيدينا أول تركيب بيانات: سلسلة عقد يعرف كل منها جاره. ⏱ نحو 40 دقيقة.
بعد هذا الدرس ستستطيع أن:
- تشرح بنية القائمة المترابطة: العقدة والرأس والمؤشر.
- تنفذ الإضافة في الأول والآخر والبحث والحذف.
- تتعامل مع الحالات الخاصة: القائمة الفارغة وحذف الرأس.
- تقارن تعقيد عملياتها بـ
list.
١عقد مربوطة بمؤشرات
القائمة المترابطة Linked List سلسلة من العقد Nodes. كل عقدة تحمل قيمة data ومؤشرًا next إلى العقدة التالية. لا تحتاج خانات متجاورة في الذاكرة؛ يكفي أن تعرف كل عقدة جارتها.
class Node: def __init__(self, data): self.data = data self.next = None a = Node("أحمد")b = Node("سارة")c = Node("خالد")a.next = bb.next = c cur = awhile cur is not None: print(cur.data) cur = cur.next
>>> %Run main.py
أحمد
سارة
خالد
>>>
٢الإضافة في الأول: O(1)
هنا تتفوق القائمة المترابطة على list: الإضافة في الأول لا تزيح شيئًا. ننشئ عقدة جديدة تشير إلى الرأس القديم، ثم تصبح هي الرأس:
🔎 تتبّع: push_front
class Node: def __init__(self, data): self.data = data self.next = None head = Node("سارة")node = Node("أحمد")node.next = headhead = nodeprint(head.data, "←", head.next.data)
Variables · المتغيّرات في الذاكرة
٣القائمة المترابطة كاملة
نجمع العمليات في كلاس LinkedList. هذا هو مشروع الخطة الرسمية: «تنفيذ هيكل بيانات بسيط: إضافة وحذف وبحث»:
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None self.size = 0 def push_front(self, data): # O(1) node = Node(data) node.next = self.head self.head = node self.size += 1 def append(self, data): # O(n): نمر حتى الآخر node = Node(data) if self.head is None: self.head = node else: cur = self.head while cur.next is not None: cur = cur.next cur.next = node self.size += 1 def find(self, data): # O(n) cur, i = self.head, 0 while cur is not None: if cur.data == data: return i cur, i = cur.next, i + 1 return -1 def remove(self, data): # O(n) prev, cur = None, self.head while cur is not None: if cur.data == data: if prev is None: self.head = cur.next # حذف الرأس else: prev.next = cur.next # تخطي العقدة self.size -= 1 return True prev, cur = cur, cur.next return False def to_list(self): out, cur = [], self.head while cur is not None: out.append(cur.data) cur = cur.next return out names = LinkedList()names.append("سارة")names.append("خالد")names.push_front("أحمد")print(names.to_list(), names.size)print("موقع خالد:", names.find("خالد"))names.remove("سارة")print(names.to_list(), names.size)
>>> %Run main.py
['أحمد', 'سارة', 'خالد'] 3
موقع خالد: 2
['أحمد', 'خالد'] 2
>>>
٤الحذف: تخطَّ العقدة
لحذف عقدة من الوسط نجعل العقدة السابقة تشير إلى ما بعدها، فتخرج من السلسلة. لذلك نحتاج متغيرين أثناء المرور: prev و cur. وحذف الرأس حالة خاصة: الرأس الجديد هو التالي.
| الحالة | ما نفعل |
|---|---|
| القائمة فارغة | لا شيء: نُرجع False |
| العنصر في الرأس | head = head.next |
| العنصر في الوسط أو الآخر | prev.next = cur.next |
| العنصر غير موجود | نصل إلى None ونُرجع False |
٥مقارنة مع list
| العملية | list (مصفوفة) | القائمة المترابطة |
|---|---|---|
| الوصول إلى العنصر رقم i | O(1) | O(n): نمر من الرأس |
| الإضافة في الأول | O(n) | O(1) |
| الإضافة في الآخر | O(1) | O(n)، أو O(1) إن حفظنا مؤشرًا للذيل tail |
| الحذف من الأول | O(n) | O(1) |
| البحث | O(n) | O(n) |
| الذاكرة | خانات متجاورة | مؤشر إضافي لكل عنصر |
عمليًّا في بايثون تبقى list الأسرع لأغلب الاستخدامات. لكن فهم القائمة المترابطة أساس لتراكيب كثيرة: المكدس والطابور والأشجار والرسوم، وهي مستخدمة بكثرة في لغات مثل C و Java.
توقّع وتحقّق
ماذا تحفظ كل عقدة؟
data و next.الإضافة في أول القائمة المترابطة:
خطوتان.
الوصول إلى العنصر الخامس:
لا عناوين متجاورة.
حذف عقدة من الوسط:
تخطي العقدة.
الخلاصة
- العقدة:
dataوnext. والقائمة تحفظheadفقط. - الإضافة في الأول
O(1)، والوصول بالموقع والبحثO(n). - الحذف:
prev.next = cur.next، وحذف الرأس:head = head.next. listأسرع للوصول بالموقع، والمترابطة أسرع للإضافة والحذف من الأول.
تحدٍّ برمجي: اقلب القائمة المترابطة
متقدمأضف إلى LinkedList دالة reverse تقلب القائمة في المكان بتغيير المؤشرات فقط، دون إنشاء عقد جديدة.
المطلوب:
- ثلاثة متغيرات: prev و cur و nxt.
- في كل خطوة: احفظ cur.next، ثم اجعل
cur.next = prev، ثم تقدّم. - في الآخر:
head = prev. - اطبع القائمة قبل القلب وبعده.
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None self.size = 0 def push_front(self, data): # O(1) node = Node(data) node.next = self.head self.head = node self.size += 1 def append(self, data): # O(n): نمر حتى الآخر node = Node(data) if self.head is None: self.head = node else: cur = self.head while cur.next is not None: cur = cur.next cur.next = node self.size += 1 def find(self, data): # O(n) cur, i = self.head, 0 while cur is not None: if cur.data == data: return i cur, i = cur.next, i + 1 return -1 def remove(self, data): # O(n) prev, cur = None, self.head while cur is not None: if cur.data == data: if prev is None: self.head = cur.next # حذف الرأس else: prev.next = cur.next # تخطي العقدة self.size -= 1 return True prev, cur = cur, cur.next return False def to_list(self): out, cur = [], self.head while cur is not None: out.append(cur.data) cur = cur.next return out def reverse(self): pass lst = LinkedList()for x in [1, 2, 3, 4]: lst.append(x)print(lst.to_list())lst.reverse()print(lst.to_list())
[1, 2, 3, 4]
[4, 3, 2, 1]
💡 تلميح 1
nxt = cur.next أولًا، وإلا فقدت بقية القائمة.💡 تلميح 2
بعد الحلقة:
self.head = prevحاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None self.size = 0 def push_front(self, data): # O(1) node = Node(data) node.next = self.head self.head = node self.size += 1 def append(self, data): # O(n): نمر حتى الآخر node = Node(data) if self.head is None: self.head = node else: cur = self.head while cur.next is not None: cur = cur.next cur.next = node self.size += 1 def find(self, data): # O(n) cur, i = self.head, 0 while cur is not None: if cur.data == data: return i cur, i = cur.next, i + 1 return -1 def remove(self, data): # O(n) prev, cur = None, self.head while cur is not None: if cur.data == data: if prev is None: self.head = cur.next # حذف الرأس else: prev.next = cur.next # تخطي العقدة self.size -= 1 return True prev, cur = cur, cur.next return False def to_list(self): out, cur = [], self.head while cur is not None: out.append(cur.data) cur = cur.next return out def reverse(self): prev, cur = None, self.head while cur is not None: nxt = cur.next cur.next = prev prev = cur cur = nxt self.head = prev lst = LinkedList()for x in [1, 2, 3, 4]: lst.append(x)print(lst.to_list())lst.reverse()print(lst.to_list())