شرح هياكل البيانات بأمثلة - قائمة مرتبطة

تمامًا مثل إكليل الزهور ، تتكون القائمة المرتبطة من العقد. نسمي كل زهرة في هذا الطوق المعين لتكون عقدة. وكل عقدة تشير إلى العقدة التالية في هذه القائمة بالإضافة إلى أنها تحتوي على بيانات (هنا نوع الزهرة).

أنواع

قائمة مرتبطة بشكل فردي

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

 head | | +-----+--+ +-----+--+ +-----+------+ | 1 |o-----> | 2 |o-----> | 3 | NULL | +-----+--+ +-----+--+ +-----+------+

التنفيذ الداخلي لـ CPython ، يتم الاحتفاظ بالإطارات والمتغيرات المقيمة في مكدس.

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

قائمة مرتبطة بشكل مضاعف

تحتوي القوائم المرتبطة بشكل مضاعف على عقدة تحتوي على dataحقل وحقل nextوحقل ارتباط آخر prevيشير إلى العقدة السابقة في التسلسل.

 head | | +------+-----+--+ +--+-----+--+ +-----+------+ | | |o------> | |o------> | | | | NULL | 1 | | 2 | | 3 | NULL | | | | <------o| | <------o| | | +------+-----+--+ +--+-----+--+ +-----+------+

ذاكرة التخزين المؤقت للمتصفح التي تسمح لك بالضغط على زر BACK و FORWARD. نحتاج هنا إلى الاحتفاظ بقائمة مرتبطة بشكل مزدوج ، مع URLsحقل بيانات ، للسماح بالوصول في كلا الاتجاهين. للانتقال إلى عنوان URL السابق ، سنستخدم prevالحقل وللانتقال إلى الصفحة التالية سنستخدم nextالحقل.

قائمة مرتبطة دائرية

القوائم المرتبطة الدائرية هي قائمة مرتبطة بشكل فردي حيث nextيشير الحقل الأخير إلى العقدة الأولى في التسلسل.

 head | | +-----+--+ +-----+--+ +-----+--+ —> | 1 |o-----> | 2 |o-----> | 3 |o----| +-----+--+ +-----+--+ +-----+--+

تم حل مشكلة مشاركة الوقت بواسطة نظام التشغيل.

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

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

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

إدراج

لإضافة عنصر جديد إلى القائمة.

الإدخال في البداية:

  • قم بإنشاء عقدة جديدة ببيانات معينة.
  • أشر العقدة الجديدة nextإلى القديمة head.
  • أشر headإلى هذه العقدة الجديدة.

الإدراج في المنتصف / النهاية.

الإدراج بعد العقدة X.

  • قم بإنشاء عقدة جديدة ببيانات معينة.
  • أشر العقدة الجديدة nextإلى X القديم next.
  • النقطة X nextإلى هذه العقدة الجديدة.

تعقيد الوقت: O (1)

حذف

لحذف عنصر موجود من القائمة.

الحذف في البداية

  • احصل على العقدة المشار إليها headبـ Temp.
  • أشر headإلى درجة الحرارة next.
  • الذاكرة الخالية المستخدمة بواسطة عقدة Temp.

الحذف في المنتصف / النهاية.

الحذف بعد العقدة X.

  • احصل على العقدة المشار إليها Xبـ Temp.
  • النقطة X nextإلى Temp's next.
  • الذاكرة الخالية المستخدمة بواسطة عقدة Temp.

تعقيد الوقت: O (1)

عبور

للسفر عبر القائمة.

اجتياز

  • احصل على العقدة التي يشير إليها headالتيار.
  • تحقق مما إذا كان التيار ليس فارغًا وقم بعرضه.
  • أشر الحالي إلى Current's nextوانتقل إلى الخطوة أعلاه.

تعقيد الوقت: O (n) // هنا n هو حجم قائمة الارتباط

التنفيذ

C ++ تنفيذ قائمة مرتبطة منفردة

// Header files #include  struct node { int data; struct node *next; }; // Head pointer always points to first element of the linked list struct node *head = NULL;

طباعة البيانات في كل عقدة

// Display the list void printList() { struct node *ptr = head; // Start from the beginning while(ptr != NULL) { std::cout 

Insertion at the beginning

// Insert link at the beginning void insertFirst(int data) { // Create a new node struct node *new_node = new struct node; new_node->data = data; // Point it to old head new_node->next = head; // Point head to new node head = new_node; std::cout << "Inserted successfully" << std::endl; }

Deletion at the beginning

// Delete first item void deleteFirst() { // Save reference to head struct node *temp = head; // Point head to head's next head = head->next; // Free memory used by temp temp = NULL: delete temp; std::cout << "Deleted successfully" << std::endl; }

Size

// Find no. of nodes in link list void size() { int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) { length++; } std::cout << "Size of Linked List is " << length << std::endl; }

Searching

// Find node with given data void find(int data){ // Start from the head struct node* current = head; // If list is empty if(head == NULL) { std::cout << "List is empty" next == NULL){ std::cout << "Not Found" 
      

Deletion after a node

// Delete a node with given data void del(int data){ // Start from the first node struct node* current = head; struct node* previous = NULL; // If list is empty if(head == NULL){ std::cout << "List is empty" next == NULL){ std::cout << "Element not found" 
       
        next; } else { // Skip the current node previous->next = current->next; } // Free space used by deleted node current = NULL; delete current; std::cout << "Deleted succesfully" << std::endl; }
       

Python Implementation of Singly Linked List

class Node(object): # Constructor def __init__(self, data=None, next=None): self.data = data self.next = next # Function to get data def get_data(self): return self.data # Function to get next node def get_next(self): return self.next # Function to set next field def set_next(self, new_next): self.next = new_next class LinkedList(object): def __init__(self, head=None): self.head = head

Insertion

 # Function to insert data def insert(self, data): # new_node is a object of class Node new_node = Node(data) new_node.set_next(self.head) self.head = new_node print("Node with data " + str(data) + " is created succesfully")

Size

 # Function to get size def size(self): current = self.head count = 0 while current: count += 1 current = current.get_next() print("Size of link list is " + str(count))

Searching

 # Function to search a data def search(self, data): current = self.head found = False while current and found is False: if current.get_data() == data: found = True else: current = current.get_next() if current is None: print("Node with data " + str(data) + " is not present") else: print("Node with data " + str(data) + " is found")

Deletion after a node

 # Function to delete a node with data def delete(self, data): current = self.head previous = None found = False while current and found is False: if current.get_data() == data: found = True else: previous = current current = current.get_next() if current is None: print("Node with data " + str(data) + " is not in list") elif previous is None: self.head = current.get_next() print("Node with data " + str(data) + " is deleted successfully") else: previous.set_next(current.get_next()) print("Node with data " + str(data) + " is deleted successfully")

Advantages

  1. Linked lists are a dynamic data structure, which can grow and shrink, allocating and deallocating memory while the program is running.
  2. Insertion and deletion of node are easily implemented in a linked list at any position.

Disadvantages

  1. They use more memory than arrays because of the memory used by their pointers (next and prev).
  2. Random access is not possible in linked list. We have to access nodes sequentially.
  3. It’s more complex than array. If a language supports array bound check automatically, Arrays would serve you better.

Note

We have to use free() in C and delete in C++ to free the space used by deleted node, whereas, in Python and Java free space is collected automatically by garbage collector.