Java LinkedList

हाय! सर्व नवीनतम धडे ArrayList ला समर्पित केले गेले आहेत . ही डेटा रचना अतिशय सोयीस्कर आणि उपयुक्त आहे. ते बरीच कामे हाताळू शकते. पण Java मध्ये इतर अनेक डेटा स्ट्रक्चर्स आहेत. का? सर्वात महत्त्वाचे म्हणजे, कार्यांची श्रेणी प्रचंड आहे आणि विविध कार्यांसाठी सर्वात कार्यक्षम डेटा संरचना भिन्न आहेत. आज आपण एक नवीन रचना भेटू: Java 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(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);

   }
}

तुम्ही बघू शकता, ओव्हरलोड केलेली add() पद्धत तुम्हाला नवीन आयटमसाठी विशिष्ट निर्देशांक निर्दिष्ट करू देते. या प्रकरणात, आम्हाला 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 च्या बर्‍याच पद्धती सामाईक आहेत . उदाहरणार्थ, दोन्ही वर्गांमध्ये add() , remove() , indexOf() , clear() , contains() (एखादी आयटम सूचीमध्ये आहे की नाही हे दर्शवते), सेट() (विद्यमान घटक पुनर्स्थित करते) आणि आकार( ) जरी त्यांपैकी बरेच जण आंतरिकरित्या वेगळ्या पद्धतीने कार्य करतात (जसे आम्हाला add() आणि remove() सह आढळले आहे ), अंतिम परिणाम समान आहे. तथापि, 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 स्पायडर'}, कार{मॉडेल='बुगाटी वेरॉन'}, कार{मॉडेल='लॅम्बोर्गिनी डायब्लो'}] [कार{मॉडेल='फोर्ड मॉन्डिओ'}, कार{मॉडेल=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] आम्ही सूचीच्या शीर्षस्थानी "फोर्ड" सह संपतो , आणि शेवटी "फियाट".

• 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 स्पायडर'} कार{मॉडेल='लॅम्बोर्गिनी डायब्लो'}

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

आउटपुट: कार{model='Ferrari 360 Spider'} कार{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 पेक्षा LinkedList च्या मध्यभागी समाविष्ट करणे आणि काढणे ऑपरेशन्स खूप सोपे आहेत . आम्ही फक्त शेजारच्या घटकांचे दुवे अद्यतनित करतो आणि अवांछित घटक लिंकच्या साखळीतून "ड्रॉप आउट" करतो. पण एक 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));
   }
}

आउटपुट: 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 ते अनपेक्षित होते! आम्ही एक ऑपरेशन केले जेथे LinkedList अधिक कार्यक्षम असावे: सूचीच्या मध्यभागी 100 आयटम समाविष्ट करणे. आणि आमची यादी मोठी आहे: 5,000,000 घटक. ArrayList ला प्रत्येक इन्सर्शनसह काही दशलक्ष आयटम हलवावे लागले! ते कसे जिंकले? प्रथम, घटकांमध्ये प्रवेश करण्यासाठी ArrayList ला लागणारा वेळ निश्चित (स्थिर) आहे. तुम्ही लिहिता तेव्हा

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

