القوائم Data Structures and Algorithms – Linked List

-

linked list هي سلسلة من هياكل البيانات  sequence of data structures وتتضمن سلسلة من العقد المتصلة connected nodes، تخزن كل عقدة nodes البيانات وعنوان العقدة التالية التي ترتبط بها. 

تعتبر Linked list ثاني أكثر data structure استخدامًا بعد المصفوفات array. 

وفقًا للصورة أعلاه ، فيما يلي النقاط المهمة التي يجب مراعاتها.

• تحتوي القائمة المرتبطة على link element يسمى first وهو العقدة الأولى والتي عادتا يعطى العنوان اسمًا خاصًا يسمى HEAD .
• يحتوي كل ارتباط link على حقل او حقول field بيانات و link field يسمى التالي next.
• كل رابط مرتبط بالرابط التالي باستخدام الرابط التالي.
• الارتباط الأخير يحمل ارتباطًا فارغًا null  لوضع علامة على نهاية القائمة.

يمكن أن تكون القوائم المرتبطة من أنواع متعددة:

•  مفردة او البسيطة singly Simple or: في هذا النوع تنقل العناصر إلى الأمام فقط forward only. 
•  مزدوجة doubly : يمكن التنقل بين العناصر للأمام forward وللخلف backward.
•  دائرية circular : يحتوي العنصر الأخير على ارتباط link  للعنصر الأول كعنصر تالي والعنصر الأول له ارتباط بالعنصر الأخير على النحو السابق.

في هذه المقالة، بنحكي عن القائمة المرتبطة المفردة.  بقية الأنواع سيتم مناقشتها في الدرس التالي:

تمثيل القائمة المرتبطة Representation of Linked List

تتكون كل عقدة من:

• عنصر بيانات data item
• عنوان عقدة أخرى address of another node

يتم تمثيل ذلك على النحو التالي:

struct node
{
  int data;
  struct node *next;
}

تحتوي كل عقدة هيكلية struct node  على عنصر بيانات data item  ومؤشر pointer  إلى عقدة هيكلية  struct node أخرى.

في المثال التالي ننشئ قائمة مرتبطة Linked List بسيطة بثلاثة عناصر لفهم كيفية عمل ذلك.

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;
/* Save address of first node in head */
head = one;

للمزيد حول الكود السابق يمكن الانتقال الى الدرس  C structs and Pointers

قوة القائمة المرتبطة linked list في القدرة على كسر السلسلة بحيث يمكن الإضافة لها وإعادة الترتيب. 

القوائم  Lists هي واحدة من هياكل البيانات data structures الأكثر شيوعًا وفعالية وتستخدم في اللغات البرمجة مثل:

C, C ++, Python, Java, C #

بصرف النظر عن ذلك ، تعد القوائم المرتبطة linked list  طريقة رائعة لمعرفة كيفية عمل المؤشرات pointers . من خلال التدرب على كيفية التعامل مع القوائم المرتبطة، يمكنك أن تعد نفسك لتعلم المزيد من هياكل البيانات المتقدمة مثل الرسوم البيانية graphs   والأشجار trees.

مثال (لغة C):

// Linked list implementation in C
#include <stdio.h>
#include <stdlib.h>
// Creating a node
struct node {
  int value;
  struct node *next;
};
// print the linked list value
void printLinkedlist(struct node *p) {
  while (p != NULL) {
    printf("%d ", p->value);
    p = p->next;
  }
}
int main() {
  // Initialize nodes
  struct node *head;
  struct node *one = NULL;
  struct node *two = NULL;
  struct node *three = NULL;
  // Allocate memory
  one = malloc(sizeof(struct node));
  two = malloc(sizeof(struct node));
  three = malloc(sizeof(struct node));
  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;
  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;
  // printing node-value
  head = one;
  printLinkedlist(head);
}

النتيجة 

العمليات الأساسية Basic Operations

تدعم القائم مجموعة من العمليات هذه العمليات هي:

• الإضافة Insertion: يضيف عنصرًا في بداية القائمة.
• الحذف Deletion: يحذف عنصرًا في بداية القائمة.
• العرض Display: يعرض القائمة الكاملة.
• بحث Search: يبحث عن عنصر باستخدام مفتاح معين key.
• حذف Delete: يحذف عنصرًا باستخدام مفتاح محدد key.

فيما يلي توضيح لهذه العمليات.

الإضافة Insertion

يمكن إضافة عنصر الى القائمة بشرط ان يكون من نفس البنية same structure ثم يجب تحديد الموقع المطلوب إدراجه فيه.

الصورة التالية تحتوي على قائمة تحتوي على 2 node وهما ) A,B). المطلوب إضافة عنصر جديد بين (A,B).

خطوات الإضافة 

 انشاء عنصر جديد باسم C من نفس النوع. 

تغير الرابط من العقدة الأولى وهي A وتحويلها الى العقدة الجديدة C بدل من B.

الكود :

LeftNode.next −> NewNode;

ربط العقدة C مع العقدة الأخيرة B

بهذه الطريقة سيتم وضع العقدة الجديدة في منتصف العقدتين (A,B). وبناء عليه ستبدو القائمة الجديدة هكذا:

عملية الحذف Deletion Operation

في عملية الحذف يتم تحديد العقدة المطلوب حذفها بالبحث عنها (استخدام خوارزمية البحث) ثم إجراء عملية الحذف. 

نطبق الحذف على المثال السابق 

لنفرض لدينا قائمة تحتوي على 3 عقد هي (A,B,C).

لحذف العقدة B من الوسط تتم على مرحلتين:

• مرحلة 1 حذف الرابط link  بين العقد: البحث عن العقدة المطلوب حذفها.

تغير الرابط Link اليسار للعقدة المطلوب حذفها بحيث يتم تعديلها للإشارة الى العقدة التالية (العقدة بعد العقدة المطلوب حذفها) 

الكود :

LeftNode.next −> TargetNode.next;

• مرحلة 2 حذف العقدة نفسها.

نستخدم الكود التالي لحذف العقدة

TargetNode.next −> NULL;

ملاحظة : عند الحذف يمكن الاحتفاظ بالعقدة في الذاكرة لاستخدامها لاحقا. كما يمكن إلغاء العقدة بشكل نهائي وذلك عن طريق تخصيص الذاكرة ومسح العقدة المستهدفة تمامًا.

النتيجة :