দৈনিক কোডিং সমস্যা: এক পাসে লিঙ্ক করা তালিকা থেকে k-th সূচকটি সরান

এক পাসে লিঙ্ক করা তালিকা থেকে k-th সূচক সরানো হচ্ছে

আবার স্বাগত জানাই, অন্য সমস্যা সমাধানের সাথে! আজ, আমরা লিঙ্ক করা তালিকা এবং তাদের উপাদান অপসারণ নিয়ে কাজ করছি। লিঙ্ক করা তালিকাগুলি কী তা নিয়ে আমরা একটু আলোচনা করব, আমরা একটি তৈরি করব এবং কীভাবে এটি থেকে উপাদানগুলি সরানো যায় তা দেখব।

শুরু করার আগে, সাধারণ দাবিত্যাগ:

• এই সমস্যাগুলি বিস্ময়কর নিউজলেটার দৈনিক কোডিং সমস্যা দ্বারা সরবরাহ করা হয়, যা আপনি সদস্যতা নিতে পারেন এখানে . এটি পরীক্ষা করে দেখুন, এবং আপনার চ্যালেঞ্জগুলিও সমাধান করার চেষ্টা করুন!

• আমি একজন বিশেষজ্ঞ প্রোগ্রামার নই: শুধু একজন লোক যে তার শট শেয়ার করতে পছন্দ করে! আপনি যদি একটি অ্যালগরিদম জন্য একটি ভাল বা দ্রুত সমাধান আছে ঘটতে, মন্তব্যে এটি জমা দিন! আমি এই সম্পর্কে আরো কিছু জানতে চাই!

  
  

যথেষ্ট আড্ডা; এর সমস্যা ঝাঁপ দেওয়া যাক!

একটি লিঙ্ক করা তালিকা এবং একটি পূর্ণসংখ্যা k দেওয়া, তালিকার শেষ থেকে k-th নোডটি সরিয়ে দিন এবং তালিকার প্রধানটি ফিরিয়ে দিন।

k তালিকার দৈর্ঘ্যের চেয়ে ছোট হওয়ার নিশ্চয়তা।

এক পাসে এটি করুন।

ঠিক আছে তাহলে, এখানে কি ঘটছে তা একটু ব্যাখ্যা করা যাক: তালিকা থেকে মুছে ফেলার জন্য আমাদের একটি লিঙ্ক করা তালিকা এবং একটি সূচক উপাদান k দেওয়া হয়েছে। এর পরে, আমাদের লিঙ্কযুক্ত তালিকার মাথাটি ফিরিয়ে দেওয়া উচিত।

পরিশেষে, আমাদের অবশ্যই এই সমস্ত কিছু করতে হবে শুধুমাত্র একটি পাসে, যার অর্থ হল আমরা তালিকাটি একবারের বেশি লুপ করতে পারি না।

আমরা নিশ্চিত যে সূচক k তালিকার মধ্যে রয়েছে , তাই তালিকার প্রকৃত দৈর্ঘ্য অতিক্রম করার জন্য আমাদের এটি পরীক্ষা করতে হবে না।

আমরা আজ অ্যালগরিদম তৈরি করতে Go ব্যবহার করব কারণ এর সিনট্যাক্স এই ধরণের কাজের জন্য দুর্দান্ত, এবং একই সময়ে, এটি বোঝার জন্য বেশ সহজ।

আসুন শুরু থেকে শুরু করি: একটি সহজ লিঙ্কযুক্ত তালিকা তৈরি করা।

লিঙ্ক করা তালিকা

লিঙ্কযুক্ত তালিকার পিছনের ধারণাটি বেশ সহজ: এটি বস্তুর তৈরি একটি তালিকা (সাধারণত নোড বলা হয়), এবং প্রতিটি নোডের কমপক্ষে দুটি বৈশিষ্ট্য থাকতে হবে: একটি মান (কোন কিছু আসলে নোডের মধ্যে থাকে) এবং পরবর্তী নোডের একটি লিঙ্ক ।

সাধারণত, একটি পয়েন্টার একটি নোড থেকে অন্য নোডে লাফানোর জন্য একটি লিঙ্ক হিসাবে ব্যবহৃত হয়।

এছাড়াও, তালিকার প্রথম নোডটিকে সাধারণত তালিকার প্রধান বলা হয়, এটিও সেই নোড যা আমাদের সমস্যার দ্বারা ফিরে আসতে বলা হয়।

এখানে একটি গ্রাফিকাল উদাহরণ:

বাম দিকের প্রথম নোডটি তালিকার প্রধান, যেখানে এর মান v₀ এবং একটি মেমরি পয়েন্টার P(n₁) রয়েছে যা তালিকাটিকে পরবর্তী নোড n₁-এ পুনঃনির্দেশ করে। নিম্নলিখিত নোড n₁ এর মান থাকবে এবং পরবর্তী নোডে একটি পয়েন্টার P(n₂) থাকবে , ইত্যাদি।

