Java मध्ये लिंक्ड लिस्ट डेटा स्ट्रक्चर

वेगवेगळ्या उद्देशांसाठी वेगवेगळ्या डेटा स्ट्रक्चर्स तयार केल्या जातात. तुम्हाला ArrayList बद्दल माहिती असेल (अजूनही नसल्यास, आम्ही तुम्हाला त्याबद्दल आधी वाचण्याची शिफारस करतो). या लेखात, आपण LinkedList बद्दल जाणून घेणार आहोत आणि हे संकलन कशासाठी चांगले आहे हे जाणून घेणार आहोत. तुम्ही 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 ही द्वि-मार्गी रांग आहे आणि ती दोन्ही बाजूंनी घटक जोडणे आणि काढून टाकण्यास समर्थन देते. स्टॅक आणि रांगेचे संयोजन म्हणून तुम्ही याचा विचार करू शकता. तर, LinkedList ही या दोघांची अंमलबजावणी आहे आणि ती आम्हाला null सह कोणत्याही ऑब्जेक्ट्सची द्विदिशात्मक रांग तयार करण्यास अनुमती देते. लिंक्डलिस्टघटकांचा संग्रह आहे. आम्ही ते वर्गाच्या कोड स्त्रोतामध्ये पाहू शकतो, यावेळी फील्डकडे लक्ष द्या:

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

प्रत्येक घटक, ज्याला आपण सहसा नोड म्हणतो , त्यात एक ऑब्जेक्ट असतो आणि दोन शेजारच्या वस्तूंचा संदर्भ असतो - मागील आणि पुढील. त्यामुळे मेमरी वापरण्याच्या दृष्टीने ते फारसे प्रभावी नाही. LinkedList ही एक द्विदिश रचना असल्यामुळे , आम्ही दोन्ही बाजूंनी घटक सहज जोडू किंवा काढू शकतो.

LinkedList Constructors

कोड स्त्रोताकडे परत, आम्ही शोधू शकतो की LinkedList मध्ये दोन कन्स्ट्रक्टर आहेत

• पॅरामीटर्सशिवाय LinkedList() रिकामी यादी तयार करण्यासाठी वापरली जाते.
• >LinkedList(संग्रह<? extensions E> c) निर्दिष्ट संग्रहातील घटक असलेली सूची तयार करण्यासाठी आहे, क्रमाने, ते संग्रहाच्या पुनरावृत्तीद्वारे परत केले जातात.

लिंक्डलिस्ट घोषणा

खरं तर, लिंक केलेल्या सूचीमध्ये (जावा किंवा इतर कोणत्याही भाषेत) नोड्सचा क्रम असतो. प्रत्येक नोड तयार करताना परिभाषित केलेल्या प्रकारातील ऑब्जेक्ट संग्रहित करण्यासाठी डिझाइन केलेले आहे. तर LinkedList तयार करण्यासाठी , Java कोड पुढील आहे:

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

पूर्णांकांचा क्रम आणि शेजारी लिंक ठेवण्यासाठी आम्हाला एक ऑब्जेक्ट मिळाला आहे. मात्र, सध्या ते रिकामे आहे.

लिंक्डलिस्ट मुख्य ऑपरेशन्स

नेहमीप्रमाणे, कलेक्शन्सच्या बाबतीत तुम्ही LinkedList मध्ये घटक टाकू शकता (त्याच्या शेवटी किंवा मध्यभागी), तेथून काढून टाका आणि अनुक्रमणिकेनुसार एक घटक मिळवा. तर ते येथे आहेत:

• add(E घटक) या सूचीच्या शेवटी निर्दिष्ट घटक जोडते;
• add(int index, E element) निर्दिष्‍ट पोझिशन इंडेक्सवर घटक घालतो ;
• get(int index) या सूचीतील निर्दिष्ट स्थानावर घटक परत करते;
• remove(int index) पोझिशन इंडेक्सवर असलेला घटक काढून टाकतो;
• रिमूव्ह (ऑब्जेक्ट ओ) ची पहिली घटना काढून टाकते? o या सूचीतील घटक तेथे असल्यास.
• remove() सूचीतील पहिला घटक पुनर्प्राप्त करतो आणि काढून टाकतो.

Java मध्ये लिंक्ड सूची अंमलबजावणी, घटक जोडणे आणि काढून टाकणे. उदाहरण

चला या ऑपरेशन्सचा सराव करून पाहू या. प्रथम, Java LinkedList अंमलबजावणी: स्ट्रिंग्सची LinkedList तयार करणे, तेथे 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 . आणखीही, इटरेटरसह ऑपरेशन्स लिंक्डलिस्ट क्लासचे मुख्य फायदे देतात: इन्सर्ट/डिलीट ऑपरेशन्सची चांगली कामगिरी. इटरेटर वापरून तुम्हाला त्यांच्यासाठी सतत वेळ मिळू शकतो. या लेखात नंतर, आम्ही ArrayList आणि LinkedList+Iterator ची तुलना करण्यासाठी एक कोड उदाहरण लिहू