मग ArrayList [2_000_000] हा एक विशिष्ट मेमरी पत्ता आहे (तरीही, सूचीमध्ये अंतर्गत अॅरे आहे). परंतु, लिंक्डलिस्टमध्ये अॅरे नसते. ते लिंक्सच्या साखळीसह घटक क्रमांक 2_000_000 शोधेल. LinkedList साठी, हा मेमरी पत्ता नाही, परंतु एक लिंक आहे ज्यावर पोहोचणे आवश्यक आहे: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. नेक्स्ट.नेक्स्ट.नेक्स्ट.नेक्स्ट.नेक्स्ट.नेक्स्ट.नेक्स्ट.नेक्स्ट.नेक्स्ट _ , ArrayList ला आधीच प्रवेश करण्यासाठी अचूक मेमरी पत्ता माहित आहे, परंतु LinkedList ला अजूनही "तेथे पोहोचणे" आवश्यक आहे. दुसरे, ArrayList ची रचना आहेस्वतः. एक विशेष अंतर्गत फंक्शन ( System.arrayCopy() ) अंतर्गत अॅरे विस्तृत करते आणि सर्व घटक कॉपी आणि शिफ्ट करते. हे खूप वेगवान आहे, कारण ते या विशिष्ट कार्यासाठी ऑप्टिमाइझ केलेले आहे. परंतु जेव्हा तुम्हाला एखाद्या विशिष्ट निर्देशांकावर जाण्याची गरज नसते, तेव्हा LinkedList हा विजेता असतो. समजा आपण यादीच्या अगदी सुरुवातीलाच टाकतो. तेथे दशलक्ष घटक घालण्याचा प्रयत्न करूया:

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 सेकंदात केले! लिंक्डलिस्टचा येथे फायदा झाला, कारण प्रत्येक वेळी सूचीच्या मध्यभागी असलेल्या लिंक्सच्या साखळीतून धावावे लागत नाही. ते सूचीच्या सुरुवातीला आवश्यक निर्देशांक शोधते, म्हणून भिन्न अल्गोरिदम आधीपासूनच एक फायदा आहे. :) खरं तर, " ArayList विरुद्ध LinkedList " चर्चा खूप व्यापक आहे, आणि सध्याच्या पातळीवर आम्ही त्यात खोलवर जाणार नाही. आपल्याला लक्षात ठेवण्याची आवश्यकता असलेली मुख्य गोष्ट अशी आहे:

• सर्व सैद्धांतिक फायदे कोणतेही विशिष्ट संग्रह नेहमीच वास्तवात कार्य करत नाहीत (आम्ही हे सूचीच्या मध्यभागी असलेल्या उदाहरणासह पाहिले)
• संग्रह निवडताना टोकाची स्थिती स्वीकारू नका (" अॅरेलिस्ट नेहमीच वेगवान असते. ती वापरा आणि तुम्ही चुकीचे होऊ शकत नाही. बर्याच काळापासून कोणीही LinkedList वापरत नाही").

जरी LinkedList चे लेखक, Joshua Bloch म्हणतात की हे प्रकरण आहे. :) तरीही, हा दृष्टीकोन 100% बरोबर नाही आणि आम्ही स्वतःला याची खात्री पटवून दिली आहे. आमच्या मागील उदाहरणात, LinkedList 400 (!) पट वेगवान होते. दुसरी गोष्ट अशी आहे की खरोखरच काही परिस्थिती आहेत जिथे LinkedList ही सर्वोत्तम निवड आहे. पण ते अस्तित्वात आहेत, आणि योग्य क्षणी LinkedListतुम्हाला छान बक्षीस देऊ शकता. धड्याच्या सुरुवातीला आम्ही काय सांगितले ते विसरू नका: सर्वात कार्यक्षम डेटा संरचना वेगवेगळ्या कार्यांसाठी भिन्न आहेत. जोपर्यंत तुम्हाला तुमच्या कार्याच्या सर्व अटी माहित होत नाहीत तोपर्यंत कोणती डेटा रचना सर्वोत्तम असेल याची 100% खात्री असणे अशक्य आहे. तुम्हाला या संग्रहांबद्दल नंतर अधिक माहिती मिळेल, ज्यामुळे निवड करणे सोपे होईल. परंतु सर्वात सोपा आणि सर्वात प्रभावी पर्याय नेहमी समान असतो: तुमच्या प्रोग्राममध्ये वापरलेल्या वास्तविक डेटावर दोन्ही वापरून पहा. मग दोन्ही प्रकारच्या याद्या कशा प्रकारे कार्य करतात हे तुम्ही स्वतः पाहण्यास सक्षम असाल आणि तुमची नक्कीच चूक होणार नाही. :) तुम्ही जे शिकलात ते बळकट करण्यासाठी, आम्ही तुम्हाला आमच्या Java कोर्समधून व्हिडिओ धडा पाहण्याची शिफारस करतो