চূড়ান্ত নোডের, অবশ্যই, নির্দেশ করার মতো কিছুই থাকবে না, তাই এর পয়েন্টারের মান null হবে।

চলুন একটি তৈরি করার কোড দেখুন!

কোডটি বেশ সহজ: আমরা দুটি কাঠামো তৈরি করি, একটি অভ্যন্তরীণ নোডের জন্য এবং একটি লিঙ্কযুক্ত তালিকার জন্য।

• নোড, যেমনটি আমরা এইমাত্র দেখেছি, এর দুটি বৈশিষ্ট্য থাকবে, যথা প্রপার্টি Value এবং প্রোপার্টি Next , যা পরবর্তী নোডের পয়েন্টার হিসেবে *Node টাইপ ধারণ করে।

• লিঙ্ক করা তালিকা, লিঙ্ক করা তালিকাকে "শুরু করতে" একটি কাঠামো, যার শুধুমাত্র একটি সম্পত্তি থাকবে, তালিকার Head ।

  
  

এর পরে, আমরা কেবলমাত্র মূল ফাংশনে তালিকাটি শুরু করি এবং এর মাথাকে 10 এর এলোমেলো মান সহ একটি নোড দিই।

লিংকড লিস্ট বোঝার মূল চাবিকাঠি হল এখন হেড নোড, যেহেতু Node টাইপ , সহজাতভাবে একটি Next প্রপার্টি থাকবে , Head পরবর্তী নোড থাকবে। এই শেষ নোড তারপর তার Next সম্পত্তি থাকবে পরবর্তী নোডে লাফানো, এবং তাই.

আমরা তালিকায় কিছু নোড যোগ করার পরে সবকিছু আরও পরিষ্কার হবে, তাই আসুন এটি করি! আমাদের কাছে দুটি বিকল্প রয়েছে: হয় আমরা এটি ম্যানুয়ালি করি, একটি সত্যিই ক্লান্তিকর কাজ, অথবা আমরা আরও কিছু নোড যুক্ত করার জন্য লিঙ্কযুক্ত তালিকা শ্রেণীর জন্য একটি পদ্ধতি লিখি। এর এটা চেক আউট করা যাক!

নোড যোগ করা: ছদ্মবেশে পরিবর্তনযোগ্য তালিকা

এমনকি যদি আপনার সামান্য প্রোগ্রামিং অভিজ্ঞতা থাকে, প্রায় প্রতিটি প্রোগ্রামিং ভাষায়, আপনার শোনা উচিত ছিল প্রথম ধারণাগুলির মধ্যে একটি হল পরিবর্তনযোগ্য এবং অপরিবর্তনীয় তালিকার মধ্যে পার্থক্য।

তাদের নাম অনুসারে, পরিবর্তনযোগ্য তালিকা হল সেই তালিকা যা আপনি ম্যানিপুলেট করতে এবং উপাদান যোগ করতে পারেন ৷ অপরিবর্তনীয়, এর পরিবর্তে, একটি নির্দিষ্ট আকার থাকে এবং নতুন উপাদানগুলির সাথে যুক্ত করা যায় না । কিন্তু কেন এমন হল?

অপরিবর্তনীয় তালিকাগুলি মেমরিতে সংলগ্ন থাকে, যার অর্থ তাদের উপাদানগুলি ক্রমানুসারে মেমরিতে সংরক্ষণ করা হয়: 3টি উপাদানের একটি তালিকার জন্য, যদি প্রথম উপাদানটি 0x00 এ সংরক্ষণ করা হয়, তাহলে দ্বিতীয়টি 0x01 এ এবং শেষটি 0x02 এ থাকবে।

এই কারণেই এটি একটি নির্দিষ্ট অ্যারে, একটি অপরিবর্তনীয় তালিকা, বা পাইথনের একটি টিপলের উপর পুনরাবৃত্তি করা এত দ্রুত কারণ সিপিইউ কেবল একের পর এক মেমরি সূচকগুলি স্মরণ করে।

অন্যদিকে, পরিবর্তনযোগ্য তালিকাগুলি শুধুমাত্র মেমরিতে সংলগ্ন থাকে যখন প্রথম শুরু হয়: সেই সময়ে, যদি উপাদানগুলি যোগ করা হয়, সেগুলি আর অনুক্রমিক হবে না। তাই কিভাবে আমরা তাদের উপর লুপ করতে পারেন?