• Iterator.remove() या पुनरावृत्तीने परत केलेला शेवटचा घटक काढून टाकतो.
• ListIterator.add(E घटक) सूचीमध्ये एक घटक समाविष्ट करते

Java LinkedList उदाहरण: Iterator कसे कार्य करते

येथे आमच्याकडे एक छोटा Java LinkedList उदाहरण कोड आहे, जेथे आम्ही Iterator द्वारे जोडण्याचा आणि हटवण्याचा प्रयत्न करतो.

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]

अधिक Java LinkedList ऑपरेशन्स:

• addFirst() , addLast() सूचीच्या सुरूवातीस/शेवटमध्ये एक घटक जोडा
• clear() सूचीमधून सर्व घटक काढून टाकते
• समाविष्ट (ऑब्जेक्ट o) सूचीमध्ये o घटक असल्यास सत्य परत येतो.
• indexOf(Object o) o घटकाच्या पहिल्या घटनेची अनुक्रमणिका किंवा -1 सूचीमध्ये नसल्यास.
• सेट(इंट इंडेक्स, ई एलिमेंट) इंडेक्स पोझिशनवरील एलिमेंटला एलिमेंटने बदलतो
• आकार() सूचीमधील घटकांचे प्रमाण मिळवते.
• toArray() पहिल्यापासून शेवटच्या घटकापर्यंत सूचीतील सर्व घटक असलेली अॅरे मिळवते.

BTW ही दोन-आकाराची रांग असल्याने, Java मधील LinkedList मध्ये विशिष्ट ऑपरेशन्स स्टॅक आहेत:

• pop() जो स्टॅकमधून एक घटक पॉप करतो (सूचीद्वारे दर्शविला जातो)
• पुश(ई ई) जो घटक स्टॅकवर ढकलतो (या सूचीद्वारे प्रस्तुत)

LinkedList कसे उलटवायचे: उदाहरण

येथे एक लहान उदाहरण आहे, एक लोकप्रिय, तरीही नवशिक्यांसाठी सोपे काम. आमच्याकडे लिंक्डलिस्ट आहे आणि ती उलट केली पाहिजे. सर्वात सोपा अल्गोरिदम म्हणजे LinkedList मधून उलट क्रमाने जाणे आणि प्रत्येक घटक नवीनमध्ये ठेवणे. तथापि, कदाचित तुम्हाला एक चांगला मार्ग सापडेल? रिव्हर्स लिंक्ड लिस्ट जावा प्रोग्रामचा कोड येथे आहे:

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]

LinkedList vs ArrayList: पहिली कधी वापरायची

LinkedList आणि ArrayList दोन्ही लिस्ट इंटरफेसची अंमलबजावणी आहेत . LinkedList ते दुप्पट-लिंक केलेल्या सूचीसह लागू करते. अॅरेलिस्ट डायनॅमिकली रिसाइजिंग अॅरे वापरून त्याची अंमलबजावणी करते. तुम्हाला आधीच माहित आहे की, LinkedList च्या प्रत्येक नोडमध्ये ऑब्जेक्ट्स आणि शेजारी दोन संदर्भ असतात. याचा अर्थ Java LinkedList च्या बाबतीत घटकांमधील संदर्भ संचयित करण्यासाठी अतिरिक्त मेमरी खर्च . अॅरेलिस्ट डायनॅमिकली रिसाइजिंग अॅरेसह त्याची अंमलबजावणी करते. काही LinkedList आणि ArrayList ऑपरेशन्स सारख्या दिसतात, परंतु ते वेगळ्या प्रकारे कार्य करतात. ArrayList मध्येबाबतीत, तुम्ही अंतर्गत अॅरेसह हाताळणी करता, LinkedList मध्ये — संदर्भांसह. ArrayList ही सर्वात लोकप्रिय यादी अंमलबजावणी आहे. जेव्हा ही ऑपरेशन्स सतत वेळेत केली जातात तेव्हा अनुक्रमणिका प्रवेशास प्राधान्य असते तेव्हा तुम्ही निश्चितपणे ArrayList वापरावे . सरासरी यादीच्या शेवटी जोडणे देखील सतत वेळेत केले जाते. आणखीही, अॅरेलिस्टमध्ये घटकांचा समूह संचयित करण्यासाठी अतिरिक्त खर्च नाही. तुम्‍ही अंतर्भूत आणि काढून टाकण्‍याचा वेग सूचीच्‍या शेवटी पूर्ण न केल्‍यावर ते बाधक म्हणून मोजू शकता. लिंक्डलिस्टकाही मार्गांनी ऑपरेशन्स टाकणे आणि हटवणे या बाबतीत अधिक उपयुक्त आहे: जर तुम्ही पुनरावृत्ती वापरत असाल तर ते सतत घडते. अनुक्रमणिकेद्वारे प्रवेश ऑपरेशन्स इच्छित घटकाच्या शेवटच्या सुरुवातीपासून (जे जवळ असेल) शोधून केले जातात. तथापि, घटकांमधील संदर्भ संचयित करण्यासाठी अतिरिक्त खर्चाबद्दल विसरू नका. म्हणून येथे अल्गोरिदमिक रनटाइमसह मानक LinkedList आणि ArrayList ऑपरेशन्स. N हा सूचीमध्ये आधीपासून असलेल्या आयटमच्या संख्येचा संदर्भ देतो. O(N) चा अर्थ असा आहे की सर्वात वाईट स्थितीत आवश्यक स्थान मिळेपर्यंत आपण संपूर्ण सूचीमधून "चालणे" पाहिजे, उदाहरणार्थ, सूचीमध्ये नवीन घटक समाविष्ट करण्यासाठी. O(1)याचा अर्थ असा की ऑपरेशन सतत वेळेत होते, स्वतंत्रपणे आयटमच्या संख्येवर.

