জাভাতে লিঙ্কড তালিকা ডেটা স্ট্রাকচার

বিভিন্ন উদ্দেশ্যে বিভিন্ন ডেটা স্ট্রাকচার তৈরি করা হয়। আপনি ArrayList সম্পর্কে জানতে পারেন (যদি এখনও না হয়, আমরা আপনাকে প্রথমে এটি সম্পর্কে পড়ার পরামর্শ দিই)। এই নিবন্ধে, আমরা লিঙ্কডলিস্ট সম্পর্কে শিখতে যাচ্ছি এবং বুঝতে যাচ্ছি যে এই সংগ্রহটি কীসের জন্য ভাল। আপনি যদি LinkedList Java 8 (বা ভাষার পরবর্তী সংস্করণ) ক্লাস কোড সোর্স (Oracle ওয়েবসাইটে বা আপনার IDE-তে, IDEA: ক্লাসের নামের উপর crtl+B এর ক্ষেত্রে) দেখেন তাহলে আপনি পরবর্তী ঘোষণা দেখতে পাবেন:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

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

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

প্রতিটি উপাদান, সাধারণত আমরা একে নোড বলে থাকি , একটি বস্তু থাকে এবং দুটি প্রতিবেশী বস্তুর উল্লেখ থাকে - পূর্ববর্তী এবং পরবর্তী। অতএব, মেমরি ব্যবহারের ক্ষেত্রে এটি খুব কার্যকর নয়। যেহেতু LinkedList আসলে একটি দ্বিমুখী কাঠামো, আমরা সহজেই উভয় দিক থেকে উপাদান যোগ করতে বা অপসারণ করতে পারি।

LinkedList Constructors

কোড উত্সে ফিরে, আমরা জানতে পারি যে লিঙ্কডলিস্টের দুটি কনস্ট্রাক্টর রয়েছে

• লিঙ্কডলিস্ট() প্যারামিটার ছাড়াই একটি খালি তালিকা তৈরি করতে ব্যবহৃত হয়।
• >LinkedList(সংগ্রহ<? extensions E> c) হল নির্দিষ্ট সংগ্রহের উপাদান সমন্বিত একটি তালিকা তৈরি করার জন্য, ক্রমানুসারে, সেগুলি সংগ্রহের পুনরাবৃত্তিকারী দ্বারা ফেরত দেওয়া হয়।

লিঙ্কডলিস্ট ঘোষণা

প্রকৃতপক্ষে, একটি লিঙ্ক করা তালিকা (জাভা বা অন্য কোনো ভাষায়) নোডের একটি ক্রম নিয়ে গঠিত। প্রতিটি নোড তৈরি করার সময় সংজ্ঞায়িত ধরনের একটি বস্তু সংরক্ষণ করার জন্য ডিজাইন করা হয়েছে। তাই লিঙ্কডলিস্ট তৈরি করতে , জাভা কোডটি পরবর্তী:

LinkedList<Integer> myList = new LinkedList<>();

আমরা প্রতিবেশীদের সাথে পূর্ণসংখ্যা এবং লিঙ্কগুলির একটি ক্রম রাখার জন্য একটি বস্তু পেয়েছি। তবে এই মুহূর্তে তা খালি।

লিঙ্কডলিস্ট প্রধান অপারেশন

যথারীতি, সংগ্রহের ক্ষেত্রে আপনি উপাদানগুলিকে লিঙ্কডলিস্টে রাখতে পারেন (এর শেষে বা মাঝখানে), সেখান থেকে সরান এবং সূচী অনুসারে একটি উপাদান পেতে পারেন। তাই তারা এখানে:

• add(E element) এই তালিকার শেষে নির্দিষ্ট উপাদান যুক্ত করে;
• add(int index, E element) নির্দিষ্ট অবস্থানের সূচকে এলিমেন্ট সন্নিবেশ করায় ;
• get(int index) এই তালিকার নির্দিষ্ট অবস্থানে উপাদান প্রদান করে;
• remove(int index) অবস্থান সূচকে থাকা উপাদানটিকে সরিয়ে দেয়;
• রিমুভ (অবজেক্ট o) এর প্রথম ঘটনাটি সরিয়ে দেয়? এই তালিকা থেকে o উপাদান যদি এটি আছে.
• remove() পুনরুদ্ধার করে এবং তালিকার প্রথম উপাদানটি সরিয়ে দেয়।

জাভাতে লিঙ্কযুক্ত তালিকা বাস্তবায়ন, উপাদান যোগ করা এবং অপসারণ করা। উদাহরণ

আসুন অনুশীলনে এই অপারেশনগুলি চেষ্টা করে দেখি। প্রথম, জাভা লিঙ্কডলিস্ট বাস্তবায়ন: স্ট্রিংগুলির একটি লিঙ্কডলিস্ট তৈরি করা, সেখানে 3টি উপাদান যোগ করা। তারপর একটি সরান, তারপর মাঝখানে একটি যোগ করুন.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

এই প্রোগ্রাম চালানোর ফলাফল:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

একটি লিঙ্কডলিস্ট হল কালেকশন ফ্রেমওয়ার্কের একটি অংশ , আপনি উপাদানগুলি সরাতে ইটারেটর ব্যবহার করতে পারেন, সেইসাথে তালিকাগুলির জন্য একটি বিশেষ পুনরাবৃত্তিকারী — ListIterator । আরও বেশি, ইটারেটরের সাথে ক্রিয়াকলাপগুলি লিঙ্কডলিস্ট ক্লাসের প্রধান সুবিধাগুলি প্রদান করে : সন্নিবেশ/মুছুন অপারেশনগুলির ভাল পারফরম্যান্স। Iterator ব্যবহার করে আপনি তাদের জন্য একটি ধ্রুবক সময় পেতে পারেন। পরে এই নিবন্ধে, আমরা ArrayList এবং LinkedList+Iterator তুলনা করার জন্য একটি কোড উদাহরণ লিখব

