წაშალეთ კვანძი დაკავშირებული სიიდან სათაურის მაჩვენებლის გარეშე


Რთული ტური Easy
ხშირად ეკითხებიან GE Healthcare MAQ
მიბმული სია ტექნიკური სკრიპტერი

პრობლემის განცხადება

პრობლემა "წაშალეთ კვანძი დაკავშირებული სიიდან სათაურის მაჩვენებლის გარეშე" აცხადებს, რომ თქვენ გაქვთ დაკავშირებული კვანძი ზოგიერთ კვანძთან. ახლა გსურთ კვანძის წაშლა, მაგრამ არ გაქვთ მისი მშობლის კვანძის მისამართი. ასე რომ, წაშალეთ ეს კვანძი.

მაგალითი

წაშალეთ კვანძი დაკავშირებული სიიდან სათაურის მაჩვენებლის გარეშე

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

განმარტება: ვინაიდან გვინდოდა მე -4 მნიშვნელობის კვანძის წაშლა. ჩვენ ის ამოვიღეთ დაკავშირებული სიიდან და დარჩა სია, რომელიც მითითებულია გამომავალში.

მიდგომა კვანძის წაშლის თავით მაჩვენებლის გარეშე

Linked List არის ხაზოვანი მონაცემთა სტრუქტურა, რომელსაც აქვს უდიდესი უპირატესობა მასივის მიმართ, არის ის, რომ მისი ზომა შეიძლება განსხვავდებოდეს. თუ გსურთ დაამატოთ ელემენტი დაკავშირებულ სიაში, შეგიძლიათ დაამატოთ O (1) დროში. იმის გათვალისწინებით, რომ თქვენ პირველ რიგში ჩადებთ ელემენტს. მაგრამ თუ თქვენ იგივე უნდა გააკეთოთ ჩვეულებრივ მასივში. დაგიჯდებათ O (N) დრო ამის გაკეთება. ამრიგად, სასურველია გამოიყენოს დაკავშირებული სია მასივზე რეალურ პროგრამებში. და დაკავშირებული სია აღწევს ამ ყველაფერს, რადგან ის არ ინახავს მონაცემებს, როგორც მომიჯნავე ბლოკი. ის ინახავს თითოეულ ელემენტს რაიმე შემთხვევით ადგილას. მაგრამ შემდეგ როგორ ინარჩუნებს წესრიგი? ამ კითხვაზე პასუხია: მიბმული სია იყენებს მაჩვენებლის გამოყენებას. თითოეული კვანძი მიუთითებს დაკავშირებული კვანძის სხვა კვანძზე და ამ გზით ჩვენ არ უნდა გამოვყოთ ერთი ბლოკი, რაც თავის მხრივ საჭირო იქნებოდა მრავალი გამოთვლა.

თუ თავით მაჩვენებელი მიეცა

ახლა პრობლემა ამას გვთხოვს კვანძის წაშლა. საერთოდ, ჩვენ გვეძლევა კვანძის მისამართი და მოგვმართავს შემდეგი კვანძის წაშლა დაკავშირებულ სიაში. მაგრამ აქ ჩვენ უნდა წაშალოთ კვანძი, რომლის მისამართიც მოგვცეს. ამ პრობლემის გადაჭრის ერთ-ერთი გზაა, პირველ რიგში, მთლიანი დაკავშირებული სიის გადაკვეთა. შემდეგ შეინახეთ თითოეული კვანძის მშობელი და დაანგრიეთ მარყუჟი, როდესაც იმ კვანძზე იმყოფებით, რომელიც შეყვანილია. ამ გზით ჩვენ საბოლოოდ გვაქვს კვანძის მშობელი, რომელიც უნდა წაიშალოს. ახლა პრობლემა შეიცვალა იმ კვანძის მარტივი წაშლით, რომელიც დაკავშირებულია სიაში, რომლის მშობლის მისამართიც არის მოცემული. მაგრამ ამის გაკეთება O (N) ოპერაციად დაგვიჯდება. მაგრამ ამ ხერხის გამოყენება შესაძლებელია მხოლოდ მაშინ, როდესაც თქვენ გაქვთ საჩვენებელი მაჩვენებელი.

Solution

პრობლემის "კვანძის წაშლა მიბმული სიიდან სათაურის მაჩვენებლის გარეშე" მიდგომა იქნება გასაგები კვანძისა და შემდეგი კვანძის დაკავშირებული მონაცემების შეცვლა. თითოეული კვანძი მიბმულ სიაში ინახავს რომელი კვანძია შემდეგი. ამ ოპერაციას მხოლოდ 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

სირთულის ანალიზი

დროის სირთულე

O (1), რადგან შეცვლა შეიძლება შემცირდეს მუდმივ დროში. შემდეგ ჩვენ უბრალოდ ვცვლით ზოგიერთ მითითებას, რაც ისევ მუდმივი დროის ოპერაციაა.

სივრცის სირთულე

O (1), რადგან ის ცვლადები, რომლებიც ჩვენ გამოვიყენეთ, არ არის დამოკიდებული კვანძების რაოდენობაზე მიბმულ სიაში. ამრიგად, სივრცის სირთულე ასევე მუდმივია.