Избришете јазол од поврзаната листа без главен покажувач


Ниво на тешкотија Лесно
Често прашувано во ГЕ здравство MAQ
Поврзан список Технички скриптер

Изјава за проблем

Проблемот „Избриши јазол од поврзана листа без главен покажувач“ наведува дека имате поврзана листа со некои јазли. Сега сакате да избришете јазол, но ја немате неговата адреса на родителскиот јазол. Затоа избришете го овој јазол.

пример

Избришете јазол од поврзаната листа без главен покажувач

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

Објаснување: Бидејќи сакавме да го избришеме јазолот со вредност 4. Го отстранивме од поврзаната листа и останавме со список што се споменува во излезот.

Пристап кон бришење јазол без покажувач на главата

Поврзаната листа е линеарна структура на податоци што има огромна предност во однос на низата е тоа што може да се разликува по големина. Ако сакате да додадете елемент во поврзана листа, можете да го додадете во време О (1). Имајќи предвид дека го вметнувате елементот на прво место. Но, ако требаше да го сториш истото во нормална низа. Youе ве чини О (Н) време да го сторите тоа. Така е поволно да се користи поврзана листа преку низа во реални апликации. И поврзаната листа го постигнува сето ова бидејќи не ги зачувува податоците како соседно парче. Тој го чува секој елемент на некоја случајна локација. Но, тогаш како го одржува редот? Одговорот на ова прашање е, поврзаниот список ја користи употребата на покажувачот. Секој јазол покажува на друг јазол во поврзаната листа и на овој начин не треба да одвоиме ниту едно парче менување, што за возврат ќе бараше многу пресметки.

Ако беше даден главата покажувач

Сега проблемот го бара тоа од нас избришете јазол. Општо, ни е дадена адреса на јазол и се бара да го избришеме следниот јазол во поврзаната листа. Но, тука треба да избришеме јазол чија адреса ни е дадена. Еден начин да се реши овој проблем е прво да се пресече целата поврзана листа. Потоа зачувајте го родителот на секој јазол и скршете ја јамката кога сте на јазол што е даден како влез. На овој начин на крајот имаме родител на јазолот што треба да се избрише. Па сега, проблемот е променет во едноставно бришење на јазол во поврзаната листа чија адреса на родител е дадена. Но, ова ќе не чини операции О (Н). Но, овој начин може да се користи само кога имате главен покажувач.

Решение

Пристапот за проблемот „Избриши јазол од поврзана листа без покажувач на глава“ би бил да ги замениме податоците на јазолот што треба да се избрише и следниот јазол во поврзаната листа. Секој јазол во поврзаната листа чува кој јазол е следен. Значи, оваа операција има само 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

Јава код за бришење јазол без покажувач на глава

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), бидејќи променливите што ги користевме не зависат од бројот на јазли во поврзаната листа. Така, комплексноста на просторот е исто така постојана.