জাভা লিঙ্কডলিস্ট

ওহে! সমস্ত সাম্প্রতিক পাঠগুলি ArrayList- এ উৎসর্গ করা হয়েছে । এই তথ্য কাঠামো খুব সুবিধাজনক এবং দরকারী. এটি প্রচুর কাজ পরিচালনা করতে পারে। কিন্তু জাভা অন্যান্য অনেক তথ্য কাঠামো আছে. কেন? সর্বোপরি, কারণ কাজের পরিধি বিশাল, এবং সবচেয়ে দক্ষ ডেটা স্ট্রাকচার বিভিন্ন কাজের জন্য আলাদা। আজ আমরা একটি নতুন কাঠামোর সাথে দেখা করব: Java LinkedList , একটি দ্বিগুণ লিঙ্কযুক্ত তালিকা। আসুন দেখি এটি কীভাবে সংগঠিত, কেন এটিকে দ্বিগুণ-সংযুক্ত বলা হয়, কীভাবে এটি ArrayList থেকে আলাদা । জাভা লিঙ্কডলিস্টের উপাদানগুলি আসলে একটি একক চেইনের লিঙ্ক। ডেটা ছাড়াও, প্রতিটি উপাদান পূর্ববর্তী এবং পরবর্তী উপাদানগুলির রেফারেন্স সংরক্ষণ করে। এই রেফারেন্সগুলি আপনাকে এক উপাদান থেকে অন্য উপাদানে যেতে দেয়। এইভাবে আপনি একটি তৈরি করুন:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

আউটপুট: [হ্যালো ওয়ার্ল্ড! আমার নাম আর্ল, আমি জাভা ভালোবাসি, আমি কানাডায় থাকি] এখানে আমাদের তালিকাটি কেমন দেখাচ্ছে: আসুন দেখি কীভাবে একটি নতুন উপাদান যুক্ত করা যায়। এটি add() পদ্ধতি ব্যবহার করে করা হয়।

earlBio.add(str2);

কোডের বিন্দুতে, আমাদের তালিকায় একটি উপাদান রয়েছে: স্ট্রিং str1 । চলুন দেখে নেওয়া যাক ছবিতে পরবর্তীতে কী হয়: ফলস্বরূপ, str2 এবং str1 তালিকার এই নোডগুলিতে সংরক্ষিত পরবর্তী এবং পূর্ববর্তী লিঙ্কগুলির মাধ্যমে লিঙ্ক হয়ে গেছে : এখন আপনার দ্বিগুণ-লিঙ্কযুক্ত তালিকার মূল ধারণাটি বোঝা উচিত। লিঙ্কের এই চেইনটিই লিঙ্কডলিস্টের উপাদানগুলিকে একটি একক তালিকা করে তোলে। ArrayList এর বিপরীতে , LinkedList এর ভিতরে কোনো অ্যারে বা অ্যারের মতো কিছু নেই। ArrayList এর সাথে যেকোন (ভাল, বেশিরভাগ) কাজ অভ্যন্তরীণ অ্যারের সাথে কাজ করে। Java LinkedList এর সাথে যেকোনো কাজলিংক পরিবর্তন করার জন্য নিচে ফুটন্ত. তালিকার মাঝখানে একটি উপাদান যোগ করে এটি খুব স্পষ্টভাবে দেখা যেতে পারে:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

আপনি দেখতে পাচ্ছেন, ওভারলোড করা অ্যাড() পদ্ধতি আপনাকে একটি নতুন আইটেমের জন্য একটি নির্দিষ্ট সূচক নির্দিষ্ট করতে দেয়। এই ক্ষেত্রে, আমরা str1 এবং str3 এর মধ্যে স্ট্রিং str2 যোগ করতে চাই । এটি অভ্যন্তরীণভাবে ঘটবে: অভ্যন্তরীণ লিঙ্কগুলি পরিবর্তন করার পরে, str2 সফলভাবে তালিকায় যোগ করা হয়েছে: এখন 3টি উপাদান সংযুক্ত। আপনি পরবর্তী লিঙ্কের মাধ্যমে চেইনের প্রথম উপাদান থেকে শেষ এবং আবার ফিরে যেতে পারেন। সুতরাং, আমরা সন্নিবেশের সাথে মোটামুটি আরামদায়ক, কিন্তু উপাদান অপসারণ সম্পর্কে কি? নীতি ঠিক একই। আমরা কেবল অপসারণ করা উপাদানটির "বাম এবং ডানদিকে" দুটি উপাদানের লিঙ্কগুলি আপডেট করি:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

