أ قائمة مرتبطة هو نوع من بنية البيانات الديناميكية الخطية التي نستخدمها لتخزين عناصر البيانات. المصفوفات هي أيضًا نوع من بنية البيانات الخطية حيث يتم تخزين عناصر البيانات في كتل ذاكرة مستمرة.
على عكس المصفوفات، لا تحتاج القائمة المرتبطة إلى تخزين عناصر البيانات في مناطق أو كتل ذاكرة متجاورة.
أ قائمة مرتبطة يتكون من عناصر تعرف باسم 'العقد' والتي تنقسم إلى قسمين. المكون الأول هو الجزء الذي نقوم فيه بتخزين البيانات الفعلية، والثاني هو الجزء الذي نقوم فيه بتخزين المؤشر إلى العقدة التالية. يُعرف هذا النوع من البنية باسم ' قائمة مرتبطة منفردة .'
القائمة المرتبطة في C++
سيتناول هذا البرنامج التعليمي القائمة المرتبطة بشكل فردي بعمق.
يتم توضيح هيكل القائمة المرتبطة بشكل فردي في الرسم البياني أدناه
- كما رأينا في الجزء أعلاه، تُعرف العقدة الأولى من القائمة المرتبطة باسم 'الرأس'، بينما تسمى العقدة الأخيرة 'الذيل'. نظرًا لعدم تحديد عنوان ذاكرة في العقدة الأخيرة، سيكون للعقدة النهائية للقائمة المرتبطة مؤشر تالٍ فارغ.
- نظرًا لأن كل عقدة تتضمن مؤشرًا إلى العقدة التالية، فلا يلزم الاحتفاظ بعناصر البيانات الموجودة في القائمة المرتبطة في مواقع متجاورة. قد تكون العقد متفرقة في جميع أنحاء الذاكرة. نظرًا لأن كل عقدة لها عنوان العقدة التي تليها، فيمكننا الوصول إلى العقد وقتما نريد.
- يمكننا إضافة عناصر البيانات وإزالتها بسرعة من القائمة المتصلة. ونتيجة لذلك، يمكن أن تزيد القائمة المرتبطة أو تتقلص ديناميكيًا. لا تحتوي القائمة المرتبطة على الحد الأقصى لعدد عناصر البيانات التي يمكن أن تحتوي عليها. ونتيجة لذلك، يمكننا إضافة أي عدد نريده من عناصر البيانات إلى القائمة المرتبطة طالما أن ذاكرة الوصول العشوائي متوفرة.
- نظرًا لأننا لا نحتاج إلى تحديد عدد العناصر التي نحتاجها في القائمة المرتبطة مسبقًا، فإن القائمة المرتبطة توفر مساحة في الذاكرة بالإضافة إلى سهولة إدراجها وحذفها. المساحة الوحيدة التي تستخدمها القائمة المرتبطة هي تخزين المؤشر إلى العقدة التالية، مما يضيف بعض التكلفة.
بعد ذلك، سنتناول العمليات المختلفة التي يمكن إجراؤها على القائمة المرتبطة.
1) الإدراج
يتم توسيع القائمة المرتبطة من خلال إجراء الإضافة إليها. على الرغم من أن الأمر قد يبدو بسيطًا، نظرًا لبنية القائمة المرتبطة، فإننا نعلم أنه في كل مرة تتم فيها إضافة عنصر بيانات، يجب علينا تغيير المؤشرات التالية للعقد السابقة والتالية للعنصر الجديد الذي أضفناه.
المكان الذي سيتم فيه إدراج عنصر البيانات الجديد هو الجانب الثاني الذي يجب التفكير فيه.
تم فرز قائمة صفيف جافا
توجد ثلاثة أماكن حيث يمكن إضافة عنصر بيانات إلى القائمة المرتبطة.
أ. البدء بالقائمة المرتبطة
فيما يلي قائمة متصلة بالأرقام 2->4->6->8->10. سيشير الرأس الذي يشير إلى العقدة 2 الآن إلى العقدة 1، وسيكون للمؤشر التالي للعقدة 1 عنوان ذاكرة العقدة 2، كما هو موضح في الرسم التوضيحي أدناه، إذا أضفنا عقدة جديدة 1 كأول عقدة في القائمة .
ونتيجة لذلك، فإن القائمة المرتبطة الجديدة هي 1->2->4->6->8->10.
ب. بعد العقدة المحددة
في هذه الحالة، حصلنا على عقدة ويجب علينا إضافة عقدة جديدة خلفها. ستظهر القائمة المرتبطة كما يلي إذا تمت إضافة العقدة f إلى القائمة المرتبطة a->b->c->d->e بعد العقدة c:
ولذلك فإننا نتحقق لمعرفة ما إذا كانت العقدة المحددة موجودة في الرسم البياني أعلاه. إذا كانت موجودة، فسيتم إنشاء عقدة جديدة f. بعد ذلك، نوجه المؤشر التالي للعقدة c إلى العقدة الجديدة تمامًا f. يشير المؤشر التالي للعقدة f الآن إلى العقدة d.
ج. العنصر الأخير في القائمة المرتبطة
وفي الحالة الثالثة، تتم إضافة عقدة جديدة إلى نهاية القائمة المرتبطة. خذ بعين الاعتبار القائمة المرتبطة أدناه: a->b->c->d->e، مع إضافة العقدة f في النهاية. بعد إضافة العقدة، ستظهر القائمة المرتبطة بهذا الشكل.
ونتيجة لذلك، نقوم ببناء عقدة جديدة f. يشير مؤشر الذيل المؤدي إلى القيمة الخالية إلى f، ويشير المؤشر التالي للعقدة f إلى قيمة خالية. في لغة البرمجة أدناه، قمنا بإنشاء جميع الأنواع الثلاثة من وظائف الإدراج.
يمكن الإعلان عن القائمة المرتبطة كهيكل أو كفئة في C++. القائمة المرتبطة التي تم تعريفها كهيكل هي عبارة عن بيان نمط C كلاسيكي. يتم استخدام القائمة المرتبطة كفئة في لغة C++ الحديثة، خاصة عند استخدام مكتبة القوالب القياسية.
تم استخدام البنية في التطبيق التالي للإعلان عن قائمة مرتبطة وإنشائها. سيكون أعضاؤها عبارة عن بيانات ومؤشر للعنصر التالي.
برنامج سي++:
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) الحذف
كما هو الحال مع الإدراج، يتطلب حذف عقدة من القائمة المرتبطة العديد من النقاط التي قد يتم حذف العقدة منها. يمكننا إزالة العقدة الأولى أو الأخيرة أو العقدة k من القائمة المرتبطة بشكل عشوائي. يجب علينا تحديث المؤشر التالي وجميع مؤشرات القائمة المرتبطة الأخرى بشكل صحيح من أجل الحفاظ على القائمة المرتبطة بعد الحذف.
في تطبيق C++ التالي، لدينا طريقتان للحذف: حذف العقدة الأولية للقائمة وحذف العقدة الأخيرة للقائمة. نبدأ بإضافة العقد إلى رأس القائمة. ويتم عرض محتويات القائمة بعد كل إضافة وحذف.
برنامج سي++:
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> عدد العقد
أثناء اجتياز القائمة المرتبطة، يمكن إجراء عملية حساب عدد العقد. في الطريقة السابقة، رأينا أنه إذا كنا بحاجة إلى إدراج/حذف عقدة أو عرض محتويات القائمة المرتبطة، فيجب علينا اجتياز القائمة المرتبطة من البداية.
إن تعيين عداد وزيادة وكذلك اجتياز كل عقدة سيوفر لنا عدد العقد في القائمة المرتبطة.
الاختلافات بين المصفوفة والقائمة المرتبطة:
| مجموعة مصفوفة | قائمة مرتبطة |
|---|---|
| المصفوفات لها حجم محدد. | حجم القائمة المرتبطة متغير. |
| إدخال عنصر جديد أمر صعب. | الإدراج والحذف أسهل. |
| يسمح بالوصول عشوائيا. | لا يوجد وصول عشوائي ممكن. |
| العناصر قريبة أو متجاورة نسبيًا. | العناصر ليست متجاورة. |
| ليست هناك حاجة إلى مساحة إضافية للمؤشر التالي. | يتطلب المؤشر التالي ذاكرة إضافية. |
وظائف
نظرًا لأن القوائم والمصفوفات المرتبطة عبارة عن هياكل بيانات خطية تحتوي على كائنات، فيمكن استخدامها بطرق مماثلة لغالبية التطبيقات.
فيما يلي بعض الأمثلة لتطبيقات القائمة المرتبطة:
- يمكن تنفيذ الأكوام وقوائم الانتظار باستخدام القوائم المرتبطة.
- عندما نحتاج إلى التعبير عن الرسوم البيانية كقوائم مجاورة، يمكننا استخدام قائمة مرتبطة لتنفيذها.
- يمكننا أيضًا استخدام قائمة مرتبطة لاحتواء كثيرات الحدود الرياضية.
- في حالة التجزئة، يتم استخدام القوائم المرتبطة لتنفيذ المجموعات.
- عندما يتطلب أحد البرامج تخصيص ذاكرة ديناميكية، يمكننا استخدام قائمة مرتبطة لأن القوائم المرتبطة تكون أكثر كفاءة في هذه الحالة.
خاتمة
القوائم المرتبطة هي هياكل بيانات تستخدم للاحتفاظ بعناصر البيانات في نموذج خطي ولكن غير متجاور. تتكون القائمة المرتبطة من عقد تحتوي كل منها على مكونين. يتكون المكون الأول من البيانات، بينما يحتوي النصف الثاني على مؤشر يخزن عنوان الذاكرة للعضو التالي في القائمة.
كعلامة على انتهاء القائمة المرتبطة، يتم تعيين المؤشر التالي للعنصر الأخير في القائمة على NULL. الرأس هو العنصر الأول في القائمة. تسمح القائمة المرتبطة بمجموعة متنوعة من الإجراءات مثل الإدراج والحذف والاجتياز وما إلى ذلك. يتم تفضيل القوائم المرتبطة على المصفوفات لتخصيص الذاكرة الديناميكية.
من الصعب طباعة القوائم المرتبطة أو اجتيازها لأننا لا نستطيع الوصول إلى العناصر بشكل عشوائي مثل المصفوفات. عند مقارنتها بالمصفوفات، تكون إجراءات الإدراج والحذف أقل تكلفة.
في هذا البرنامج التعليمي، تعلمنا كل ما يمكن معرفته حول القوائم المرتبطة الخطية. يمكن أيضًا أن تكون القوائم المرتبطة مرتبطة بشكل مزدوج أو دائرية. وفي دروسنا القادمة، سنتناول هذه القوائم بالتفصيل.