الفرق بين المراجعتين ل"Algorithms/linked lists"

من موسوعة حسوب
اذهب إلى التنقل اذهب إلى البحث
(مراجعتان متوسطتان بواسطة نفس المستخدم غير معروضتين)
سطر 1٬436: سطر 1٬436:
 
القائمة المترابطة بعد حذف العنصر في الموقع 4:  
 
القائمة المترابطة بعد حذف العنصر في الموقع 4:  
 
  8  2  3  1  
 
  8  2  3  1  
 +
</syntaxhighlight>
 +
 +
== البحث عن عنصر في القائمة المترابطة ==
 +
 +
يمكن البحث عن عنصر في القائمة المترابطة بطريقتين هما:
 +
 +
# الطريقة التكرارية iterative.
 +
# الطريقة التعاودية recursive.
 +
 +
=== الطريقة التكرارية ===
 +
 +
تتضمن الطريقة التكرارية الخطوات التالية:
 +
 +
# تهيئة مؤشرة العقدة، <code>current = head</code>
 +
# إنجاز ما يلي ما دامت قيمة <code>current</code> ليست <code>Null</code>
 +
## إن كانت <code>current-&gt;key</code> مساوية للمفتاح الذي المراد البحث عنه نعيد القيمة <code>true</code>.
 +
## إسناد <code>current-&gt;next</code> إلى <code>current</code>
 +
## إعادة القيمة <code>false</code>.
 +
تعرض الأمثلة التالية كيفية تنفيذ الطريقة التكرارية في البحث عن عقدة معينة في القائمة المترابطة وفي عدد من لغات البرمجة:<syntaxhighlight lang="c++">
 +
#include <bits/stdc++.h>
 +
using namespace std;
 +
 +
/* عقدة في القائمة المترابطة */
 +
class Node
 +
{
 +
public:
 +
int key;
 +
Node* next;
 +
};
 +
 +
/* تضيف هذه الدالة عقدة جديدة في مقدمة القائمة المترابطة
 +
باستخدام إشارة (مؤشر إلى مؤشر) إلى رأس القائمة والعدد الصحيح المعطى */
 +
 +
void push(Node** head_ref, int new_key)
 +
{
 +
/* حجز موقع للعقدة في الذاكرة */
 +
Node* new_node = new Node();
 +
 +
/* إضافة المفتاح */
 +
new_node->key = new_key;
 +
 +
/* فك ارتباط القائمة القديمة عن العقدة الجديدة */
 +
new_node->next = (*head_ref);
 +
 +
/* تحريك رأس القائمة ليشير إلى العقدة الجديدة */
 +
(*head_ref) = new_node;
 +
}
 +
 +
/* التحقق من أن القيمة المعطاة موجودة في القائمة المترابطة */
 +
bool search(Node* head, int x)
 +
{
 +
Node* current = head; // تهيئة العقدة الحالية
 +
while (current != NULL)
 +
{
 +
if (current->key == x)
 +
return true;
 +
current = current->next;
 +
}
 +
return false;
 +
}
 +
 +
/* اختبار الدوال السابقة*/
 +
int main()
 +
{
 +
/* البدء بقائمة مترابطة فارغة */
 +
Node* head = NULL;
 +
int x = 21;
 +
 +
/* push() استخدام الدالة
 +
لإنشاء القائمة المترابطة التالية:
 +
14->21->11->30->10 */
 +
push(&head, 10);
 +
push(&head, 30);
 +
push(&head, 11);
 +
push(&head, 21);
 +
push(&head, 14);
 +
 +
search(head, 21)? cout<<"Yes" : cout<<"No";
 +
return 0;
 +
}
 +
</syntaxhighlight>
 +
* '''بايثون''':
 +
<syntaxhighlight lang="python3">
 +
# صنف العقدة
 +
class Node:
 +
 +
# تهيئة كائن العقدة
 +
def __init__(self, data):
 +
self.data = data # Assign data
 +
self.next = None # Initialize next as null
 +
 +
# صنف القائمة المترابطة
 +
class LinkedList:
 +
def __init__(self):
 +
self.head = None # تهيئة رأس القائمة
 +
 +
# يدرج هذا التابع عقدة جديدة في بداية القائمة المترابطة
 +
def push(self, new_data):
 +
 +
# إنشاء عقدة جديدة
 +
new_node = Node(new_data)
 +
 +
# جعل رأس القائمة يلي العقدة الجديدة 
 +
new_node.next = self.head
 +
 +
# تحريك الرأس ليشير إلى العقدة الجديدة
 +
self.head = new_node
 +
 +
# تتحقق هذه الدالة من وجود القيمة المعطاة في القائمة المترابطة
 +
def search(self, x):
 +
 +
# تهيئة رأس القائمة الحالي
 +
current = self.head
 +
 +
# تنفيذ حلقة تكرارية إلى أن تصبح قيمة
 +
# None العقدة الحالية هي
 +
while current != None:
 +
if current.data == x:
 +
return True # data found
 +
 +
current = current.next
 +
 +
return False # لم يُعثر على البيانات المطلوبة
 +
 +
 +
# اختبار التوابع السابقة
 +
if __name__ == '__main__':
 +
 +
# البدء بقائمة مترابطة فارغة
 +
llist = LinkedList()
 +
 +
''' نستخدم التابع
 +
push()
 +
لإنشاء القائمة المترابطة التالية:
 +
14->21->11->30->10 '''
 +
llist.push(10);
 +
llist.push(30);
 +
llist.push(11);
 +
llist.push(21);
 +
llist.push(14);
 +
 +
if llist.search(21):
 +
print("Yes")
 +
else:
 +
print("No")
 +
 +
</syntaxhighlight>
 +
* جافا:
 +
<syntaxhighlight lang="java">
 +
//صنف العقدة
 +
class Node
 +
{
 +
int data;
 +
Node next;
 +
Node(int d)
 +
{
 +
data = d;
 +
next = null;
 +
}
 +
}
 +
 +
//صنف القائمة المترابطة
 +
class LinkedList
 +
{
 +
Node head; //رأس القائمة
 +
 +
//إدراج عقدة في بداية القائمة
 +
public void push(int new_data)
 +
{
 +
//حجز موقع للعقدة الجديدة في الذاكرة وإضافة البيانات
 +
Node new_node = new Node(new_data);
 +
 +
//جعل رأس القائمة يتلو العقدة التالية
 +
new_node.next = head;
 +
 +
//تحريك رأس القائمة ليشير إلى العقدة الجديدة
 +
head = new_node;
 +
}
 +
 +
//التحقق من كون القيمة المعطاة موجودة في القائمة المترابطة
 +
public boolean search(Node head, int x)
 +
{
 +
Node current = head; //تهيئة الرأس الحالي
 +
while (current != null)
 +
{
 +
if (current.data == x)
 +
return true; //عُثر على البيانات المطلوبة
 +
current = current.next;
 +
}
 +
return false; //لم يُعثر على البيانات المطلوبة
 +
}
 +
 +
//اختبار الدوال السابقة
 +
public static void main(String args[])
 +
{
 +
 +
//البدء بقائمة مترابطة فارغة
 +
LinkedList llist = new LinkedList();
 +
 +
/*استخدام التابع
 +
push()
 +
لإنشاء القائمة المترابطة التالية
 +
14->21->11->30->10 */
 +
llist.push(10);
 +
llist.push(30);
 +
llist.push(11);
 +
llist.push(21);
 +
llist.push(14);
 +
 +
if (llist.search(llist.head, 21))
 +
System.out.println("Yes");
 +
else
 +
System.out.println("No");
 +
}
 +
}
 +
</syntaxhighlight>تعطي الشيفرات السابقة المخرجات التالية:<syntaxhighlight lang="text">
 +
Yes
 +
</syntaxhighlight>
 +
 +
=== الطريقة التعاودية ===
 +
 +
تعمل الدالة <code>search(head, x)‎</code> بطريقة تعاودية وحسب الخطوات التالية:
 +
 +
# إن كانت قيمة الرأس تساوي <code>Null</code> تعيد الدالة القيمة <code>false</code>.
 +
# إن كان المفتاح الخاص بالرأس هو <code>x</code> نفسه، تعيد الدالة القيمة <code>true</code>.
 +
# فيما عدا ذلك تعيد الدالة ناتج استدعاء الدالة <code>search(head-&gt;next, x)‎</code>.
 +
 +
تعرض الأمثلة التالية كيفية تنفيذ عملية البحث بالطريقة التعاودية وفي عدد من لغات البرمجة:
 +
* '''C''':
 +
<syntaxhighlight lang="c">
 +
#include<stdio.h>
 +
#include<stdlib.h>
 +
#include<stdbool.h>
 +
/* عقدة في القائمة المترابطة */
 +
struct Node
 +
{
 +
int key;
 +
struct Node* next;
 +
};
 +
 +
/* تدرج الدالة عقدة جديدة في مقدمة القائمة المترابطة
 +
باستخدام إشارة (مؤشر إلى مؤشر) إلى رأس القائمة والعدد الصحيح المعطى
 +
*/
 +
 +
void push(struct Node** head_ref, int new_key)
 +
{
 +
/* حجز موقع العقدة في الذاكرة */
 +
struct Node* new_node =
 +
(struct Node*) malloc(sizeof(struct Node));
 +
 +
/* إضافة المفتاح */
 +
new_node->key = new_key;
 +
 +
/* فك الترابط بين القائمة المترابطة والعقدة الجديدة */
 +
new_node->next = (*head_ref);
 +
 +
/* تحريك رأس القائمة ليشير إلى العقدة الجديدة*/
 +
(*head_ref) = new_node;
 +
}
 +
 +