সূচী 1 সহ আইটেমটি মুছে ফেললে কি হবে (এটি তালিকার মাঝখানে রয়েছে): লিঙ্কগুলি আপডেট করার পরে, আমরা পছন্দসই ফলাফল পাই: ArrayList- এ অপসারণ অপারেশনের বিপরীতে , এখানে অ্যারে উপাদানগুলিকে স্থানান্তরিত করার বা করার দরকার নেই ধরনের কিছু আমরা শুধু str1 এবং str3 এর জন্য লিঙ্ক আপডেট করি । তারা এখন একে অপরের দিকে নির্দেশ করে, এবং str2 লিঙ্কের চেইন থেকে " বাদ পড়েছে " এবং তালিকার আর অংশ নয়।

পদ্ধতির ওভারভিউ

ArrayList এর সাথে LinkedList-এর অনেকগুলি পদ্ধতির মিল রয়েছে । উদাহরণস্বরূপ, উভয় শ্রেণীরই পদ্ধতি রয়েছে যেমন add() , remove() , indexOf() , clear() , contains() (একটি আইটেম তালিকায় আছে কিনা তা নির্দেশ করে), set() (একটি বিদ্যমান উপাদান প্রতিস্থাপন করে), এবং আকার() । যদিও তাদের মধ্যে অনেকেই অভ্যন্তরীণভাবে ভিন্নভাবে কাজ করে (যেমন আমরা add() এবং remove() দিয়ে পেয়েছি ), শেষ ফলাফল একই। যাইহোক, লিংকডলিস্টের তালিকার শুরু এবং শেষের সাথে কাজ করার জন্য আলাদা পদ্ধতি রয়েছে, যা ArrayList-এর নেই:

• addFirst() , addLast() : তালিকার শুরু/শেষে একটি উপাদান যুক্ত করার জন্য এই পদ্ধতিগুলি

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

