ഹെഡ് പോയിന്റർ ഇല്ലാതെ ലിങ്കുചെയ്‌ത ലിസ്റ്റിൽ നിന്ന് ഒരു നോഡ് ഇല്ലാതാക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു GE ഹെൽത്ത്കെയർ 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) സമയ സങ്കീർണ്ണത മാത്രമേയുള്ളൂ. ഇപ്പോൾ ഡാറ്റ സ്വാപ്പ് ചെയ്യുമ്പോൾ. മാതാപിതാക്കളുടെ വിലാസം നൽകിയിട്ടുള്ള നോഡ് ഇല്ലാതാക്കുന്നതിലേക്ക് ഞങ്ങൾ വീണ്ടും പ്രശ്നം മാറ്റി. ഇപ്പോൾ പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾക്ക് എളുപ്പമാണ്. എൻഡ് നോഡ് ഇല്ലാതാക്കേണ്ടിവരുമ്പോൾ ഒരു എഡ്ജ് കേസ് ഉണ്ട്, പക്ഷേ ഞങ്ങൾക്ക് അത് ഇല്ലാതാക്കാൻ കഴിയില്ല. കാരണം അടുത്ത നോഡ് ഇല്ല.

കോഡ്

ഹെഡ് പോയിന്റർ ഇല്ലാതെ ഒരു നോഡ് ഇല്ലാതാക്കുന്നതിനുള്ള സി ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (1), കാരണം സ്വാപ്പിംഗ് നിരന്തരമായ സമയത്ത് പ്രവർത്തനരഹിതമാകും. എന്നിട്ട് ഞങ്ങൾ ചില പോയിന്ററുകൾ മാറ്റുന്നു, അത് വീണ്ടും ഒരു സ്ഥിരമായ സമയ പ്രവർത്തനമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), കാരണം ഞങ്ങൾ ഉപയോഗിച്ച വേരിയബിളുകൾ ലിങ്കുചെയ്‌ത ലിസ്റ്റിലെ നോഡുകളുടെ എണ്ണത്തെ ആശ്രയിക്കുന്നില്ല. അതിനാൽ സ്ഥല സങ്കീർണ്ണതയും സ്ഥിരമാണ്.