लिंक्डलिस्ट वेळ जटिलता

ArrayList वेळ जटिलता

LinkedList कधी वापरायचे: उदाहरण

निश्चितपणे, ArrayList ही सर्वात लोकप्रिय यादी अंमलबजावणी आहे. तथापि, जेव्हा अॅड/रिमूव्ह ऑपरेशन्सची खूप वेळा आवश्यकता असते तेव्हा तुम्ही परिस्थितीला सामोरे जाऊ शकता. अशावेळी, Iterator सह LinkedList फायदेशीर ठरू शकते. येथे एक उदाहरण आहे. आमच्याकडे एक लांबलचक यादी आहे आणि आम्ही या सूचीतील प्रत्येक घटक हटवला पाहिजे. हे कार्य 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

LinkedList साठी परिणाम:

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

आपण या प्रकरणात पाहू शकता की LinkedList मार्ग अधिक प्रभावी आहे. चला प्रामाणिक असू द्या. वास्तविक सॉफ्टवेअर डेव्हलपमेंटमध्ये LinkedList चा वापर ही एक प्रकारची दुर्मिळ घटना आहे. तरीही, एखाद्या व्यावसायिकाला या डेटा स्ट्रक्चरचे अस्तित्व आणि त्याचे फायदे याबद्दल माहिती असणे आवश्यक आहे. रिअल कोडमध्ये LinkedList एक दुर्मिळ अतिथी असल्यास, Java Junior मुलाखतींवर ते खूप लोकप्रिय आहे. आणि तरीही, लिंक्डलिस्टबद्दल जोशुआ ब्लोचने लिहिले ते येथे आहे :

अॅडऑन: सिंगली लिंक्ड लिस्ट जावा

जावामधील शास्त्रीय संग्रहामध्ये सिंगली लिंक्ड लिस्ट नाही , सिंगली लिंक्ड लिस्ट ही अशी रचना आहे जिथे प्रत्येक नोडमध्ये एक ऑब्जेक्ट आणि पुढील नोडचा संदर्भ असतो, परंतु मागीलसाठी नाही. Java LinkedList दोन-लिंक केलेली आहे, परंतु कोणीही तुमची स्वतःची डेटा संरचना तयार करण्यासाठी हस्तक्षेप करत नाही, जसे की सिंगली ,कोड>लिंक केलेली सूची. या कार्यांचे निराकरण करण्यासाठी येथे काही चरणे आहेत:

1. दोन गुणधर्मांसह नोड वर्ग तयार करा , डेटा आणि पुढील. पुढे पुढील नोडचा संदर्भ आहे.
2. डोके आणि शेपटी या दोन विशेषतांनी फर्स्टलास्ट क्लास तयार करा .
3. सूचीमध्ये नवीन नोड जोडण्यासाठी add() पद्धत तयार करा . यादी प्रथम रिकामी आहे का ते तपासा ( head == null ). तसे असल्यास, डोके आणि शेपटी नवीन नोडचा संदर्भ घेतात. जर सूची रिकामी नसेल, तर नवीन नोड शेवटी जोडला जाईल, म्हणून शेपटीची पुढील विशेषता जोडलेल्या नोडला संदर्भित करते आणि नवीन नोड सूचीची शेपटी बनते.

तसे तुम्ही व्यायाम म्हणून तुमची स्वतःची LinkedList तयार करण्याचा प्रयत्न करू शकता. तुमच्या शिकण्यात शुभेच्छा.