• يمكن تعريف القائمة المرتبطة على أنها مجموعة من الكائنات تسمى العقد التي يتم تخزينها بشكل عشوائي في الذاكرة.
• تحتوي العقدة على حقلين، أي البيانات المخزنة في هذا العنوان المحدد والمؤشر الذي يحتوي على عنوان العقدة التالية في الذاكرة.
• تحتوي العقدة الأخيرة من القائمة على مؤشر إلى القيمة الخالية.

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

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

لماذا استخدام القائمة المرتبطة على المصفوفة؟

حتى الآن، كنا نستخدم بنية بيانات المصفوفة لتنظيم مجموعة العناصر التي سيتم تخزينها بشكل فردي في الذاكرة. ومع ذلك، فإن للمصفوفة العديد من المزايا والعيوب التي يجب معرفتها من أجل تحديد بنية البيانات التي سيتم استخدامها في جميع أنحاء البرنامج.

يحتوي المصفوفة على القيود التالية:

1. يجب معرفة حجم المصفوفة مسبقاً قبل استخدامها في البرنامج.
2. إن زيادة حجم المصفوفة هي عملية تستغرق وقتًا طويلاً. يكاد يكون من المستحيل توسيع حجم المصفوفة في وقت التشغيل.
3. يجب تخزين جميع العناصر الموجودة في المصفوفة بشكل متجاور في الذاكرة. إن إدراج أي عنصر في المصفوفة يحتاج إلى تغيير جميع العناصر السابقة له.

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

الدليل في أوامر لينكس

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

قائمة مرتبطة منفردة أو سلسلة ذات اتجاه واحد

يمكن تعريف القائمة المرتبطة بشكل فردي على أنها مجموعة من العناصر المرتبة. قد يختلف عدد العناصر حسب حاجة البرنامج. تتكون العقدة في القائمة المرتبطة بشكل فردي من جزأين: جزء البيانات وجزء الارتباط. يقوم جزء البيانات من العقدة بتخزين المعلومات الفعلية التي سيتم تمثيلها بواسطة العقدة بينما يقوم جزء الارتباط من العقدة بتخزين عنوان خليفتها المباشرة.

شيء لصديقي

يمكن اجتياز سلسلة ذات اتجاه واحد أو قائمة مرتبطة بشكل فردي في اتجاه واحد فقط. بمعنى آخر، يمكننا القول أن كل عقدة تحتوي على المؤشر التالي فقط، وبالتالي لا يمكننا اجتياز القائمة في الاتجاه المعاكس.

لنأخذ مثالاً حيث يتم تخزين العلامات التي حصل عليها الطالب في ثلاث مواد في قائمة مرتبطة كما هو موضح في الشكل.

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

تعقيد

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

هناك العديد من العمليات التي يمكن تنفيذها على قائمة مرتبطة بشكل فردي. وترد أدناه قائمة بجميع هذه العمليات.

نقل وسائل الإعلام

إنشاء العقدة

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

إدراج

يمكن إجراء الإدراج في قائمة مرتبطة منفردة في مواضع مختلفة. بناءً على موضع العقدة الجديدة التي يتم إدراجها، يتم تصنيف عملية الإدراج إلى الفئات التالية.

الحذف والعبور

يمكن إجراء حذف عقدة من قائمة مرتبطة منفردة في مواضع مختلفة. بناءً على موضع العقدة التي يتم حذفها، يتم تصنيف العملية إلى الفئات التالية.

القائمة المرتبطة في C: برنامج يحركه القائمة

 #include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('

*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
 5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
 Enter the location of the node after which you want to perform deletion 
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } 

انتاج:

 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9