• Iterator.remove() এই পুনরাবৃত্তিকারীর দ্বারা ফিরে আসা শেষ উপাদানটি সরিয়ে দেয়।
• ListIterator.add(E উপাদান) তালিকায় একটি উপাদান সন্নিবেশ করায়

জাভা লিঙ্কডলিস্ট উদাহরণ: কিভাবে ইটারেটর কাজ করে

এখানে আমাদের কাছে একটি ছোট জাভা লিঙ্কডলিস্ট উদাহরণ কোড রয়েছে, যেখানে আমরা ইটারেটরের মাধ্যমে যোগ এবং মুছে ফেলার চেষ্টা করি।

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);

       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);

   }
}

এই প্রোগ্রাম চালানোর ফলাফল:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

আরও জাভা লিঙ্কডলিস্ট অপারেশন:

• addFirst() , addLast() একটি তালিকার শুরু/শেষে একটি উপাদান যোগ করুন
• clear() তালিকা থেকে সমস্ত উপাদান সরিয়ে দেয়
• contains(Object o) ট্রু রিটার্ন করে যদি তালিকায় o উপাদান থাকে।
• indexOf(Object o) o উপাদানটির প্রথম উপস্থিতির সূচী প্রদান করে, অথবা -1 যদি তালিকায় না থাকে।
• set(int index, E element) সূচী অবস্থানে থাকা এলিমেন্টকে এলিমেন্ট দিয়ে প্রতিস্থাপন করে
• size() তালিকায় উপাদানের পরিমাণ প্রদান করে।
• toArray() প্রথম থেকে শেষ উপাদান পর্যন্ত তালিকার সমস্ত উপাদান ধারণকারী একটি অ্যারে প্রদান করে।

BTW একটি দ্বি-আকারের সারি হওয়ায়, জাভাতে লিঙ্কডলিস্টে নির্দিষ্ট ক্রিয়াকলাপগুলি স্ট্যাক রয়েছে:

• pop() যা স্ট্যাক থেকে একটি উপাদান পপ করে (তালিকা দ্বারা উপস্থাপিত)
• পুশ(ই ই) যা একটি উপাদানকে স্ট্যাকের উপর ঠেলে দেয় (এই তালিকা দ্বারা উপস্থাপিত)

লিঙ্কডলিস্টকে কীভাবে বিপরীত করবেন: উদাহরণ

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

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

ফলাফল:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

লিঙ্কডলিস্ট বনাম অ্যারেলিস্ট: প্রথমটি কখন ব্যবহার করবেন

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

লিঙ্কডলিস্ট সময় জটিলতা

ArrayList সময় জটিলতা

লিঙ্কডলিস্ট কখন ব্যবহার করবেন: উদাহরণ

অবশ্যই, ArrayList হল সবচেয়ে জনপ্রিয় তালিকা বাস্তবায়ন। যাইহোক, আপনি পরিস্থিতিগুলি পূরণ করতে পারেন, যখন অ্যাড/রিমুভ অপারেশনগুলি প্রায়শই প্রয়োজন হয়। সেক্ষেত্রে, লিংকডলিস্ট একসাথে ইটারেটরের সাথে উপকারী হতে পারে। এখানে একটি উদাহরণ. আমরা একটি দীর্ঘ তালিকা পেয়েছি, এবং আমাদের এই তালিকা থেকে প্রতিটি উপাদান মুছে ফেলা উচিত। আসুন ArrayList এবং LinkedList + Iterator দিয়ে এই কাজটি করি । আমরা প্রতিটি অপারেশনের সময় তুলনা করি এবং কনসোলে এটি মুদ্রণ করি। এখানে কোড:

import java.util.*;
import java.util.function.BiPredicate;

public class ListTest2 {

   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());

       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }

   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);

           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }

   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }

   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

ArrayList এর জন্য ফলাফল:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

লিঙ্কডলিস্টের ফলাফল:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

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

অ্যাডঅন: এককভাবে লিঙ্কযুক্ত তালিকা জাভা

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

1. দুটি বৈশিষ্ট্য, ডেটা এবং পরবর্তী সহ একটি নোড ক্লাস তৈরি করুন। পরবর্তী পরবর্তী নোড একটি রেফারেন্স.
2. দুটি বৈশিষ্ট্য, মাথা এবং পুচ্ছ দিয়ে ফার্স্টলাস্ট ক্লাস তৈরি করুন ।
3. তালিকায় একটি নতুন নোড যোগ করতে একটি add() পদ্ধতি তৈরি করুন। তালিকাটি প্রথমে খালি কিনা তা পরীক্ষা করুন ( head == null )। যদি তাই হয়, মাথা এবং পুচ্ছ নতুন নোড উল্লেখ করুন. তালিকাটি খালি না থাকলে, নতুন নোডটি শেষে যোগ করা হবে, তাই টেলের পরবর্তী বৈশিষ্ট্যটি যোগ করা নোডকে বোঝায় এবং নতুন নোডটি তালিকার পুচ্ছ হয়ে যায়।

যাইহোক আপনি একটি ব্যায়াম হিসাবে আপনার নিজের লিঙ্কডলিস্ট তৈরি করার চেষ্টা করতে পারেন। আপনার শেখার সৌভাগ্য.