מחק צומת מהרשימה המקושרת ללא מצביע ראש


רמת קושי קַל
נשאל לעתים קרובות GE Healthcare מאק
רשימה מקושרת סקריפט טכני

הצהרת בעיה

הבעיה "מחק צומת מרשימה מקושרת ללא מצביע ראש" קובעת שיש לך רשימה מקושרת עם כמה צמתים. כעת ברצונך למחוק צומת אך אין לך את כתובת צומת האב שלו. אז מחק את הצומת הזה.

דוגמה

מחק צומת מהרשימה המקושרת ללא מצביע ראש

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

ניתוח מורכבות

מורכבות זמן

O (1), מכיוון שההחלפה יכולה להיות למטה בזמן קבוע. ואז פשוט משנים כמה מצביעים שזו שוב פעולת זמן קבועה.

מורכבות בחלל

O (1), מכיוון שהמשתנים בהם השתמשנו אינם תלויים במספר הצמתים ברשימה המקושרת. כך מורכבות החלל היא גם קבועה.