ঠিক আছে, কারণ প্রথম সূচনার শেষ উপাদানটিতে একটি পয়েন্টার থাকবে যা উপাদানটির পরে যোগ করা হয়েছে , যা আমাদেরকে উপাদানের সাথে যুক্ত করবে এবং আরও অনেক কিছু। তাই হ্যাঁ, পরিবর্তনযোগ্য তালিকাগুলি আসলেই প্রায়ই ছদ্মবেশে লিঙ্কযুক্ত তালিকা!

এখন, কোডটি দেখি:

আমরা আমাদের লিঙ্ক করা তালিকার পদ্ধতিতে AddNode পদ্ধতি যোগ করেছি। একটি নোড যোগ করার প্রক্রিয়া এই মত যায়:

• প্রথমত, আমরা current নামক একটি ভেরিয়েবলে Head মান সংরক্ষণ করি

• পরবর্তী, আমরা প্রতিবার পরবর্তী নোডের সাথে current ভেরিয়েবল আপডেট করে লিঙ্ক করা তালিকার উপর লুপ করি, যতক্ষণ না পরবর্তী নোডটি শূন্য হয়। আমরা বর্তমানে যে নোডটিতে আছি তার একটি নাল পয়েন্টার থাকলে, আমরা জানি যে আমরা তালিকার শেষ নোডে আছি।

• অবশেষে, আমরা এই শেষ নোডটিকে একটি নতুন নোড এবং একটি নতুন মান দিয়ে আপডেট করি (এই নতুন নোডের Next পয়েন্টারটি ফাঁকা রেখে দিলে সেটি নাল হিসাবে সেট করা হবে)

  
  

গ্রাফিকভাবে, এই প্রক্রিয়াটি এরকম কিছু:

আমরা মূল ফাংশনে এই পদ্ধতির সঠিক কার্যকারিতা পরীক্ষা করতে পারি, লিঙ্ক করা তালিকায় নোডগুলির মানগুলি প্রিন্ট করে।

নোড অপসারণ

এখন আমাদের সমস্যার চূড়ান্ত অংশ এবং সমাধানের জন্য: সঠিক সূচক সহ একটি নোড অপসারণ করা। প্রথম বন্ধ, এটি একটি লিঙ্ক তালিকা থেকে একটি নোড অপসারণ মানে কি? যদি আমরা এটি সম্পর্কে চিন্তা করি, একটি লিঙ্ক করা তালিকার একটি নোড শুধুমাত্র বিদ্যমান থাকে যদি এটি পূর্ববর্তীটির সাথে সংযুক্ত থাকে , তাই না?

উদাহরণস্বরূপ, যদি আমরা n-1ᵗʰ কে null এর একটি Next মান দেই, তাহলে আমরা তালিকা থেকে nᵗʰ মানটিকে সংযোগ বিচ্ছিন্ন করতে পারি।

আমরা যে উপাদানটি সরাতে চাই সেটি শেষ না হলে কী হবে? ঠিক আছে, আমরা আগেরটির সাথে পরেরটির সাথে সংযোগ স্থাপন করে উপাদানটিকে আনলিঙ্ক করতে পারি!

সুতরাং kᵗʰ উপাদানটি অপসারণ করতে, আমাদের অবশ্যই k-1ᵗʰ উপাদানটি খুঁজে বের করতে হবে এবং এটিকে k+1ᵗʰ নোডের সাথে লিঙ্ক করতে হবে। আমাদের আগের নোড (k-1ᵗʰ) সংরক্ষণ করতে হবে।

স্পষ্টতই, আমরা সরাসরি তালিকাটি সূচী করতে পারি না : linkedlist[n] শুধু একটি ত্রুটি বাড়িয়ে তুলবে। যদিও এই দেওয়া, আমরা সূচক 0 হিসাবে তালিকার প্রধান বিবেচনা করতে পারেন, এবং সূচক 1 হিসাবে তার পরবর্তী নোড, এবং তাই, এবং আমরা নোডের উপর লুপ করতে পারেন, যেমন আমরা আগে করেছি.

আমরা তখন যা করতে পারি তা হল আমরা যে নোডটিতে আছি তার ট্র্যাক রাখার জন্য একটি কাউন্টার প্রয়োগ করা!

এর তারপর কোড করা যাক.

আসুন RemoveNode ফাংশনটি দেখি যা একটি index অ্যাট্রিবিউট গ্রহণ করে। এর পরে, আমরা তিনটি ভেরিয়েবল শুরু করি:

• previousNode , যা পূর্ববর্তী নোড ধরে রাখবে

• current , যা লুপের সময় আমরা যে নোডটি চালু করি তা ধরে রাখবে

• counter , প্রাথমিকভাবে 0 এর সমান, যা তালিকায় আমাদের অবস্থান ধরে রাখবে

  
  