/* التحقق من كون القيمة المعطاة موجودة في القائمة المترابطة */
 +
bool search(struct Node* head, int x)
 +
{
 +
// الشرط الأساسي
 +
if (head == NULL)
 +
return false;
 +
 +
// نعيد قيمة صحيحة إن كان المفتاح المطلوب موجودًا في القائمة
 +
if (head->key == x)
 +
return true;
 +
 +
// تنفذ الدالة تعاوديًا للبحث عن المفتاح المطلوب
 +
return search(head->next, x);
 +
}
 +
 +
/* اختبار الدوال السابقة*/
 +
int main()
 +
{
 +
/* البدء بقائمة فارغة */
 +
struct Node* head = NULL;
 +
int x = 21;
 +
 +
/* تستخدم الدالة
 +
push()
 +
لإنشاء القائمة المترابطة التالية
 +
14->21->11->30->10 */
 +
push(&head, 10);
 +
push(&head, 30);
 +
push(&head, 11);
 +
push(&head, 21);
 +
push(&head, 14);
 +
 +
search(head, 21)? printf("Yes") : printf("No");
 +
return 0;
 +
}
 +
</syntaxhighlight>
 +
* '''بايثون''':
 +
<syntaxhighlight lang="python3">
 +
# صنف العقدة
 +
class Node:
 +
 +
# تهيئة كائن العقدة
 +
def __init__(self, data):
 +
self.data = data # Assign data
 +
self.next = None # Initialize next as null
 +
 +
# صنف القائمة المترابطة
 +
class LinkedList:
 +
def __init__(self):
 +
self.head = None # تهيئة رأس القائمة
 +
 +
# يدرج هذا التابع عقدة جديدة في بداية القائمة المترابطة
 +
def push(self, new_data):
 +
 +
# إنشاء عقدة جديدة
 +
new_node = Node(new_data)
 +
 +
# جعل رأس القائمة يلي العقدة الجديدة 
 +
new_node.next = self.head
 +
 +
# تحريك الرأس ليشير إلى العقدة الجديدة
 +
self.head = new_node
 +
 +
# تتحقق هذه الدالة من وجود القيمة المعطاة في القائمة المترابطة
 +
def search(self, li, key):
 +
 +
# الشرط الأساسي
 +
if(not li):
 +
return False
 +
 +
# نعيد قيمة صحيحة
 +
# إن كان المفتاح موجودًا في العقدة الحالية
 +
if(li.data == key):
 +
return True
 +
 +
# تنفذ الدالة تعاوديًا على بقية العقد في القائمة المترابطة
 +
return self.search(li.next, key)
 +
 +
 +
# اختبار التوابع السابقة
 +
if __name__ == '__main__':
 +
 +
# البدء بقائمة مترابطة فارغة
 +
llist = LinkedList()
 +
 +
''' نستخدم التابع
 +
push()
 +
لإنشاء القائمة المترابطة التالية:
 +
14->21->11->30->10 '''
 +
llist.push(10);
 +
llist.push(30);
 +
llist.push(11);
 +
llist.push(21);
 +
llist.push(14);
 +
 +
if llist.search(21):
 +
print("Yes")
 +
else:
 +
print("No")
 +
 +
</syntaxhighlight>
 +
* جافا:
 +
<syntaxhighlight lang="java">
 +
//صنف العقدة
 +
class Node
 +
{
 +
int data;
 +
Node next;
 +
Node(int d)
 +
{
 +
data = d;
 +
next = null;
 +
}
 +
}
 +
 +
//صنف القائمة المترابطة
 +
class LinkedList
 +
{
 +
Node head; //رأس القائمة
 +
 +
//إدراج عقدة في بداية القائمة
 +
public void push(int new_data)
 +
{
 +
//حجز موقع للعقدة الجديدة في الذاكرة وإضافة البيانات
 +
Node new_node = new Node(new_data);
 +
 +
//جعل رأس القائمة يتلو العقدة التالية
 +
new_node.next = head;
 +
 +
//تحريك رأس القائمة ليشير إلى العقدة الجديدة
 +
head = new_node;
 +
}
 +
 +
//التحقق من كون القيمة المعطاة موجودة في القائمة المترابطة
 +
public boolean search(Node head, int x)
 +
    {
 +
        // الشرط الأساسي
 +
        if (head == null)
 +
            return false;
 +
 
 +
        // نعيد قيمة صحيحة
 +
        // إن كان المفتاح موجودًا في العقدة الحالية
 +
        if (head.data == x)
 +
            return true;
 +
 
 +
        // تنفذ الدالة تعاودية على بقية العقد في القائمة المترابطة
 +
        return search(head.next, x);
 +
    } 
 +
 +
//اختبار الدوال السابقة
 +
public static void main(String args[])
 +
{
 +
 +
//البدء بقائمة مترابطة فارغة
 +
LinkedList llist = new LinkedList();
 +
 +
/*استخدام التابع
 +
push()
 +
لإنشاء القائمة المترابطة التالية
 +
14->21->11->30->10 */
 +
llist.push(10);
 +
llist.push(30);
 +
llist.push(11);
 +
llist.push(21);
 +
llist.push(14);
 +
 +
if (llist.search(llist.head, 21))
 +
System.out.println("Yes");
 +
else
 +
System.out.println("No");
 +
}
 +
}
 +
 
</syntaxhighlight>
 
</syntaxhighlight>
  
