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


مستوى الصعوبة سهل
كثيرا ما يطلب في جنرال إلكتريك للرعاية الصحية MAQ
قائمة مرتبطة الناسخ الفني

المشكلة بيان

تشير مشكلة "حذف عقدة من القائمة المرتبطة بدون مؤشر الرأس" إلى أن لديك قائمة مرتبطة ببعض العقد. أنت الآن تريد حذف عقدة ولكن ليس لديك عنوانها الأصلي. لذا احذف هذه العقدة.

مثال

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

2->3->4->5->6->7
Node to be deleted: 4
2->3->5->6->7

توضيح: نظرًا لأننا أردنا حذف العقدة ذات القيمة 4. قمنا بإزالتها من القائمة المرتبطة وبقيت قائمة مذكورة في الإخراج.

نهج لحذف العقدة بدون مؤشر الرأس

القائمة المرتبطة هي بنية بيانات خطية لها ميزة كبيرة على المصفوفة وهي أنها يمكن أن تختلف في الحجم. إذا كنت تريد إضافة عنصر إلى قائمة مرتبطة ، يمكنك إضافته في وقت O (1). مع الأخذ في الاعتبار أنك تقوم بإدراج العنصر في المقام الأول. ولكن إذا كان عليك أن تفعل الشيء نفسه في مجموعة عادية. سيكلفك الوقت O (N) للقيام بذلك. وبالتالي ، من الأفضل استخدام قائمة مرتبطة عبر مصفوفة في تطبيقات العالم الحقيقي. وتحقق القائمة المرتبطة كل هذا لأنها لا تخزن البيانات كقطعة متجاورة. يخزن كل عنصر في مكان عشوائي. ولكن كيف تحافظ بعد ذلك على النظام؟ الإجابة على هذا السؤال هي أن القائمة المرتبطة تستخدم المؤشر. تشير كل عقدة إلى عقدة أخرى في القائمة المرتبطة ، وبهذه الطريقة لا يتعين علينا تخصيص قطعة واحدة تتغير والتي بدورها تتطلب العديد من العمليات الحسابية.

إذا تم إعطاء مؤشر الرأس

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

الحل

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

رمز

كود C ++ لحذف عقدة بدون مؤشر رئيسي

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

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

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

void deletedNode(node* &head, node* toBeDeleted){
  if(toBeDeleted == NULL)
    return;
  else{
    if(toBeDeleted->next == NULL){
      cout<<"Last node can't be freed";
    }
    // store or swap but ( the data of current node will be deleted)
    toBeDeleted->data = toBeDeleted->next->data;
    toBeDeleted->next = toBeDeleted->next->next;
  }
}

int main(){
  // create a linked list
  node* head = new node();
  head = create(2);
  head->next = create(3);
  node* toBeDeleted = create(4);
  head->next->next = toBeDeleted;
  head->next->next->next = create(5);
  head->next->next->next->next = create(6);
  head->next->next->next->next->next = create(7);

  cout<<"Old Linked List: ";
  node* tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
  deletedNode(head, toBeDeleted);

  cout<<endl<<"New Linked List: ";
  tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
}
Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 5 6 7

كود Java لحذف عقدة بدون مؤشر رئيسي

import java.util.*;
class node{
  int data;
  node next;
}
 
class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.next = null;
    return tmp;
  }
 
  static node deletedNode(node head, node toBeDeleted){
    if(toBeDeleted == null)
      return null;
    else{
      if(toBeDeleted.next == null){
        System.out.print("Last node can't be freed");
        return null;
      }
      // store or swap but ( the data of current node will be deleted)
      toBeDeleted.data = toBeDeleted.next.data;
      toBeDeleted.next = toBeDeleted.next.next;
      return head;
    }
  }
 
  public static void main(String[] args){
    // create a linked list
    node head = new node();
    head = create(2);
    head.next = create(3);
    node toBeDeleted = create(4);
    head.next.next = toBeDeleted;
    head.next.next.next = create(5);
    head.next.next.next.next = create(6);
    head.next.next.next.next.next = create(7);
 
    System.out.print("Old Linked List: ");
    node tmp = head;
    while(tmp != null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
    head = deletedNode(head, toBeDeleted);
 
    System.out.print("\n"+"New Linked List: ");
    tmp = head;
    while(tmp!=null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
  }
}
Old Linked List: 2 3 4 5 6 7 
New Linked List: 2 3 5 6 7

تحليل التعقيد

تعقيد الوقت

يا (1) ، لأن المبادلة يمكن أن تكون معطلة في وقت ثابت. ثم نقوم بتغيير بعض المؤشرات وهي عملية زمنية ثابتة مرة أخرى.

تعقيد الفضاء

يا (1) ، لأن المتغيرات التي استخدمناها لا تعتمد على عدد العقد في القائمة المرتبطة. وبالتالي فإن تعقيد الفضاء ثابت أيضًا.