আউটপুট: [কার{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] [কার{model='Ford Mondeo'}, Car{model=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] আমরা তালিকার শীর্ষে "Ford" দিয়ে শেষ করি , এবং শেষে "ফিয়াট"।

• peekFirst() , peekLast() : পদ্ধতিগুলি তালিকার প্রথম/শেষ উপাদান প্রদান করে। তালিকা খালি থাকলে তারা শূন্য ফেরত দেয়।

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

আউটপুট: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'}

• pollFirst() , pollLast() : এই পদ্ধতিগুলি তালিকার প্রথম/শেষ উপাদানটি ফিরিয়ে দেয় এবং তালিকা থেকে সরিয়ে দেয়। তালিকা খালি থাকলে তারা শূন্য ফেরত দেয়

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

আউটপুট: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'} তালিকায় কী বাকি আছে? [কার{মডেল='বুগাটি ভেরন'}]

• toArray() : এই পদ্ধতিটি তালিকা আইটেম ধারণকারী একটি অ্যারে প্রদান করে

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

আউটপুট: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] এখন আমরা জানি কিভাবে LinkedList কাজ করে এবং কিভাবে এর সংগঠন ArrayList থেকে আলাদা । LinkedList ব্যবহার করার সুবিধা কি কি ? সর্বোপরি, তালিকার মাঝখানে কাজ করার সময় আমরা উপকৃত হই। একটি লিঙ্কডলিস্টের মাঝখানে সন্নিবেশ এবং অপসারণের ক্রিয়াকলাপগুলি অ্যারেলিস্টের তুলনায় অনেক সহজ । আমরা কেবল প্রতিবেশী উপাদানগুলির লিঙ্কগুলিকে আপডেট করি এবং অবাঞ্ছিত উপাদানগুলি লিঙ্কগুলির চেইন থেকে "ড্রপ আউট" করি৷ কিন্তু একটি ArrayList , আমরা অবশ্যই

• পর্যাপ্ত জায়গা আছে কিনা পরীক্ষা করুন (ঢোকানোর সময়)
• যদি না হয়, তাহলে আমরা একটি নতুন অ্যারে তৈরি করি এবং সেখানে ডেটা অনুলিপি করি (ঢোকানোর সময়)
• আমরা উপাদানটি অপসারণ/সন্নিবেশ করি এবং অন্যান্য সমস্ত উপাদানকে ডান/বামে নিয়ে যাই (অপারেশনের ধরণের উপর নির্ভর করে)। এবং এই প্রক্রিয়ার জটিলতা তালিকার আকারের উপর ব্যাপকভাবে নির্ভর করে। 10টি উপাদান কপি/সরানো এক জিনিস, এবং এক মিলিয়ন উপাদানের সাথে একই কাজ করা অন্য জিনিস।

অন্য কথায়, যদি তালিকার মাঝখানে সন্নিবেশ/অপসারণের ক্রিয়াকলাপগুলি আপনার প্রোগ্রামে সবচেয়ে সাধারণ হয়, লিঙ্কডলিস্টটি ArrayList এর চেয়ে দ্রুত হওয়া উচিত ।

ধারণায়

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

আউটপুট: LinkedList দ্বারা নেওয়া সময় (মিলিসেকেন্ডে) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

আউটপুট: ArrayList দ্বারা নেওয়া সময় (মিলিসেকেন্ডে) = 181 এটি অপ্রত্যাশিত ছিল! আমরা একটি অপারেশন করেছি যেখানে লিঙ্কডলিস্ট অনেক বেশি দক্ষ হওয়া উচিত: একটি তালিকার মাঝখানে 100টি আইটেম সন্নিবেশ করানো। এবং আমাদের তালিকা বিশাল: 5,000,000 উপাদান। অ্যারেলিস্টকে প্রতি সন্নিবেশের সাথে কয়েক মিলিয়ন আইটেম স্থানান্তর করতে হয়েছিল! এটা কিভাবে জিতেছে? প্রথমত, অ্যারেলিস্টের উপাদানগুলি অ্যাক্সেস করার জন্য প্রয়োজনীয় সময় স্থির (ধ্রুবক)। আপনি যখন লিখবেন

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

তারপর ArrayList [2_000_000] একটি নির্দিষ্ট মেমরির ঠিকানা (সর্বশেষে, তালিকার একটি অভ্যন্তরীণ অ্যারে আছে)। কিন্তু, একটি লিঙ্কডলিস্টের একটি অ্যারে নেই। এটি লিঙ্কের চেইন বরাবর উপাদান নম্বর 2_000_000 অনুসন্ধান করবে। লিঙ্কডলিস্টের জন্য, এটি একটি মেমরি ঠিকানা নয়, তবে একটি লিঙ্ক যা এখনও পৌঁছাতে হবে: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. নেক্সট _ , অ্যারেলিস্ট ইতিমধ্যেই অ্যাক্সেস করার জন্য সঠিক মেমরি ঠিকানা জানে, কিন্তু লিঙ্কডলিস্টকে এখনও "সেখানে পেতে" প্রয়োজন। দ্বিতীয়ত, ArrayList এর গঠন আছেনিজেই একটি বিশেষ অভ্যন্তরীণ ফাংশন ( System.arrayCopy() ) অভ্যন্তরীণ অ্যারেকে প্রসারিত করে এবং সমস্ত উপাদান কপি করে এবং স্থানান্তর করে। এটি খুব দ্রুত, কারণ এটি এই নির্দিষ্ট কাজের জন্য অপ্টিমাইজ করা হয়েছে। কিন্তু যখন আপনাকে একটি নির্দিষ্ট সূচকে "যাতে" হবে না, লিঙ্কডলিস্ট বিজয়ী। ধরুন আমরা তালিকার একেবারে শুরুতে সন্নিবেশ করেছি। আসুন সেখানে এক মিলিয়ন উপাদান সন্নিবেশ করার চেষ্টা করি:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

আউটপুট: মিলিসেকেন্ডে ফলাফল: 43448 মিলিসেকেন্ডে ফলাফল: 107 এখন আমরা একটি সম্পূর্ণ ভিন্ন ফলাফল পেয়েছি! ArrayList 43 সেকেন্ডেরও বেশি সময় ব্যয় করেছে তালিকার সামনে এক মিলিয়ন আইটেম ঢোকাতে, যেখানে LinkedList 0.1 সেকেন্ডের মধ্যে এটি করতে পেরেছে! লিঙ্কডলিস্ট এখানে উপকৃত হয়েছে, কারণ এটিকে প্রতিবার তালিকার মাঝখানে লিঙ্কের চেইন দিয়ে চালানোর দরকার ছিল না। এটি অবিলম্বে তালিকার শুরুতে প্রয়োজনীয় সূচক খুঁজে পায়, তাই বিভিন্ন অ্যালগরিদম ইতিমধ্যেই একটি সুবিধা। :) আসলে, " ArrayList বনাম LinkedList " আলোচনা খুবই বিস্তৃত, এবং আমরা বর্তমান স্তরে এর গভীরে প্রবেশ করব না। প্রধান জিনিস যা আপনাকে মনে রাখতে হবে তা হল:

