শীর্ষ নির্দেশক ছাড়াই লিঙ্কযুক্ত তালিকা থেকে একটি নোড মুছুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় জিই হেলথকেয়ার ম্যাক
যোজিত তালিকা টেকনিক্যাল স্ক্রিপ্টার

সমস্যা বিবৃতি

"প্রধান পয়েন্টার ছাড়াই লিঙ্কযুক্ত তালিকা থেকে একটি নোড মুছুন" সমস্যাটি জানিয়েছে যে কয়েকটি নোডের সাথে আপনার লিঙ্কযুক্ত তালিকা রয়েছে। এখন আপনি একটি নোড মুছতে চান তবে আপনার এর প্যারেন্ট নোড ঠিকানা নেই। সুতরাং এই নোড মুছুন।

উদাহরণ

শীর্ষ নির্দেশক ছাড়াই লিঙ্কযুক্ত তালিকা থেকে একটি নোড মুছুন

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

ব্যাখ্যা: যেহেতু আমরা 4 টি মান সহ নোডটি মুছতে চেয়েছি আমরা এটি লিঙ্কযুক্ত তালিকা থেকে সরিয়েছি এবং আউটপুটে উল্লিখিত একটি তালিকা রেখে চলেছি।

হেড পয়েন্টার ছাড়াই নোড মোছার পদ্ধতির

লিঙ্কযুক্ত তালিকাগুলি একটি লিনিয়ার ডেটা স্ট্রাকচার যা একটি অ্যারের উপরে বিশাল সুবিধা অর্জন করে তা হ'ল এটি আকারে পৃথক হতে পারে। আপনি যদি কোনও লিঙ্কযুক্ত তালিকায় কোনও উপাদান যুক্ত করতে চান তবে আপনি এটি ও (1) সময়ে যুক্ত করতে পারেন। আপনি প্রথমে উপাদানটি areোকাচ্ছেন তা বিবেচনা করে। তবে যদি আপনাকে সাধারণ অ্যারেতে একই কাজ করতে হয়। এটি করার জন্য আপনার ও (এন) সময় ব্যয় করতে হবে। সুতরাং বাস্তব-বিশ্বের অ্যাপ্লিকেশনগুলিতে একটি অ্যারের উপরে একটি লিঙ্কযুক্ত তালিকা ব্যবহার করা অনুকূল। এবং লিঙ্কযুক্ত তালিকাগুলি এগুলি সমস্ত অর্জন করে কারণ এটি ডেটাগুলিকে একটি সামঞ্জস্যপূর্ণ অংশ হিসাবে সঞ্চয় করে না। এটি প্রতিটি উপাদানকে কিছু এলোমেলো জায়গায় সঞ্চয় করে। কিন্তু তারপরে কীভাবে এটি অর্ডার বজায় রাখে? এই প্রশ্নের উত্তরটি হল, লিঙ্কযুক্ত তালিকার পয়েন্টারের ব্যবহার লাগে। প্রতিটি নোড লিঙ্কযুক্ত তালিকার অন্য নোডের দিকে নির্দেশ করে এবং এইভাবে আমাদের একটি একক অংশ বরাদ্দ করতে হবে না যার ফলস্বরূপ অনেকগুলি গণনা প্রয়োজন required

যদি হেড পয়েন্টার দেওয়া হত

এখন সমস্যা আমাদের জিজ্ঞাসা একটি নোড মুছুন। সাধারণত, আমাদের একটি নোডের ঠিকানা দেওয়া হয় এবং লিঙ্কযুক্ত তালিকার পরবর্তী নোডটি মুছতে হবে। তবে এখানে আমাদের একটি নোড মুছতে হবে যার ঠিকানা আমাদের দেওয়া হয়েছে। এই সমস্যাটি সমাধানের একটি উপায় হ'ল প্রথমে পুরো লিঙ্কযুক্ত তালিকাকে অতিক্রম করা। তারপরে প্রতিটি নোডের পিতামাতাকে সংরক্ষণ করুন এবং যখন আপনি ইনপুট হিসাবে সরবরাহিত নোডে থাকবেন তখন লুপটি ভাঙ্গুন break এইভাবে শেষ পর্যন্ত আমাদের কাছে নোডের পিতামাতা মুছতে হবে। সুতরাং এখন সমস্যাটি লিঙ্কযুক্ত তালিকার একটি নোডের সরান মুছে ফেলাতে পরিবর্তিত হয়েছে যার পিতামাতার ঠিকানা দেওয়া হয়েছে। তবে এটি করার জন্য আমাদের ও (এন) অপারেশনগুলি ব্যয় করতে হবে। তবে আপনার হেড পয়েন্টার থাকলেই এই উপায়টি ব্যবহার করা যেতে পারে।

সমাধান

সমস্যার সমাধানের জন্য "হেড পয়েন্টার ছাড়াই লিঙ্কযুক্ত তালিকা থেকে একটি নোড মুছুন" মুছে ফেলা হবে নোডের ডেটা এবং লিঙ্কযুক্ত তালিকার পরবর্তী নোড ap লিঙ্কযুক্ত তালিকার প্রতিটি নোড যা পরবর্তী নোড। সুতরাং এই অপারেশনটিতে কেবল ও (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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (1), কারণ অদলবদল স্থির সময়ে ডাউন হতে পারে। এবং তারপরে আমরা কিছু পয়েন্টার পরিবর্তন করেছি যা আবার ধ্রুবক সময় অপারেশন is

স্পেস জটিলতা ity

ও (1), কারণ আমরা যে ভেরিয়েবলগুলি ব্যবহার করেছি তা সংযুক্ত তালিকার নোডের সংখ্যার উপর নির্ভর করে না। সুতরাং স্থান জটিলতাও ধ্রুবক।