Изтриване на възел от свързан списък без указател на главата


Ниво на трудност Лесно
Често задавани в GE Healthcare 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

Анализ на сложността

Сложност във времето

O (1), тъй като размяната може да намалее през постоянно време. И тогава просто сменяме някои указатели, което отново е постоянна операция във времето.

Сложност на пространството

O (1), тъй като променливите, които сме използвали, не зависят от броя на възлите в свързания списък. По този начин сложността на пространството също е постоянна.