• সমস্ত তাত্ত্বিক সুবিধাগুলি যে কোনও নির্দিষ্ট সংগ্রহ সর্বদা বাস্তবে কাজ করে না (আমরা তালিকার মাঝখানের উদাহরণ সহ এটি দেখেছি)
• একটি সংগ্রহ বাছাই করার ক্ষেত্রে চরম অবস্থান গ্রহণ করবেন না (" অ্যারেলিস্ট সর্বদা দ্রুত। এটি ব্যবহার করুন এবং আপনি ভুল করতে পারবেন না। কেউই দীর্ঘদিন ধরে লিঙ্কডলিস্ট ব্যবহার করছে না")।

যদিও লিঙ্কডলিস্টের লেখক, জোশুয়া ব্লোচ বলেছেন, এই ঘটনা। :) তবুও, এই দৃষ্টিকোণটি 100% সঠিক থেকে অনেক দূরে, এবং আমরা নিজেদেরকে এই বিষয়ে নিশ্চিত করেছি। আমাদের আগের উদাহরণে, LinkedList ছিল 400 (!) গুণ দ্রুত। আরেকটি বিষয় হল যে সত্যিই কিছু পরিস্থিতিতে রয়েছে যেখানে লিঙ্কডলিস্ট সেরা পছন্দ। কিন্তু তারা বিদ্যমান, এবং সঠিক মুহূর্তে LinkedListআপনাকে সুন্দরভাবে পুরস্কৃত করতে পারে। পাঠের শুরুতে আমরা যা বলেছিলাম তা ভুলে যাবেন না: বিভিন্ন কাজের জন্য সবচেয়ে দক্ষ ডেটা স্ট্রাকচার আলাদা। আপনি আপনার টাস্কের সমস্ত শর্ত না জানা পর্যন্ত কোন ডেটা স্ট্রাকচার সেরা হবে তা 100% নিশ্চিত হওয়া অসম্ভব। আপনি পরে এই সংগ্রহগুলি সম্পর্কে আরও জানতে পারবেন, যা পছন্দটিকে আরও সহজ করে তুলবে৷ তবে সবচেয়ে সহজ এবং সবচেয়ে কার্যকর বিকল্পটি সর্বদা একই: আপনার প্রোগ্রামে ব্যবহৃত প্রকৃত ডেটা উভয়ই চেষ্টা করুন। তারপরে আপনি নিজের জন্য দেখতে সক্ষম হবেন যে উভয় প্রকারের তালিকা কীভাবে কাজ করে এবং আপনি অবশ্যই ভুল করবেন না। :) আপনি যা শিখেছেন তা শক্তিশালী করার জন্য, আমরা আপনাকে আমাদের জাভা কোর্স থেকে একটি ভিডিও পাঠ দেখার পরামর্শ দিই