जावा लिंक्डलिस्ट

नमस्ते! सभी नवीनतम पाठ 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);

   }
}

आउटपुट: [हैलो वर्ल्ड! मेरा नाम अर्ल है, मुझे जावा से प्यार है, मैं कनाडा में रहता हूं] यहां हमारी सूची कैसी दिखती है: आइए देखें कि एक नया तत्व कैसे जोड़ा जाए। यह ऐड () विधि का उपयोग करके किया जाता है।

earlBio.add(str2);

कोड के बिंदु पर, हमारी सूची में एक तत्व होता है: स्ट्रिंग str1 । आइए देखें कि चित्र में आगे क्या होता है: परिणामस्वरूप, str2 और str1 सूची के इस नोड में संग्रहीत अगले और पिछले लिंक के माध्यम से जुड़ जाते हैं : अब आपको एक दोगुनी-लिंक्ड सूची के मुख्य विचार को समझना चाहिए। लिंक की यह श्रृंखला ठीक वही है जो लिंक्डलिस्ट तत्वों को एकल सूची बनाती है। ArrayList के विपरीत , 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(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

जैसा कि आप देख सकते हैं, अतिभारित ऐड () विधि आपको एक नए आइटम के लिए एक विशिष्ट सूचकांक निर्दिष्ट करने देती है। इस स्थिति में, हम str1 और str3 के बीच String 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 लिंक की श्रृंखला से " बाहर हो गया " है और अब सूची का हिस्सा नहीं है।

विधियों का अवलोकन

LinkedList में ArrayList के साथ बहुत सी विधियाँ हैं । उदाहरण के लिए, दोनों वर्गों में ऐड () , रिमूव () , इंडेक्सऑफ () , क्लियर () , शामिल () (इंगित करता है कि कोई आइटम सूची में है), सेट () (मौजूदा तत्व को प्रतिस्थापित करता है) जैसे तरीके हैं। आकार () । हालाँकि उनमें से कई अलग-अलग आंतरिक रूप से काम करते हैं (जैसा कि हमने ऐड () और रिमूव () के साथ पाया ), अंतिम परिणाम समान है। हालाँकि, LinkedList के पास सूची की शुरुआत और अंत के साथ काम करने के लिए अलग-अलग तरीके हैं, जो 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 + '\'' +
               '}';
   }
}

आउटपुट: [कार {मॉडल = 'फेरारी 360 स्पाइडर'}, कार {मॉडल = 'बुगाटी वेरॉन'}, कार {मॉडल = 'लेम्बोर्गिनी डियाब्लो'}] [कार {मॉडल = 'फोर्ड मोंडो'}, कार {मॉडल = ' फेरारी 360 स्पाइडर'}, कार {मॉडल = 'बुगाटी वेरॉन'}, कार {मॉडल = 'लेम्बोर्गिनी डियाब्लो'}, कार {मॉडल = 'फिएट डुकाटो'}] हम सूची के शीर्ष पर "फोर्ड" के साथ समाप्त होते हैं , और अंत में "फिएट"।

• 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());
}

आउटपुट: कार {मॉडल = 'फेरारी 360 स्पाइडर'} कार {मॉडल = 'लेम्बोर्गिनी डियाब्लो'}

• पोलफर्स्ट () , पोललास्ट () : ये विधियाँ सूची में पहला / अंतिम तत्व लौटाती हैं और इसे सूची से हटा देती हैं। सूची खाली होने पर वे शून्य हो जाते हैं

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);
}

आउटपुट: कार {मॉडल = 'फेरारी 360 स्पाइडर'} कार {मॉडल = 'लेम्बोर्गिनी डियाब्लो'} सूची में क्या बचा है? [कार {मॉडल = 'बुगाटी वेरॉन'}]

• 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 स्पाइडर'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] अब हम जानते हैं कि LinkedList कैसे काम करता है और इसका संगठन ArrayList से कैसे अलग है । लिंक्डलिस्ट का उपयोग करने के क्या फायदे हैं ? इन सबसे ऊपर, सूची के मध्य में काम करने पर हमें लाभ होता है। LinkedList के बीच में सम्मिलन और निष्कासन ऑपरेशन ArrayList की तुलना में बहुत सरल हैं । हम केवल पड़ोसी तत्वों के लिंक को अपडेट करते हैं, और लिंक की श्रृंखला से अवांछित तत्व "ड्रॉप आउट" हो जाता है। लेकिन एक ArrayList में , हमें अवश्य करना चाहिए

• जांचें कि क्या पर्याप्त जगह है (डालते समय)
• यदि नहीं, तो हम एक नया ऐरे बनाते हैं और वहां डेटा कॉपी करते हैं (डालते समय)
• हम तत्व को हटाते/डालते हैं, और अन्य सभी तत्वों को दाएं/बाएं (ऑपरेशन के प्रकार के आधार पर) ले जाते हैं। और इस प्रक्रिया की जटिलता सूची के आकार पर बहुत अधिक निर्भर करती है। 10 तत्वों को कॉपी/स्थानांतरित करना एक बात है, और एक लाख तत्वों के साथ ऐसा करना दूसरी बात है।

दूसरे शब्दों में, यदि आपके प्रोग्राम में सूची के मध्य में सम्मिलन/हटाने का संचालन सबसे आम है, तो LinkedList 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));
   }
}

आउटपुट: लिंक्डलिस्ट द्वारा लिया गया समय (मिलीसेकंड में) = 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 तत्व। ArrayList को हर सम्मिलन के साथ कुछ मिलियन आइटम स्थानांतरित करने थे! यह कैसे जीत गया? सबसे पहले, तत्वों तक पहुँचने के लिए ArrayList के लिए आवश्यक समय निश्चित (स्थिर) है। जब आप लिखते हैं

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। next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.… परिणामस्वरूप, सूची के मध्य में प्रत्येक प्रविष्टि (हटाने) के दौरान , ArrayList को एक्सेस करने के लिए सटीक मेमोरी पता पहले से ही पता है, लेकिन LinkedList को अभी भी "वहां पहुंचने" की आवश्यकता है। दूसरा, 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 सबसे अच्छा विकल्प है। लेकिन वे मौजूद हैं, और सही समय पर LinkedListआपको अच्छा इनाम दे सकता है। यह न भूलें कि हमने पाठ की शुरुआत में क्या कहा था: अलग-अलग कार्यों के लिए सबसे कुशल डेटा संरचनाएं अलग-अलग होती हैं। यह 100% सुनिश्चित होना असंभव है कि कौन सी डेटा संरचना तब तक सर्वोत्तम होगी जब तक आप अपने कार्य की सभी शर्तों को नहीं जानते। आप बाद में इन संग्रहों के बारे में अधिक जानेंगे, जिससे चुनाव करना आसान हो जाएगा। लेकिन सबसे सरल और सबसे प्रभावी विकल्प हमेशा एक जैसा होता है: अपने प्रोग्राम में उपयोग किए गए वास्तविक डेटा दोनों पर प्रयास करें। तब आप स्वयं देख पाएंगे कि दोनों प्रकार की सूचियाँ कैसा प्रदर्शन करती हैं और आप निश्चित रूप से गलत नहीं होंगे। :) आपने जो सीखा है उसे सुदृढ़ करने के लिए, हमारा सुझाव है कि आप हमारे जावा कोर्स से एक वीडियो सबक देखें