চলুন মুহুর্তের জন্য প্রথম যদি ব্লকটি এড়িয়ে যাই এবং পরিবর্তে লুপের দিকে মনোনিবেশ করি। আমাদের counter ভেরিয়েবল আমাদের index থেকে কঠোরভাবে ছোট না হওয়া পর্যন্ত আমরা লুপ করা শুরু করি: প্রতিটি লুপ বর্তমানের সাথে আগের নোড আপডেট করবে এবং বর্তমান নোড এবং কাউন্টার আপডেট করতে এগিয়ে যাবে।

লুপ ভেঙ্গে গেলে, এর মানে হল যে আমরা আমাদের কাঙ্খিত সূচকের ঠিক আগে নোডে আছি: আমাদের শুধুমাত্র পূর্ববর্তী নোডের পয়েন্টার আপডেট করতে হবে, prev.Next , তালিকার পরবর্তী নোডের সাথে যেটিতে আমরা আছি। current.Next হবে । পরবর্তী । অবশেষে, আমরা লিঙ্কযুক্ত তালিকার মাথাটি ফিরিয়ে দিই।

এখন কি হবে যদি সূচকটি সরাতে হয় মাথা, যার সূচক 0 থাকে? লুপ কখনই শুরু হবে না কারণ এটি counter = 0 এবং index = 0 দিয়ে শুরু হবে, এবং শর্তটি অবিলম্বে মিথ্যা হবে। আমরা শীর্ষে if ব্লক দিয়ে এই প্রথম কেসটি পরিচালনা করতে পারি।

মূলত, যদি সূচকটি 0 হয়, তাহলে আমরা সরাসরি লিঙ্ক করা তালিকার মাথাটি তার পাশের নোডের সাথে আপডেট করতে পারি এবং এটি ফেরত দিতে পারি। আমি আপনার দৃষ্টি আকর্ষণ করতে চাই, বিশেষ করে 31 লাইনের দিকে: যান, অন্যান্য অনেক ভাষার মতো, মান দ্বারা ফাংশনে বৈশিষ্ট্যগুলি পাস করে , যার অর্থ ফাংশনটি পাস করা বস্তুর একটি অনুলিপি ধরে রাখে, আপনি যে প্রকৃত বস্তুটি পাস করছেন তা নয় .

এই ধারণাটি এই উদাহরণে স্পষ্টভাবে দেখা যায়:

 package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.

আমরা একটি বৈশিষ্ট্য হিসাবে পাস করা মানের মেমরি ঠিকানা প্রিন্ট করার জন্য একটি ফাংশন তৈরি করি। তারপর, প্রধান ফাংশনে, আমরা একটি ভেরিয়েবল a তৈরি করি এবং এর মেমরির ঠিকানা প্রিন্ট আউট করি। তারপর আমরা একই ভেরিয়েবলকে ফাংশনে পাস করি এবং এর মেমরি অ্যাড্রেস প্রিন্ট করি।

আপনি দেখতে পাচ্ছেন, যদি আপনি চেষ্টা করেন, ফলাফলগুলি ভিন্ন হবে: এর কারণ হল বৈশিষ্ট্যগুলিকে মান হিসাবে ফাংশনে পাস করা হয়, যার অর্থ a কপি শুধুমাত্র এটিকে ফাংশনে পাস করার উদ্দেশ্যে তৈরি করা হয়।

আমাদের লিঙ্কযুক্ত তালিকায় ফিরে আসুন, উপরের একই সমস্যার জন্য আসল মাথা পেতে আমাদের অবশ্যই পয়েন্টার ব্যবহার করতে হবে। তাই “real” ll.Node এ যেতে হলে আমাদের অবশ্যই এর পয়েন্টার, *ll.Node স্মরণ করতে হবে এবং এটিকে *ll.Node = *ll.Node.Next দিয়ে আরও সরাতে হবে ।

মূল ফাংশনে, আমরা পদ্ধতিতে কল যোগ করি, উদাহরণস্বরূপ, ll.RemoveNode(0) এবং ll.RemoveNode(2) কল করা, এবং আমরা ফলাফলটি পরীক্ষা করতে পারি যেখানে নোড 0 এবং নোড 2 অনুপস্থিত থাকবে।

উপসংহার

আমরা শেষ পর্যন্ত এটি তৈরি করেছি!

আপনি যদি এই বিন্দু পর্যন্ত পড়েন তবে আমার পুরো কৃতজ্ঞতা আপনার কাছে যায়। আপনি যদি একটি বা দুটি লাইক ছেড়ে নিবন্ধটি ভাগ করতে ইচ্ছুক হন তবে এটি আমার দিন তৈরি করবে এবং আমাকে এই নিবন্ধগুলি লেখা চালিয়ে যেতে সাহায্য করবে!

পরের প্রবন্ধে দেখা হবে, এবং, বরাবরের মত, পড়ার জন্য ধন্যবাদ।

নিকোলা