سطر 1٬449: سطر 1٬882:
  
 
* صفحة [https://www.geeksforgeeks.org/delete-a-linked-list-node-at-a-given-position/ Delete a Linked List node at a given position] في توثيق بنى المعطيات في موقع GeeksforGeeks.
 
* صفحة [https://www.geeksforgeeks.org/delete-a-linked-list-node-at-a-given-position/ Delete a Linked List node at a given position] في توثيق بنى المعطيات في موقع GeeksforGeeks.
 +
* صفحة [https://www.geeksforgeeks.org/search-an-element-in-a-linked-list-iterative-and-recursive/ Search an element in a Linked List (Iterative and Recursive)‎] في توثيق بنى المعطيات في موقع GeeksforGeeks.
 
[[تصنيف: الخوارزميات]]
 
[[تصنيف: الخوارزميات]]
 
[[تصنيف: بنى المعطيات]]
 
[[تصنيف: بنى المعطيات]]

مراجعة 08:47، 14 يونيو 2019


القوائم المترابطة Linked Lists بنى معطيات خطية Linear لا تخزّن فيها العناصر في مواقع متجاورة في الذاكرة، وترتبط العناصر بعضها ببعض فيها بواسطة المؤشرات.

يوضح الشكل التالي بنية القوائم المترابطة:

القوائم المترابطة.png

تتكون القوائم المترابطة من عقد، وتحتوي كل عقدة منها على حقل بيانات وإشارة (رابطة) إلى العقدة التالية في القائمة.

لماذا تستخدم القوائم المترابطة

يمكن استخدام المصفوفات لتخزين البيانات الخطية التي تكون من النوع ذاته، ولكن يعيب المصفوفات ما يلي:

  1. حجم المصفوفات ثابت، وهذا يعني أنّه يجب علينا معرفة الحد الأقصى للعناصر التي ستدخل في المصفوفة مسبقًا، إلى جانب أنّ المساحة المحجوزة في الذاكرة تكون مساوية للحد الأقصى للمصفوفة بصرف النظر عن عدد العناصر الموجودة فيها فعلًا.
  2. تستهلك عملية إضافة عنصر جديد إلى المصفوفة الكثير من الذاكرة؛ وذلك لأنّ إضافة عنصر جديد تعني إيجاد مكان له في المصفوفة، وهذا الأمر يعني بدوره إزاحة العناصر الموجودة في المصفوفة عن مواقعها.

لنفرض -على سبيل المثال- أنّ لدينا قائمة من المعرّفات المرتبة في مصفوفة: id[] = [1000, 1010, 1050, 2000, 2040]‎.

لو أردنا إضافة معرّف جديد يحمل القيمة 1005 دون الإخلال بترتيب العناصر، فيتحتّم علينا حينئذٍ تحريك جميع العناصر التي تلي المعرّف 1000.

عملية الحذف مكلفة أيضًا، إلا إذا استخدمنا بعض التقنيات الخاصة. فعلى سبيل المثال لنتمكّن من حذف المعرّف 1010 في المصفوفة السابقة يجب علينا تحريك جميع العناصر التي تلي المعرّف 1010.

القوائم المترابطة والمصفوفات

تختلف القوائم المترابطة عن المصفوفات بالنقاط التالية:

  1. المصفوفة هي بنية معطيات تحتوي على مجموعة من عناصر ذات نوع متشابه، في حين أنّ القوائم المترابطة تُعدّ من بنى المعطيات غير البدائية والتي تحتوي على مجموعة من العناصر المترابطة وغير المرتبة والتي تدعى بالعقد.
  2. تنتمي العناصر في المصفوفات إلى فهارس، بمعنى أنّه لغرض الوصول إلى العنصر الرابع في المصفوفة يجب كتابة اسم المتغير مع فهرسه أو موقعه ضمن أقواس مربعة.
  3. أما في القوائم المترابطة فيجب البدء من الرأس ثم المرور على العناصر واحدًا تلو الآخر إلى حين الوصول إلى العنصر الرابع.
  4. يمكن الوصول إلى عنصر ما في المصفوفة بسرعة، أما القوائم المترابطة فإنّ الوصول إلى العناصر فيها يأخذ وقتًا خطيًّا أكثر؛ ولهذا تكون القوائم المترابطة أبطأ قليلًا مقارنة بالمصفوفات.
  5. تستهلك عمليات مثل الإضافة والحذف الكثير من الوقت في المصفوفات، ولكنّها تكون سريعة في القوائم المترابطة.
  6. حجم المصفوفات ثابت، وذلك على عكس القوائم المترابطة التي تكون ذات حجم متغير وتمتاز بالمرونة والقابلية على تكبير أو تصغير حجمها حسب الحاجة.
  7. تُسند المعلومات إلى الذاكرة عن استخدام المصفوفات في وقت التصريف compile time، أما عند استخدام القوائم المترابطة فإنّ الذاكرة تُحجز في وقت التشغيل أو التنفيذ runtime.
  8. تخزن العناصر في المصفوفة بالترتيب، وتخزّن في القوائم المترابطة بصورة عشوائية.
  9. تتطلب المصفوفات مقدارًا أقل من الذاكرة وذلك نظرًا لتخزين البيانات الفعلية ضمن الفهرس، أما القوائم المترابطة فتحتاج بالمقابل إلى مقدار أكبر من الذاكرة وذلك لحاجتها إلى تخزين عناصر إضافية للإشارة إلى العقد السابقة واللاحقة.
  10. لا يمكن استخدام الذاكرة بكفاءة مع المصفوفات، وذلك على عكس القوائم المترابطة.

عيوب القوائم المترابطة

  1. لا يمكن الوصول إلى عناصر القوائم المترابطة بطريقة عشوائية، بل يجب الوصول إلى العناصر بالترتيب بدءًا من العقدة الأولى؛ ولذا لا يمكن إجراء عملية البحث الثنائي binary search بكفاءة إن استخدمنا الطريقة الافتراضية للتعامل مع القوائم المترابطة.
  2. يحتاج كل عنصر إلى مساحة إضافية في الذاكرة لارتباط كل عنصر بمؤشر.
  3. ليست ملائمة للذاكرة الخبيئة. لمّا كانت عناصر المصفوفة في مواقع متجاورة، فإن الإشارات إلى العناصر تكون في موقع واحد locality of reference، وهو أمر تفتقده القوائم المترابطة.

تمثيل القوائم المترابطة

تمثّل القائمة المترابطة بواسطة مؤشر pointer إلى العقدة الأولى في القائمة المترابطة. تدعى العقدة الأولى بالرأس head، وإن كانت القائمة المترابطة فارغة، فإنّ قيمة الرأس تكون NULL.

تتكوّن كل عقدة في القائمة من جزئين:

  1. البيانات.
  2. مؤشر Pointer (أو إشارة Reference) إلى العقدة التالية.

يمكن تمثيل العقدة في لغة C باستخدام البنى structures. يبين المثال التالي عقدة قائمة مترابطة مع بيانات عددية. 

struct Node 
{ 
  int data; 
  struct Node *next; 
};
  • Java, C#‎

أما في لغتي Java و C#‎ فيمكن تمثيل القوائم المترابطة بواسطة صنف والعقد بواسطة صنف آخر منفصل، ويحتوي صنف القائمة المترابطة على إشارة إلى صنف العقدة. 

// C#
class LinkedList 
{ 
	Node head; 

	class Node 
	{ 
		int data; 
		Node next; 
		
        // دالة بانية لإنشاء عقدة جديدة
		Node (int d) {data = d;} 
	} 
}

//Java
class LinkedList 
{ 
    Node head;
  
    // العقدة
    class Node 
    { 
        int data; 
        Node next; 
           
        // دالة بانية لإنشاء عقدة جديدة
        // أما القيمة العقدة اللاحقة فتهيئ تلقائيًا
        // null إلى القيمة
        Node(int d) {data = d;} 
    } 
}
  • بايثون:
# Node class 
class Node: 
   
    # دالة لتهيئة كائن العقدة
    def __init__(self, data): 
        self.data = data  # إسناد البيانات
        self.next = None  # تهيئة العقدة التالية لتكون فارغة 
   
# صنف القائمة المترابطة
class LinkedList: 
     
    # دالة لتهيئة كائن القائمة المترابطة  
    def __init__(self):  
        self.head = None

إنشاء القوائم المترابطة

تعرض الأمثلة التالية طريقة إنشاء القوائم المترابطة في عدد من لغات البرمجة:

  • C++‎:
#include <bits/stdc++.h> 
using namespace std; 

class Node 
{ 
	public: 
	int data; 
	Node *next; 
}; 

// ينشئ هذا البرنامج قائمة مترابطة بسيطة
// تمتلك ثلاث عقد
int main() 
{ 
	Node* head = NULL; 
	Node* second = NULL; 
	Node* third = NULL; 
	
// حجز مواقع لثلاث عقد
	head = new Node(); 
	second = new Node(); 
	third = new Node(); 

/* حجزت ثلاث كتل في الذاكرة ديناميكيًا
	ولدينا مؤشرات لهذه الكتل هي
	first, second, third
   
	head		 second		 third 
		|			 |			 | 
		|			 |			 | 
	+---+-----+	 +----+----+	 +----+----+ 
	| # | # |	 | # | # |	 | # | # | 
	+---+-----+	 +----+----+	 +----+----+ 
	
يمثل الرمز # أي قيمة عشوائية
البيانات عشوائية لأنّنا لم نسند أي قيمة حتى الآن */
	
head->data = 1; //نسند قيمة إلى العقدة الأولى 
head->next = second; // نربط العقدة الأولى بالثانية
	
/* 
أسندت البيانات إلى الجزء الخاص بالبيانات في الكتلة الأولى (رأس القائمة) ويشير المؤشر
اللاحق إلى الكتلة الثانية، وبهذا تكون الكتلتان متربطتين 

	head		 second		 third 
		|			 |			 | 
		|			 |			 | 
	+---+---+	 +----+----+	 +-----+----+ 
	| 1 | o----->| # | # |	 | # | # | 
	+---+---+	 +----+----+	 +-----+----+	 
*/
	
// إسناد قيمة إلى العقدة الثانية
second->data = 2; 

// ربط العقدة الثانية بالثالثة
second->next = third; 
	
/* 
أسندت قيمة إلى الجزء الخاص بالبيانات في الكتلة الثانية
ويشير المؤشر الخاص بالكتلة الثانية إلى الكتلة الثالثة
وهكذا تصبح الكتلتان متربطتين
	
	head		 second		 third 
		|			 |			 | 
		|			 |			 | 
	+---+---+	 +---+---+	 +----+----+ 
	| 1 | o----->| 2 | o-----> | # | # | 
	+---+---+	 +---+---+	 +----+----+	 */	
	
third->data = 3; //إسناد قيمة إلى العقدة الثالثة
third->next = NULL; 
	
/* 
أسندت قيمة إلى الجزء الخاص بالبيانات في العقدة الثالثة
Null ويشير المؤشر اللاحق في الكتلة الثالثة إلى القيمة
للإشارة إلى انتهاء القائمة المترابطة في هذا الموضع

		head	 
			| 
			| 
		+---+---+	 +---+---+	 +----+------+ 
		| 1 | o----->| 2 | o-----> | 3 | NULL | 
		+---+---+	 +---+---+	 +----+------+	 
	
لاحظ أنّ رأس القائمة كافٍ لتمثيل القائمة بأكملها.
ويمكن التنقل عبر عناصر القائمة كلّها باتباع المؤشر اللاحق
*/
    
return 0; 
}
  • بايثون:
# صنف العقدة
class Node: 

	# دالة لتهيئة كائن العقدة
	def __init__(self, data): 
		self.data = data # إسناد البيانات
		self.next = None # null تهيئة العقدة اللاحقة لتكون


# صنف القائمة المترابطة الذي يحتوي على كائن عقدة
class LinkedList: 

	# تهيئة رأس القائمة
	def __init__(self): 
		self.head = None


if __name__=='__main__': 

	# نبدأ بقائمة مترابطة فارغة
	llist = LinkedList() 

	llist.head = Node(1) 
	second = Node(2) 
	third = Node(3) 

	''' 
	حجزت ثلاث كتل في الذاكرة ديناميكيًا
	ولدينا مؤشرات لهذه الكتل هي
	first, second, third

	llist.head	 second			 third 
		|			 |				 | 
		|			 |				 | 
	+----+------+	 +----+------+	 +----+------+ 
	| 1 | None |	 | 2 | None |	 | 3 | None | 
	+----+------+	 +----+------+	 +----+------+ 
	'''

	llist.head.next = second; # ربط العقدة الأولى بالثانية

	''' 
	تشير العقدة الأولى الآن إلى العقدة الثانية، وبهذا تكونان مترابطتين

	llist.head	 second			 third 
		|			 |				 | 
		|			 |				 | 
	+----+------+	 +----+------+	 +----+------+ 
	| 1 | o-------->| 2 | null |	 | 3 | null | 
	+----+------+	 +----+------+	 +----+------+ 
	'''

	second.next = third; # ربط العقدة الثانية بالثالثة

	''' 
	تشير العقدة الثانية إلى العقدة الثالثة، وبهذا تكونان مترابطتين


	llist.head	 second			 third 
		|			 |				 | 
		|			 |				 | 
	+----+------+	 +----+------+	 +----+------+ 
	| 1 | o-------->| 2 | o-------->| 3 | null | 
	+----+------+	 +----+------+	 +----+------+ 
	'''
  • جافا:
class LinkedList 
{ 
	Node head; // رأس القائمة

	/* عقدة القائمة المترابطة */
	static class Node { 
		int data; 
		Node next; 
		Node(int d) { data = d; next=null; } // دالة بانية
	} 

	/* تابع لإنشاء قائمة مترابطة بسيطة تضمّ ثلاثة ععقد */
	public static void main(String[] args) 
	{ 
		/* نبدأ بقائمة فارغة */
		LinkedList llist = new LinkedList(); 

		llist.head = new Node(1); 
		Node second = new Node(2); 
		Node third = new Node(3); 

		/* تحجز ثلاث عقد مكانًا في الذاكرة ديناميكيًا
		ولدينا إشارات إلى هذه الكتل هي
		first, second, third

		llist.head	 second			 third 
			|			 |				 | 
			|			 |				 | 
		+----+------+	 +----+------+	 +----+------+ 
		| 1 | null |	 | 2 | null |	 | 3 | null | 
		+----+------+	 +----+------+	 +----+------+ */

		llist.head.next = second; // ربط العقدة الأولى بالثانية

		/* تشير العقدة الأولى الآن إلى العقدة الثانية
		وهكذا تصبح العقدتان متربطتين

		llist.head	 second			 third 
			|			 |				 | 
			|			 |				 | 
		+----+------+	 +----+------+	 +----+------+ 
		| 1 | o-------->| 2 | null |	 | 3 | null | 
		+----+------+	 +----+------+	 +----+------+ */

		second.next = third; // ربط العقدة الثانية بالعقدة الثالثة

		/* والآن تشير العقدة الثانية إلى العقدة الثالثة
		وهكذا تصبح العقدتان مرتبطتين 

		llist.head	 second			 third 
			|			 |				 | 
			|			 |				 | 
		+----+------+	 +----+------+	 +----+------+ 
		| 1 | o-------->| 2 | o-------->| 3 | null | 
		+----+------+	 +----+------+	 +----+------+ */
	} 
}

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

توضح الأمثلة التالية طريقة التنقل عبر العقد في القوائم المترابطة في عدد من لغات البرمجة:

C++‎:

#include <bits/stdc++.h> 
using namespace std; 

class Node 
{ 
	public: 
	int data; 
	Node *next; 
}; 

// تطبع هذه الدالة محتويات القائمة المترابطة
// بدءًا من العقدة المعطاة
void printList(Node *n) 
{ 
	while (n != NULL) 
	{ 
		cout << n->data << " "; 
		n = n->next; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	Node* head = NULL; 
	Node* second = NULL; 
	Node* third = NULL; 
	
	// حجز ثلاث عقد في الذاكرة
	head = new Node(); 
	second = new Node(); 
	third = new Node(); 

	head->data = 1; //إسناد البيانات إلى العقدة الأولى
	head->next = second; // ربط العقدة الأولى بالثانية

	second->data = 2; //إسناد البيانات إلى العقدة الثانية
	second->next = third; 

	third->data = 3; //إسناد البيانات إلى العقدة الثالثة
	third->next = NULL; 
	
	printList(head); 

	return 0; 
}
  • بايثون:
# صنف العقدة
class Node: 

	# دالة لتهيئة كائن العقدة
	def __init__(self, data): 
		self.data = data # إسناد البيانات
		self.next = None # null تهيئة العقدة اللاحقة لتكون


# صنف قائمة مترابطة يضم كائن عقدة
class LinkedList: 

	# تهيئة رأس القائمة
	def __init__(self): 
		self.head = None

	# تطبع هذه الدالة محتويات القائمة المترابطة
    # بدءًا من العقدة المعطاة
	def printList(self): 
		temp = self.head 
		while (temp): 
			print temp.data, 
			temp = temp.next


if __name__=='__main__': 

	# البدء بقائمة مترابطة فارغة
	llist = LinkedList() 

	llist.head = Node(1) 
	second = Node(2) 
	third = Node(3) 

	llist.head.next = second; # ربط العقدة الأولى بالثانية
	second.next = third; # ربط العقدة الثانية بالثالثة

	llist.printList()
  • جافا:
class LinkedList 
{ 
	Node head; // رأس القائمة

	/* عقدة في القائمة المترابطة */
	static class Node { 
		int data; 
		Node next; 
		Node(int d) { data = d; next=null; } // دالة بانية
	} 

	/* تطبع هذه الدالة محتويات القائمة المترابطة بدءًا من رأس القائمة */
	public void printList() 
	{ 
		Node n = head; 
		while (n != null) 
		{ 
			System.out.print(n.data+" "); 
			n = n.next; 
		} 
	} 

	/* ينشئ التابع قائمة مترابطة تضمّ ثلاث عقد */
	public static void main(String[] args) 
	{ 
		/* البدء بقائمة مترابطة فارغة*/
		LinkedList llist = new LinkedList(); 

		llist.head	 = new Node(1); 
		Node second	 = new Node(2); 
		Node third	 = new Node(3); 

		llist.head.next = second; // ربط العقدة الأولى بالثانية
		second.next = third; // ربط العقدة الثانية بالثالثة

		llist.printList(); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

1 2 3

إضافة العقد إلى القوائم المترابطة

يمكن إضافة العقد إلى القائمة المترابطة في مواضع ثلاث هي:

  1. في بداية القائمة المترابطة.
  2. بعد عقدة معينة.
  3. في نهاية القائمة المترابطة.

إضافة عقدة إلى بداية القائمة المترابطة

تضاف العقدة الجديدة دائمًا قبل الرأس الخاص بالقائمة المترابطة، وتصبح العقدة الجديدة رأس تلك القائمة. فعلى سبيل المثال إن كان لدينا القائمة المترابطة التالية: 10->15->20->25 وأضفنا الرقم 5 إلى بداية القائمة، فإنّها ستصبح بالصورة التالية: 5->10->15->20->25.

لو أسمينا الدالة التي ستضيف العنصر الجديد إلى بداية القائمة المترابطة بالاسم push()‎ فيجب على هذه الدالة أن تستقبل مؤشرًا خاصًّا بمؤشر الرأس؛ وذلك لوجوب إشارة هذا المؤشر إلى العقدة الجديدة.

إنّ مقدار تعقيد الوقت الخاص بالدالة push()‎ هو O(1)‎ وذلك لأنّها تؤدي مقدارًا ثابتًا من العمل.

إضافة عقدة بعد عقدة موجودة

يكون لدينا في هذه الحالة مؤشر إلى عقدة معينة، ونرغب في إضافة عقدة جديدة بعدها.

إن مقدار تعقيد الوقت الخاص بالدالة insertAfter()‎ هو O(q)‎ لأنّها تؤدي مقدارًا ثابتًا من العمل.

إضافة عقدة إلى نهاية القائمة المترابطة

تضاف العقدة الجديدة دائمًا بعد العقدة الأخيرة في القائمة المترابطة. فعلى سبيل المثال إن كانت لدينا القائمة المترابطة التالية: 5->10->15->20->25 وأردنا إضافة العنصر 30 إلى نهاية القائمة، فإنّ القائمة المترابطة تصبح بالصورة التالية: 5->10->15->20->25->30.

ولما كان الرأس يمثّل القائمة المترابطة عادةً، فيجب علينا أن نمر على عناصر القائمة وصولًا إلى نهايتها، ثم تغيير العقدة التالية للعقدة الأخيرة لتصبح العقدة الجديدة.

يكون مقدار تعقيد الوقت لهذه العملية هو O(n)‎ وتمثل n عد العقد الموجودة في القائمة المترابطة، ولما كان المرور على عناصر القائمة جزءًا من عمل الدالة، فإنّ الدالة تؤدي O(n)‎ من العمل.

يمكن تحسين عمل هذه الدالة لتعمل بمقدار تعقيد O(1)‎ وذلك بالإبقاء على مؤشر إضافي في نهاية القائمة المترابطة.

أمثلة

تعرض الأمثلة التالية طرق الإضافة الثلاثة وفي عدد من لغات البرمجة:

  • C++‎
#include <bits/stdc++.h> 
using namespace std; 

// عقدة قائمة مترابطة
class Node 
{ 
	public: 
	int data; 
	Node *next; 
}; 

/* إدراج عقدة جديدة في مقدّمة القائمة
باستخدام الإشارة (مؤشر إلى المؤشر) إلى رأس القائمة
والعدد الصحيح المعطى */
void push(Node** head_ref, int new_data) 
{ 
	/* 1. حجز موقع العقدة في الذاكرة */
	Node* new_node = new Node(); 

	/* 2. إضافة البيانات */
	new_node->data = new_data; 

	/* 3. جعل رأس القائمة هو العقدة التالية للعقدة الجديدة */
	new_node->next = (*head_ref); 

	/* 4. تحريك رأس القائمة ليشير إلى العقدة الجديدة */
	(*head_ref) = new_node; 
} 

/* إدراج عقدة بعد العقدة السابقة المعطاة */
void insertAfter(Node* prev_node, int new_data) 
{ 
	/*1. Null التحقق من أنّ العقدة السابقة المعطاة تحمل القيمة */
	if (prev_node == NULL) 
	{ 
		cout<<"the given previous node cannot be NULL"; 
		return; 
	} 

	/* 2. حجز موقع العقدة الجديدة في الذاكرة */
	Node* new_node = new Node(); 

	/* 3. إضافة البيانات */
	new_node->data = new_data; 

	/* 4. جعل العقدة اللاحقة للعقدة الجديدة هي العقدة اللاحقة للعقدة السابقة */
	new_node->next = prev_node->next; 

	/* 5. تحريك العقدة التالية للعقدة السابقة لتصبح العقدة الجديدة */
	prev_node->next = new_node; 
} 

/* إلحاق عقدة جديدة في نهاية القائمة باستخدام
الإشارة (مؤشر إلى مؤشر) إلى رأس القائمة والعدد الصحيح المعطى */

void append(Node** head_ref, int new_data) 
{ 
	/* 1. حجز موقع العقدة الجديدة في الذاكرة */
	Node* new_node = new Node(); 

	Node *last = *head_ref; /* يستخدم في الخطوة 5*/

	/* 2. إدراج البيانات */
	new_node->data = new_data; 

	/* 3. ستكون العقدة الجديدة هي العقدة الأخير في القائمة
	لذا سنجعل العقدة اللاحقة لها هي
	NULL*/
	new_node->next = NULL; 

	/* 4. إن كانت القائمة فارغةً
	ستكون العقدة الجديدة في رأس القائمة*/
	if (*head_ref == NULL) 
	{ 
		*head_ref = new_node; 
		return; 
	} 

	/* 5. وإن لم تكن القائمة فارغة ننقل العقدة الجديدة إلى نهاية القائمة */
	while (last->next != NULL) 
		last = last->next; 

	/* 6. نغير العقدة اللاحقة للعقدة الأخيرة. */
	last->next = new_node; 
	return; 
} 

// تطبع هذه الدالة محتويات القائمة المترابطة
// بدءًا من رأس القائمة
void printList(Node *node) 
{ 
	while (node != NULL) 
	{ 
		cout<<" "<<node->data; 
		node = node->next; 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	/* البدء بقائمة فارغة */
	Node* head = NULL; 
	
	// إدراج العنصر 6
	// لتصبح القائمة بالشكل التالي
    // 6->NULL 
	append(&head, 6); 
	
	// إدراج العنصر 7 في بداية القائمة 
	// فتصبح القائمة بالشكل التالي
    // 7->6->NULL 
	push(&head, 7); 
	
	// إدراج العنصر 1 في بداية القائمة
    // فتصبح القائمة بالشكل التالي
    // 1->7->6->NULL 
	push(&head, 1); 
	
	// إدراج العنصر 4 في نهاية القائمة
    // فتصبح القائمة بالشكل التالي
	append(&head, 4); 
	
	// إدراج العنصر 8 بعد العنصر 7
    // لتصبح القائمة بالشكل التالي
	insertAfter(head->next, 8); 
	
	cout<<"Created Linked list is: "; 
	printList(head); 
	
	return 0; 
}
  • بايثون:
# صنف العقدة
class Node: 

	# دالة لتهيئة كائن العقدة 
	def __init__(self, data): 
		self.data = data # إسناد البيانات
		self.next = None # null تهيئة العقدة اللاحقة لتكون


# يتضمّن صنف القائمة المترابطة كائن عقدة
class LinkedList: 

	# دالة لتهيئة رأس القائمة
	def __init__(self): 
		self.head = None


	# دالة لإدراج عقدة في بداية القائمة
	def push(self, new_data): 

		# 1: حجزم موقع العقدة في الذاكرة
		# 2: إضافة البيانات
		new_node = Node(new_data) 

		# 3. جعل العقدة اللاحقة للعقدة الجديدة كرأس للقائمة
		new_node.next = self.head 

		# 4: تحريك رأس القائمة ليشير إلى العقدة الجديدة.
		self.head = new_node 


	# يدرج هذا التابع عقدة جديدة بعد عقدة معطاة
	def insertAfter(self, prev_node, new_data): 

		# 1: التحقق من أنّ العقدة المعطاة موجودة في القائمة المترابطة فعلاً
		if prev_node is None: 
			print "The given previous node must inLinkedList."
			return

		# 2: إنشاء عقدة جديدة
        # 3: إضافة البيانات
		new_node = Node(new_data) 

		# 4: جعل العقدة التي تلي العقدة الجديدة هي العقدة التي تلي العقدة المعطاة
		new_node.next = prev_node.next

		# 5: جعل العقدة الجديدة هي العقدة التي تلي العقدة المعطاة
		prev_node.next = new_node 


	# يُلحق التابع عقدة جديدة في نهاية القائمة المترابطة
	def append(self, new_data): 

		# 1: إنشاء عقدة جديدة
        # 2: إضافة البيانات
        # 3: None جعل ما يلي العقدة هو 
		new_node = Node(new_data) 

        # 4: نجعل العقدة الجديدة رأسًا للقائمة
        # إن كانت القائمة المترابطة فارغة
		if self.head is None: 
			self.head = new_node 
			return

		# 5: وإلا فننتقل عبر عناصر القائمة وصولًا إلى العقدة الأخيرة
		last = self.head 
		while (last.next): 
			last = last.next

		# 6: نغير ما يلي العقدة الأخيرة
		last.next = new_node 


	# تابع مساعد لطباعة محتويات القائمة المترابطة
	def printList(self): 
		temp = self.head 
		while (temp): 
			print temp.data, 
			temp = temp.next



# اختبار التوابع السابقة
if __name__=='__main__': 

	# نبدأ بقائمة فارغة
	llist = LinkedList() 

	# ندرج العنصر 6 في القائمة فتصبح
    # 6->None 
	llist.append(6) 

	# ندرج العنصر 7 في بداية القائمة فتصبح
    # 7->6->None 
	llist.push(7); 

	# ندرج العنصر 1 في بداية القائمة فتصبح
    # 1->7->6->None 
	llist.push(1); 

	# ندرج العنصر 4 في نهاية القائمة فتصبح
    # 1->7->6->4->None 
	llist.append(4) 

	# ندرج العنصر 8 بعد العنصر 7 في القائمة فتصبح
    # 1 -> 7-> 8-> 6-> 4-> None 
	llist.insertAfter(llist.head.next, 8) 

	print 'Created linked list is:', 
	llist.printList()
  • جافا:
class LinkedList 
{ 
	Node head; // رأس القائمة 

	// عقدة قائمة مترابطة

	class Node 
	{ 
		int data; 
		Node next; 
		Node(int d) {data = d; next = null; } 
	} 

	/* إدراج عقدة جديدة في مقدّمة القائمة */
	public void push(int new_data) 
	{ 
		/* 
		1: حجز موقع العقدة في الذاكرة
		2: إضافة المعلومات */
		Node new_node = new Node(new_data); 

		/* 3. جعل رأس القائمة يتلو العقدة الجديدة */
		new_node.next = head; 

		/* 4. تحريك رأس القائمة ليشير إلى العقدة الجديدة */
		head = new_node; 
	} 

	/* يدرج التابع عقدة بعد العقدة المعطاة */
	public void insertAfter(Node prev_node, int new_data) 
	{ 
		/* 1. التحقق من وجود العقدة المعطاة في القائمة المترابطة */
		if (prev_node == null) 
		{ 
			System.out.println("The given previous node cannot be null"); 
			return; 
		} 

		/* 2: تعيين موقع العقدة في الذاكرة
		3: إضافة البيانات
		*/ 
		Node new_node = new Node(new_data); 

		/* 4. جعل ما يلي العقدة الجديدة هو ما يلي العقدة السابقة */
		new_node.next = prev_node.next; 

		/* 5. جعل العقدة الجديدة تلي العقدة السابقة */
		prev_node.next = new_node; 
	} 
	
    /* يلحق التابع عقدة جديدة في نهاية القائمة المترابطة */ 
	public void append(int new_data) 
	{ 
		/* 1: حجز موقع العقدة في الذاكرة
		2: إضافة البيانات
		3: null جعل ما يلي العقدة الجديدة هو
		*/
		Node new_node = new Node(new_data); 

		/* نجعل العقدة الجديدة رأساً للقائمة إن كانت القائمة فارغة */
		if (head == null) 
		{ 
			head = new Node(new_data); 
			return; 
		} 

		/* 4. ستكون العقدة الجديدة هي العقدة الأخيرة في القائمة
		null لذا سنجعل ما يليها هو */
		new_node.next = null; 
		
        /* 5. وإلا فسنتنقل عبر عناصر القائمة وصولًا إلى العقدة الأخيرة */
		Node last = head; 
		while (last.next != null) 
			last = last.next; 

		/* 6. نغير ما يلي العقدة الأخيرة */
		last.next = new_node; 
		return; 
	} 

	/* يطبع هذا التابع محتويات القائمة المترابطة بدءًا من العقدة المعطاة */
	public void printList() 
	{ 
		Node tnode = head; 
		while (tnode != null) 
		{ 
			System.out.print(tnode.data+" "); 
			tnode = tnode.next; 
		} 
	} 

	/* اختبار الشيفرة السابقة */

	public static void main(String[] args) 
	{ 
		/* البدء بقائمة فارغة */
		LinkedList llist = new LinkedList(); 

		// ندرج العنصر 6 في القائمة فتصبح
        // 6->NUllist 
		llist.append(6); 

		// ندرج العنصر 7 في بداية القائمة فتصبح 
		// 7->6->NUllist 
		llist.push(7); 

		// ندرج العنصر 1 في بداية القائمة فتصبح
		// 1->7->6->NUllist 
		llist.push(1); 

		// ندرج العنصر 4 في نهاية القائمة فتصبح
		// 1->7->6->4->NUllist 
		llist.append(4); 

		// ندرج العنصر 8 بعد العنصر 7 في القائمة فتصبح
		// 1->7->8->6->4->NUllist 
		llist.insertAfter(llist.head.next, 8); 

		System.out.println("\nCreated Linked list is: "); 
		llist.printList(); 
	} 
}

حذف العقد من القوائم المترابطة

تتمّ عملية حذف العقد من القوائم المترابطة بحسب الخطوات التالية:

  1. إيجاد العقدة السابقة للعقدة المراد حذفها.
  2. تغيير العقدة التالية للعقدة السابقة.
  3. إفراغ الذاكرة المحجوزة من قبل العقدة المراد حذفها.

يوضّح الشكل التالي عملية حذف عقدة من القائمة المترابطة:

remove node.png

تحجز لغة C الذاكرة ديناميكيًا لكل عقدة في القائمة المترابطة باستخدام الدالة malloc()‎؛ ولهذا يجب استدعاء الدالة free()‎ لإفراغ الجزء المحجوز من الذاكرة من قبل العقدة المراد حذفها.

تعرض الأمثلة التالية طريقة حذف عقدة من القائمة المترابطة في عدد من لغات البرمجة:

  • C++‎:
#include <stdio.h> 
#include <stdlib.h> 

// عقدة في القائمة المترابطة
struct Node 
{ 
	int data; 
	struct Node *next; 
}; 

/* تدرج الدالة عقدة جديدة في مقدمة القائمة
باستخدام إشارة (مؤشر إلى مؤشر) إلى رأس القائمة والعدد الصحيح المعطى */

void push(struct Node** head_ref, int new_data) 
{ 
	struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); 
	new_node->data = new_data; 
	new_node->next = (*head_ref); 
	(*head_ref) = new_node; 
} 

/* تحذف الدالة أول ظهور للمفتاح المعطى في القائمة المترابطة
باستخدام إشارة (مؤشر إلى مؤشر) إلى رأس القائمة والمفتاح المعطى */

void deleteNode(struct Node **head_ref, int key) 
{ 
	// تخزين عقد رأس القائمة
	struct Node* temp = *head_ref, *prev; 

    // إن كانت عقدة رأس القائمة هي العقدة التي تتضمّن المفتاح المراد حذفه

	if (temp != NULL && temp->data == key) 
	{ 
		*head_ref = temp->next; // تغيير رأس القائمة
		free(temp);			 // التخلص من رأس القائمة القديم
		return; 
	} 

    // البحث عن المفتاح المراد حذفه مع متابعة
    // العقدة السابقة وذلك لأننا نحتاج إلى
    // تغيير العقدة السابقة لتصبح العقدة اللاحقة
    // 'prev->next' 
	while (temp != NULL && temp->data != key) 
	{ 
		prev = temp; 
		temp = temp->next; 
	} 

    // إن كان المفتاح غير موجود في القائمة المترابطة
	if (temp == NULL) return; 

	// فك ارتباط العقدة من القائم المترابطة
	prev->next = temp->next; 

	free(temp); // Free memory 
} 

// تطبع هذه الدالة محتويات القائمة المترابطة بدءًا من العقدة المعطاة
void printList(struct Node *node) 
{ 
	while (node != NULL) 
	{ 
		printf(" %d ", node->data); 
		node = node->next; 
	} 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
	/* البدء بعقدة فارغة */
	struct Node* head = NULL; 

	push(&head, 7); 
	push(&head, 1); 
	push(&head, 3); 
	push(&head, 2); 

	puts("Created Linked List: "); 
	printList(head); 
	deleteNode(&head, 1); 
	puts("\nLinked List after Deletion of 1: "); 
	printList(head); 
	return 0; 
}
  • بايثون:
# صنف العقدة
class Node: 

	# دالة بانية لتهيئة كائن العقدة
	def __init__(self, data): 
		self.data = data 
		self.next = None

class LinkedList: 

	# تهيئة رأس القائمة
	def __init__(self): 
		self.head = None

	# تدرج الدالة عقدة جديدة في بداية القائمة المترابطة
	def push(self, new_data): 
		new_node = Node(new_data) 
		new_node.next = self.head 
		self.head = new_node 

    # تحذف الدالة أول ظهور للمفتاح المعطى في القائمة المترابطة
    # وذلك باستخدام إشارة إلى رأس القائمة والمفتاح المعطى
	def deleteNode(self, key): 
		
		# تخزين عقدة الرأس
		temp = self.head 

		# إن كانت عقدة الرأس تحمل قيمة المفتاح المعطى
		if (temp is not None): 
			if (temp.data == key): 
				self.head = temp.next
				temp = None
				return

        # البحث عن المفتاح المراد حذفه مع متابعة
        # العقدة السابقة لأنّنا نحتاجها لتغير العقدة اللاحقة للعقدة السابقة
        #'prev.next' 
		while(temp is not None): 
			if temp.data == key: 
				break
			prev = temp 
			temp = temp.next

		# إن كان المفتاح غير موجود في القائمة المترابطة
		if(temp == None): 
			return

		# فك ارتباط العقدة بالقائمة المترابطة
		prev.next = temp.next

		temp = None


	# Utility function to print the linked LinkedList 
	def printList(self): 
		temp = self.head 
		while(temp): 
			print " %d" %(temp.data), 
			temp = temp.next


# اختبار الدوال السابقة
llist = LinkedList() 
llist.push(7) 
llist.push(1) 
llist.push(3) 
llist.push(2) 

print "Created Linked List: "
llist.printList() 
llist.deleteNode(1) 
print "\nLinked List after Deletion of 1:"
llist.printList()
  • جافا:
class LinkedList 
{ 
	Node head; // راس القائمة

	/* عقدة القائمة المترابطة */
	class Node 
	{ 
		int data; 
		Node next; 
		Node(int d) 
		{ 
			data = d; 
			next = null; 
		} 
	} 

    /* يحذف التابع أول ظهور للمفتاح المعطى في القائمة المترابطة */
    
	void deleteNode(int key) 
	{ 
		// تخزين عقدة الرأس
		Node temp = head, prev = null; 

        // إن كانت عقدة الرأس نفسها تتضمّن المفتاح المراد حذفه
		if (temp != null && temp.data == key) 
		{ 
			head = temp.next; // تغيير رأس القائمة
			return; 
		} 

        // البحث عن المفتاح المراد حذفه، مع متابعة
        // العقدة السابقة لأننا نحتاج إلى تغيير العقدة اللاحقة
        // temp.next
		while (temp != null && temp.data != key) 
		{ 
			prev = temp; 
			temp = temp.next; 
		}	 

		// إن كان المفتاح غير موجود في القائمة المترابطة
		if (temp == null) return; 

        // فك ارتباط العقدة بالقائمة المترابطة
		prev.next = temp.next; 
	} 

	/* يدرج التابع عقدة جديدة في بداية القائمة المترابطة */
	public void push(int new_data) 
	{ 
		Node new_node = new Node(new_data); 
		new_node.next = head; 
		head = new_node; 
	} 

	/* تطبع هذه الدالة محتويات القائمة المترابطة بدءًا من العقدة المعطاة */
	public void printList() 
	{ 
		Node tnode = head; 
		while (tnode != null) 
		{ 
			System.out.print(tnode.data+" "); 
			tnode = tnode.next; 
		} 
	} 

        // اختبار التوابع السابقة
	public static void main(String[] args) 
	{ 
		LinkedList llist = new LinkedList(); 

		llist.push(7); 
		llist.push(1); 
		llist.push(3); 
		llist.push(2); 

		System.out.println("\nCreated Linked list is:"); 
		llist.printList(); 

		llist.deleteNode(1); // حذف العقدة في الموقع 1 

		System.out.println("\nLinked List after Deletion at position 4:"); 
		llist.printList(); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

القائمة المترابطة المُنشاة
 2  3  1  7
القائمة المترابطة بعد حذف العنصر 1
 2  3  7

حذف عقدة من قائمة مترابطة بالاعتماد على الموقع

إن كانت العقدة المراد حذفها هي العقدة الأولى فيمكن حذفها مباشرة، وإلا فيجب أن يكون هناك مؤشر إلى العقدة السابقة للعقدة المراد حذفها؛ ولهذا إن كان الموقع أي شيء عدا الصفر، فيجب تنفيذ حلقة تكرارية بعدد (الموقع - 1) مرة للحصول على مؤشر العقدة السابقة.

تعرض الأمثلة التالية طريقة حذف عقدة من قائمة مترابطة بالاعتماد على الموقع:

  • C++‎:
#include <stdio.h> 
#include <stdlib.h> 

// عقدة في القائمة المترابطة
struct Node 
{ 
	int data; 
	struct Node *next; 
}; 

/* تدرج الدالة التالية عقدة جديدة في مقدمة القائمة المترابطة
وذلك باستخدام إشارة (مؤشر إلى مؤشر) لرأس القائمة والعدد الصحيح المعطى */
void push(struct Node** head_ref, int new_data) 
{ 
	struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); 
	new_node->data = new_data; 
	new_node->next = (*head_ref); 
	(*head_ref) = new_node; 
} 

/* تحذف الدالة التالية العقدة الموجودة في الموقع المعطى
وذلك باستخدام إشارة (مؤشر إلى مؤشر) لرأس القائمة والموقع المعطى */
void deleteNode(struct Node **head_ref, int position) 
{ 
// إن كانت القائمة المترابطة فارغة
if (*head_ref == NULL) 
	return; 

// تخزين عقدة رأس القائمة
struct Node* temp = *head_ref; 

	// إن كانت العقدة المراد حذفها
	if (position == 0) 
	{ 
		*head_ref = temp->next; // تغيير رأس القائمة
		free(temp);			 // التخلص من رأس القائمة السابق
		return; 
	} 

	// العثور على العقدة السابقة للعقدة المراد حذفها
	for (int i=0; temp!=NULL && i<position-1; i++) 
		temp = temp->next; 

	// إن كان الموقع أكبر من عدد العقد
	if (temp == NULL || temp->next == NULL) 
		return; 

	// temp->next
	// هي العقدة التي يجب حذفها
	// تخزين المؤشر إلى العقدة التالية المراد حذفها
	struct Node *next = temp->next->next; 

	// فك ارتباط العقدة من القائمة المترابطة
	free(temp->next); // إفراغ الذاكرة التي تشغلها العقدة

	temp->next = next; // فك ارتباط العقدة من القائمة المترابطة
} 

// تطبع هذه الدالة محتويات القائمة المترابطة بدءًا من العقدة المعطاة
void printList(struct Node *node) 
{ 
	while (node != NULL) 
	{ 
		printf(" %d ", node->data); 
		node = node->next; 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	// البدء بقائمة مترابطة فارغة
	struct Node* head = NULL; 

	push(&head, 7); 
	push(&head, 1); 
	push(&head, 3); 
	push(&head, 2); 
	push(&head, 8); 

	puts("Created Linked List: "); 
	printList(head); 
	deleteNode(&head, 4); 
	puts("\nLinked List after Deletion at position 4: "); 
	printList(head); 
	return 0; 
}
  • بايثون
# صنف العقدة
class Node: 

	# دالة بانية لتهيئة كائن العقدة
	def __init__(self, data): 
		self.data = data 
		self.next = None

class LinkedList: 

	# تهيئة رأس القائمة
	def __init__(self): 
		self.head = None

	# تدرج الدالة عقدة جديدة في مقدمة القائمة
	def push(self, new_data): 
		new_node = Node(new_data) 
		new_node.next = self.head 
		self.head = new_node 

	# تحذف الدالة التالية العقدة الموجودة في الموقع المعطى
	# وذلك باستخدام إشارة لرأس القائمة والموقع المعطى */

	def deleteNode(self, position): 

		# إن كانت القائمة المترابطة فارغة
		if self.head == None: 
			return

		# تخزين عقدة الرأس
		temp = self.head 

		# إن كان المطلوب حذف رأس القائمة
		if position == 0: 
			self.head = temp.next
			temp = None
			return

		# العثور على العقدة السابقة للعقدة المراد حذفها
		for i in range(position -1 ): 
			temp = temp.next
			if temp is None: 
				break

		# إن كان الموقع المعطى أكبر من عدد العناصر في القائمة
		if temp is None: 
			return
		if temp.next is None: 
			return

		# temp.next
		# هي العقدة المراد حذفها
		# يخزن المؤشر في العقدة التي تلي العقدة المراد حذفها
		next = temp.next.next

		# فك ارتباط العقدة بالقائمة المترابطة
		temp.next = None

		temp.next = next


	# Utility function to print the linked LinkedList 
	def printList(self): 
		temp = self.head 
		while(temp): 
			print " %d " %(temp.data), 
			temp = temp.next


# اختبار الدوال السابقة
llist = LinkedList() 
llist.push(7) 
llist.push(1) 
llist.push(3) 
llist.push(2) 
llist.push(8) 

print "Created Linked List: "
llist.printList() 
llist.deleteNode(4) 
print "\nLinked List after Deletion at position 4: "
llist.printList()
  • جافا:
class LinkedList 
{ 
	Node head; // رأس القائمة

	/* عقدة في القائمة المترابطة*/
	class Node 
	{ 
		int data; 
		Node next; 
		Node(int d) 
		{ 
			data = d; 
			next = null; 
		} 
	} 

	/* إدراج عقدة جديدة في مقدمة القائمة */
	public void push(int new_data) 
	{ 
		/* 1: حجز موقع للعقدة في الذاكرة
		2: إضافة البيانات */
		Node new_node = new Node(new_data); 

		/* 3: جعل ما يلي العقدة الجديدة هو رأس القائمة المترابطة */
		new_node.next = head; 

		/* 4: تحريك الرأس ليشير إلى العقدة الجديدة */
		head = new_node; 
	} 

	/* يحذف التابع العقدة في الموقع المعطى
	وذلك باستخدام إشارة (مؤشر إلى مؤشر) لرأس القائمة والموقع المعطى */
	void deleteNode(int position) 
	{ 
		// إن كانت القائمة المترابطة فارغة
		if (head == null) 
			return; 

		// تخزين عقدة رأس القائمة
		Node temp = head; 

		// إن كان المطلوب حذف رأس القائمة
		if (position == 0) 
		{ 
			head = temp.next; // تغيير رأس القائمة
			return; 
		} 

		// العثور على العقدة التي تسبق للعقدة المراد حذفها 
		for (int i=0; temp!=null && i<position-1; i++) 
			temp = temp.next; 

		// إن كان الموقع المطلوب أكبر من عدد العقد في القائمة المترابطة
		if (temp == null || temp.next == null) 
			return; 

		// temp->next
		// هي العقدة المراد حذفها
		// تخزين المؤشر إلى العقدة التي تلي العقدة المراد حذفها
		Node next = temp.next.next; 

		temp.next = next; // فك ارتباط العقدة من القائمة المترابطة
	} 

	// تطبع هذه الدالة محتويات القائمة المترابطة بدءًا من العقدة المعطاة 
	public void printList() 
	{ 
		Node tnode = head; 
		while (tnode != null) 
		{ 
			System.out.print(tnode.data+" "); 
			tnode = tnode.next; 
		} 
	} 

// اختبار التوابع السابقة
	public static void main(String[] args) 
	{ 
		/* البدء بقائمة فارغة */
		LinkedList llist = new LinkedList(); 

		llist.push(7); 
		llist.push(1); 
		llist.push(3); 
		llist.push(2); 
		llist.push(8); 

		System.out.println("\nCreated Linked list is: "); 
		llist.printList(); 

		llist.deleteNode(4); // حذف العقدة في الموقع 4 

		System.out.println("\nLinked List after Deletion at position 4: "); 
		llist.printList(); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

القائمة المترابطة المنشأة: 
 8  2  3  1  7 
القائمة المترابطة بعد حذف العنصر في الموقع 4: 
 8  2  3  1

البحث عن عنصر في القائمة المترابطة

يمكن البحث عن عنصر في القائمة المترابطة بطريقتين هما:

  1. الطريقة التكرارية iterative.
  2. الطريقة التعاودية recursive.

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

تتضمن الطريقة التكرارية الخطوات التالية:

  1. تهيئة مؤشرة العقدة، current = head
  2. إنجاز ما يلي ما دامت قيمة current ليست Null
    1. إن كانت current->key مساوية للمفتاح الذي المراد البحث عنه نعيد القيمة true.
    2. إسناد current->next إلى current
    3. إعادة القيمة false.

تعرض الأمثلة التالية كيفية تنفيذ الطريقة التكرارية في البحث عن عقدة معينة في القائمة المترابطة وفي عدد من لغات البرمجة:

#include <bits/stdc++.h> 
using namespace std; 

/* عقدة في القائمة المترابطة */
class Node 
{ 
	public: 
	int key; 
	Node* next; 
}; 

/* تضيف هذه الدالة عقدة جديدة في مقدمة القائمة المترابطة
باستخدام إشارة (مؤشر إلى مؤشر) إلى رأس القائمة والعدد الصحيح المعطى */

void push(Node** head_ref, int new_key) 
{ 
	/* حجز موقع للعقدة في الذاكرة */
	Node* new_node = new Node(); 

	/* إضافة المفتاح */
	new_node->key = new_key; 

	/* فك ارتباط القائمة القديمة عن العقدة الجديدة */
	new_node->next = (*head_ref); 

	/* تحريك رأس القائمة ليشير إلى العقدة الجديدة */
	(*head_ref) = new_node; 
} 

/* التحقق من أن القيمة المعطاة موجودة في القائمة المترابطة */
bool search(Node* head, int x) 
{ 
	Node* current = head; // تهيئة العقدة الحالية
	while (current != NULL) 
	{ 
		if (current->key == x) 
			return true; 
		current = current->next; 
	} 
	return false; 
} 

/* اختبار الدوال السابقة*/
int main() 
{ 
	/* البدء بقائمة مترابطة فارغة */
	Node* head = NULL; 
	int x = 21; 

	/* push() استخدام الدالة 
	لإنشاء القائمة المترابطة التالية: 
	14->21->11->30->10 */
	push(&head, 10); 
	push(&head, 30); 
	push(&head, 11); 
	push(&head, 21); 
	push(&head, 14); 

	search(head, 21)? cout<<"Yes" : cout<<"No"; 
	return 0; 
}
  • بايثون:
# صنف العقدة
class Node: 
	
	# تهيئة كائن العقدة
	def __init__(self, data): 
		self.data = data # Assign data 
		self.next = None # Initialize next as null 

# صنف القائمة المترابطة
class LinkedList: 
	def __init__(self): 
		self.head = None # تهيئة رأس القائمة

	# يدرج هذا التابع عقدة جديدة في بداية القائمة المترابطة
	def push(self, new_data): 
	
		# إنشاء عقدة جديدة 
		new_node = Node(new_data) 

		# جعل رأس القائمة يلي العقدة الجديدة  
		new_node.next = self.head 

		# تحريك الرأس ليشير إلى العقدة الجديدة
		self.head = new_node 

	# تتحقق هذه الدالة من وجود القيمة المعطاة في القائمة المترابطة
	def search(self, x): 

		# تهيئة رأس القائمة الحالي
		current = self.head 

		# تنفيذ حلقة تكرارية إلى أن تصبح قيمة
		# None العقدة الحالية هي
		while current != None: 
			if current.data == x: 
				return True # data found 
			
			current = current.next
		
		return False # لم يُعثر على البيانات المطلوبة 


# اختبار التوابع السابقة
if __name__ == '__main__': 

	# البدء بقائمة مترابطة فارغة
	llist = LinkedList() 

	''' نستخدم التابع
	push()
	لإنشاء القائمة المترابطة التالية: 
		14->21->11->30->10 '''
	llist.push(10); 
	llist.push(30); 
	llist.push(11); 
	llist.push(21); 
	llist.push(14); 

	if llist.search(21): 
		print("Yes") 
	else: 
		print("No")
  • جافا:
//صنف العقدة 
class Node 
{ 
	int data; 
	Node next; 
	Node(int d) 
	{ 
		data = d; 
		next = null; 
	} 
} 

//صنف القائمة المترابطة
class LinkedList 
{ 
	Node head; //رأس القائمة

	//إدراج عقدة في بداية القائمة
	public void push(int new_data) 
	{ 
		//حجز موقع للعقدة الجديدة في الذاكرة وإضافة البيانات
		Node new_node = new Node(new_data); 

		//جعل رأس القائمة يتلو العقدة التالية
		new_node.next = head; 

		//تحريك رأس القائمة ليشير إلى العقدة الجديدة
		head = new_node; 
	} 

	//التحقق من كون القيمة المعطاة موجودة في القائمة المترابطة 
	public boolean search(Node head, int x) 
	{ 
		Node current = head; //تهيئة الرأس الحالي 
		while (current != null) 
		{ 
			if (current.data == x) 
				return true; //عُثر على البيانات المطلوبة 
			current = current.next; 
		} 
		return false; //لم يُعثر على البيانات المطلوبة 
	} 

	//اختبار الدوال السابقة
	public static void main(String args[]) 
	{ 

		//البدء بقائمة مترابطة فارغة
		LinkedList llist = new LinkedList(); 

		/*استخدام التابع
		push()
		لإنشاء القائمة المترابطة التالية
		14->21->11->30->10 */
		llist.push(10); 
		llist.push(30); 
		llist.push(11); 
		llist.push(21); 
		llist.push(14); 

		if (llist.search(llist.head, 21)) 
			System.out.println("Yes"); 
		else
			System.out.println("No"); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Yes

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

تعمل الدالة search(head, x)‎ بطريقة تعاودية وحسب الخطوات التالية:

  1. إن كانت قيمة الرأس تساوي Null تعيد الدالة القيمة false.
  2. إن كان المفتاح الخاص بالرأس هو x نفسه، تعيد الدالة القيمة true.
  3. فيما عدا ذلك تعيد الدالة ناتج استدعاء الدالة search(head->next, x)‎.

تعرض الأمثلة التالية كيفية تنفيذ عملية البحث بالطريقة التعاودية وفي عدد من لغات البرمجة:

  • C:
#include<stdio.h> 
#include<stdlib.h> 
#include<stdbool.h> 
/* عقدة في القائمة المترابطة */
struct Node 
{ 
	int key; 
	struct Node* next; 
}; 

/* تدرج الدالة عقدة جديدة في مقدمة القائمة المترابطة
باستخدام إشارة (مؤشر إلى مؤشر) إلى رأس القائمة والعدد الصحيح المعطى
*/

void push(struct Node** head_ref, int new_key) 
{ 
	/* حجز موقع العقدة في الذاكرة */
	struct Node* new_node = 
			(struct Node*) malloc(sizeof(struct Node)); 

	/* إضافة المفتاح */
	new_node->key = new_key; 

	/* فك الترابط بين القائمة المترابطة والعقدة الجديدة */
	new_node->next = (*head_ref); 

	/* تحريك رأس القائمة ليشير إلى العقدة الجديدة*/
	(*head_ref) = new_node; 
} 

/* التحقق من كون القيمة المعطاة موجودة في القائمة المترابطة */
bool search(struct Node* head, int x) 
{ 
	// الشرط الأساسي 
	if (head == NULL) 
		return false; 
	
	// نعيد قيمة صحيحة إن كان المفتاح المطلوب موجودًا في القائمة
	if (head->key == x) 
		return true; 

	// تنفذ الدالة تعاوديًا للبحث عن المفتاح المطلوب
	return search(head->next, x); 
} 

/* اختبار الدوال السابقة*/
int main() 
{ 
	/* البدء بقائمة فارغة */
	struct Node* head = NULL; 
	int x = 21; 

	/* تستخدم الدالة
	push()
	لإنشاء القائمة المترابطة التالية 
	14->21->11->30->10 */
	push(&head, 10); 
	push(&head, 30); 
	push(&head, 11); 
	push(&head, 21); 
	push(&head, 14); 

	search(head, 21)? printf("Yes") : printf("No"); 
	return 0; 
}
  • بايثون:
# صنف العقدة
class Node: 
	
	# تهيئة كائن العقدة
	def __init__(self, data): 
		self.data = data # Assign data 
		self.next = None # Initialize next as null 

# صنف القائمة المترابطة
class LinkedList: 
	def __init__(self): 
		self.head = None # تهيئة رأس القائمة

	# يدرج هذا التابع عقدة جديدة في بداية القائمة المترابطة
	def push(self, new_data): 
	
		# إنشاء عقدة جديدة 
		new_node = Node(new_data) 

		# جعل رأس القائمة يلي العقدة الجديدة  
		new_node.next = self.head 

		# تحريك الرأس ليشير إلى العقدة الجديدة
		self.head = new_node 

	# تتحقق هذه الدالة من وجود القيمة المعطاة في القائمة المترابطة
	def search(self, li, key): 
		
		# الشرط الأساسي
		if(not li): 
			return False

		# نعيد قيمة صحيحة
		# إن كان المفتاح موجودًا في العقدة الحالية
		if(li.data == key): 
			return True

		# تنفذ الدالة تعاوديًا على بقية العقد في القائمة المترابطة
		return self.search(li.next, key) 


# اختبار التوابع السابقة
if __name__ == '__main__': 

	# البدء بقائمة مترابطة فارغة
	llist = LinkedList() 

	''' نستخدم التابع
	push()
	لإنشاء القائمة المترابطة التالية: 
		14->21->11->30->10 '''
	llist.push(10); 
	llist.push(30); 
	llist.push(11); 
	llist.push(21); 
	llist.push(14); 

	if llist.search(21): 
		print("Yes") 
	else: 
		print("No")
  • جافا:
//صنف العقدة 
class Node 
{ 
	int data; 
	Node next; 
	Node(int d) 
	{ 
		data = d; 
		next = null; 
	} 
} 

//صنف القائمة المترابطة
class LinkedList 
{ 
	Node head; //رأس القائمة

	//إدراج عقدة في بداية القائمة
	public void push(int new_data) 
	{ 
		//حجز موقع للعقدة الجديدة في الذاكرة وإضافة البيانات
		Node new_node = new Node(new_data); 

		//جعل رأس القائمة يتلو العقدة التالية
		new_node.next = head; 

		//تحريك رأس القائمة ليشير إلى العقدة الجديدة
		head = new_node; 
	} 

	//التحقق من كون القيمة المعطاة موجودة في القائمة المترابطة 
	public boolean search(Node head, int x) 
    { 
        // الشرط الأساسي 
        if (head == null) 
            return false; 
  
        // نعيد قيمة صحيحة
        // إن كان المفتاح موجودًا في العقدة الحالية
        if (head.data == x) 
            return true; 
  
        // تنفذ الدالة تعاودية على بقية العقد في القائمة المترابطة
        return search(head.next, x); 
    }  

	//اختبار الدوال السابقة
	public static void main(String args[]) 
	{ 

		//البدء بقائمة مترابطة فارغة
		LinkedList llist = new LinkedList(); 

		/*استخدام التابع
		push()
		لإنشاء القائمة المترابطة التالية
		14->21->11->30->10 */
		llist.push(10); 
		llist.push(30); 
		llist.push(11); 
		llist.push(21); 
		llist.push(14); 

		if (llist.search(llist.head, 21)) 
			System.out.println("Yes"); 
		else
			System.out.println("No"); 
	} 
}

مصادر

مجلوبة من "https://wiki.hsoub.com/index.php?title=Algorithms/linked_lists&oldid=28596"