जावा में लिंक्ड सूची डेटा संरचना

अलग-अलग उद्देश्यों के लिए अलग-अलग डेटा स्ट्रक्चर बनाए जाते हैं। आप 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

फिलहाल कोड से सबसे महत्वपूर्ण जानकारी यह तथ्य है कि लिंक्डलिस्ट लिस्ट और डेक इंटरफेस को लागू करता है । सूची इंटरफ़ेस आइटम जोड़ने का क्रम रखता है और इंडेक्स द्वारा आइटम तक पहुंच की अनुमति देता है। "साधारण" कतार अंत में तत्वों को जोड़ने और उन्हें शुरुआत से निकालने का समर्थन करती है। Deque एक दो-तरफ़ा कतार है, और यह दोनों ओर से तत्वों को जोड़ने और निकालने का समर्थन करती है। आप इसे स्टैक और कतार के संयोजन के रूप में सोच सकते हैं। तो, लिंक्डलिस्ट इन दोनों का कार्यान्वयन है, और यह हमें एक द्विदिश कतार बनाने की अनुमति देता है जिसमें अशक्त सहित कोई भी वस्तु शामिल है। लिंक्ड सूचीतत्वों का संग्रह है। हम इसे कक्षा के कोड स्रोत में देख सकते हैं, इस बार फ़ील्ड पर ध्यान दें:

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

प्रत्येक तत्व, जिसे हम आमतौर पर नोड कहते हैं , में एक वस्तु और दो पड़ोसी वस्तुओं के संदर्भ होते हैं - पिछले और अगले। इसलिए, यह स्मृति का उपयोग करने के मामले में बहुत प्रभावी नहीं है। जैसा कि लिंक्डलिस्ट वास्तव में एक द्विदिश संरचना है, हम दोनों पक्षों से तत्वों को आसानी से जोड़ या हटा सकते हैं।

लिंक्डलिस्ट कंस्ट्रक्टर्स

कोड स्रोत पर वापस, हम यह पता लगा सकते हैं कि लिंक्डलिस्ट में दो कंस्ट्रक्टर हैं

• LinkedList() पैरामीटर के बिना खाली सूची बनाने के लिए उपयोग किया जाता है।
• >LinkedList(Collection<? extends E> c) निर्दिष्ट संग्रह के तत्वों वाली एक सूची बनाने के लिए है, क्रम में, वे संग्रह के पुनरावर्तक द्वारा लौटाए जाते हैं।

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

वास्तव में, एक लिंक की गई सूची (जावा या किसी अन्य भाषा में) में नोड्स का एक क्रम होता है। प्रत्येक नोड को बनाते समय परिभाषित प्रकार के ऑब्जेक्ट को स्टोर करने के लिए डिज़ाइन किया गया है। तो LinkedList बनाने के लिए , जावा कोड अगला है:

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

हमारे पास पूर्णांकों का क्रम और पड़ोसियों के लिंक रखने के लिए एक वस्तु है। हालांकि, फिलहाल यह खाली है।

लिंक्डलिस्ट मुख्य संचालन

हमेशा की तरह, संग्रह के मामले में आप तत्वों को लिंक्डलिस्ट (इसके अंत में या बीच में) में डाल सकते हैं, वहां से हटा सकते हैं, और सूचकांक द्वारा एक तत्व प्राप्त कर सकते हैं। तो ये रहे:

• जोड़ें (ई तत्व) इस सूची के अंत में निर्दिष्ट तत्व जोड़ता है;
• जोड़ें (इंट इंडेक्स, ई तत्व) तत्व को निर्दिष्ट स्थिति सूचकांक में सम्मिलित करता है ;
• get(int index) इस सूची में निर्दिष्ट स्थान पर तत्व लौटाता है;
• हटाएं (इंट इंडेक्स) उस तत्व को हटा दें जो स्थिति सूचकांक पर है;
• हटाएं (ऑब्जेक्ट ओ) की पहली घटना को हटा दें? इस सूची से ओ तत्व अगर यह है।
• हटाएं() सूची के पहले तत्व को पुनर्प्राप्त और हटा देता है।

जावा में लिंक्ड सूची कार्यान्वयन, तत्वों को जोड़ना और हटाना। उदाहरण

आइए इन ऑपरेशनों को अभ्यास में देखें। सबसे पहले, जावा लिंक्डलिस्ट कार्यान्वयन: स्ट्रिंग्स की एक लिंक्डलिस्ट बनाना, वहां 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]

एक लिंक्डलिस्ट संग्रह ढांचे का एक हिस्सा है , आप तत्वों को हटाने के लिए Iterator का उपयोग कर सकते हैं, साथ ही सूचियों के लिए एक विशेष पुनरावर्तक - ListIterator । इससे भी अधिक, इटरेटर के साथ संचालन लिंक्डलिस्ट वर्ग के मुख्य लाभ प्रदान करता है : डालने/हटाने के संचालन का अच्छा प्रदर्शन। इटरेटर का उपयोग करके आप उनके लिए निरंतर समय प्राप्त कर सकते हैं। बाद में इस लेख में, हम ArrayList और LinkedList+Iterator की तुलना करने के लिए एक कोड उदाहरण लिखेंगे

• Iterator.remove() इस पुनरावर्तक द्वारा लौटाए गए अंतिम तत्व को हटा देता है।
• ListIterator.add (ई तत्व) सूची में एक तत्व सम्मिलित करता है

जावा लिंक्डलिस्ट उदाहरण: इटरेटर कैसे काम करता है

यहां हमारे पास एक छोटा जावा लिंक्डलिस्ट उदाहरण कोड है, जहां हम इटरेटर के माध्यम से जोड़ने और हटाने का प्रयास करते हैं।

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() सूची के आरंभ/अंत में एक तत्व जोड़ें
• स्पष्ट() सूची से सभी तत्वों को हटा देता है
• सम्‍मिलित है (ऑब्जेक्ट ओ) सच है अगर सूची में ओ तत्व है।
• indexOf(Object o) o तत्व की पहली घटना का सूचकांक लौटाता है, या -1 यदि यह सूची में नहीं है।
• सेट (इंट इंडेक्स, ई एलिमेंट) तत्व को इंडेक्स स्थिति में तत्व के साथ बदल देता है
• आकार () सूची में तत्वों की मात्रा लौटाता है।
• toArray() एक सरणी देता है जिसमें सभी सूची के तत्व पहले से अंतिम तत्व तक होते हैं।

बीटीडब्ल्यू दो आकार की कतार है, जावा में लिंक्डलिस्ट में विशिष्ट संचालन हैं:

• पॉप () जो स्टैक से एक तत्व को पॉप करता है (सूची द्वारा दर्शाया गया है)
• पुश (ई ई) जो एक तत्व को स्टैक पर धकेलता है (इस सूची द्वारा दर्शाया गया है)

लिंक्डलिस्ट को कैसे उलटा करें: उदाहरण

यहाँ एक छोटा सा उदाहरण दिया गया है, जो शुरुआती लोगों के लिए एक लोकप्रिय, फिर भी एक आसान काम है। हमारे पास एक लिंक्डलिस्ट है और इसे उलट देना चाहिए। सबसे आसान एल्गोरिदम लिंक्डलिस्ट को रिवर्स ऑर्डर में जाना है और प्रत्येक तत्व को नए में रखना है। हालाँकि, शायद आपको एक बेहतर तरीका मिल जाएगा? यहाँ रिवर्स लिंक्ड लिस्ट जावा प्रोग्राम का कोड है:

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 और ArrayList दोनों ही List इंटरफ़ेस के कार्यान्वयन हैं । लिंक्डलिस्ट इसे दोगुनी-लिंक्ड सूची के साथ लागू करता है। ArrayList इसे गतिशील रूप से आकार देने वाले सरणी का उपयोग करके लागू करता है। जैसा कि आप पहले से ही जानते हैं, लिंक्डलिस्ट के प्रत्येक नोड में ऑब्जेक्ट्स और पड़ोसियों के दो संदर्भ होते हैं। इसका मतलब है कि जावा लिंक्डलिस्ट के मामले में तत्वों के बीच संदर्भों को संग्रहित करने के लिए अतिरिक्त मेमोरी लागत । ArrayList इसे गतिशील रूप से आकार देने वाले सरणी के साथ लागू करता है। कुछ LinkedList और ArrayList ऑपरेशन एक जैसे दिखते हैं, लेकिन वे अलग तरीके से काम करते हैं। ऐरेलिस्ट मेंमामला, आप लिंक्डलिस्ट में - संदर्भों के साथ , आंतरिक सरणियों के साथ हेरफेर करते हैं । ArrayList सबसे लोकप्रिय सूची कार्यान्वयन है। आपको निश्चित रूप से ऐरेलिस्ट का उपयोग करना चाहिए जब इंडेक्स एक्सेस एक प्राथमिकता है क्योंकि ये ऑपरेशन निरंतर समय में किए जाते हैं। सूची के अंत में औसतन जोड़ना भी निरंतर समय में किया जाता है। इससे भी अधिक, ArrayList के पास तत्वों का एक समूह संग्रहीत करने के लिए अतिरिक्त लागत नहीं है। जब यह सूची के अंत में नहीं किया जाता है तो आप सम्मिलन की गति और संचालन को हटाने के रूप में गिन सकते हैं। लिंक्ड सूचीइन्सर्ट और डिलीट ऑपरेशंस प्रदर्शन के मामले में कुछ मायनों में अधिक उपयोगी है: यदि आप पुनरावृत्तियों का उपयोग करते हैं तो यह निरंतर समय में होता है। इंडेक्स द्वारा एक्सेस ऑपरेशंस वांछित तत्व के अंत की शुरुआत (जो भी करीब हो) से खोज कर किया जाता है। हालाँकि, तत्वों के बीच संदर्भों को संग्रहीत करने के लिए अतिरिक्त लागतों के बारे में मत भूलना। तो यहाँ एल्गोरिथम रनटाइम के साथ मानक लिंक्डलिस्ट और ऐरेलिस्ट ऑपरेशंस। एन उन वस्तुओं की संख्या को संदर्भित करता है जो पहले से ही सूची में हैं। ओ (एन) का अर्थ है कि सबसे खराब स्थिति में हमें पूरी सूची के माध्यम से "चलना" चाहिए जब तक कि आवश्यक स्थान नहीं मिल जाता है, उदाहरण के लिए, सूची में नए तत्व को सम्मिलित करने के लिए। हे (1)इसका मतलब है कि ऑपरेशन निरंतर समय में होता है, स्वतंत्र रूप से वस्तुओं की संख्या पर।

लिंक्डलिस्ट समय जटिलता

ArrayList समय जटिलता

लिंक्डलिस्ट का उपयोग कब करें: उदाहरण

निश्चित रूप से, ArrayList सबसे लोकप्रिय सूची कार्यान्वयन है। हालाँकि, आप उन स्थितियों का सामना कर सकते हैं, जब जोड़ने/निकालने के कार्यों की अक्सर आवश्यकता होती है। उस स्थिति में, LinkedList सभी Iterator के साथ मिलकर लाभकारी हो सकते हैं। यहाँ एक उदाहरण है। हमारे पास एक लंबी सूची है, और हमें इस सूची से प्रत्येक तत्व को हटा देना चाहिए। आइए इस कार्य को 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 अधिक प्रभावी है। हम ईमानदार हो। वास्तविक सॉफ्टवेयर विकास में लिंक्डलिस्ट का उपयोग एक दुर्लभ घटना है। फिर भी, एक पेशेवर को इस डेटा संरचना के अस्तित्व और इसके लाभों के बारे में पता होना चाहिए। यदि वास्तविक कोड में लिंक्डलिस्ट एक दुर्लभ अतिथि है, तो जावा जूनियर साक्षात्कार में यह बहुत लोकप्रिय है। और फिर भी, यहाँ जोशुआ बलोच ने लिंक्डलिस्ट के बारे में लिखा है :

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

जावा में शास्त्रीय संग्रह के बीच कोई सिंगल लिंक्ड लिस्ट नहीं है , सिंगली लिंक्ड लिस्ट एक ऐसी संरचना है जहाँ हर नोड में एक ऑब्जेक्ट और अगले नोड का संदर्भ होता है, लेकिन पिछले वाले के लिए नहीं। Java LinkedList दो-लिंक्ड है, लेकिन कोई भी आपके साथ अपना डेटा स्ट्रक्चर बनाने के लिए हस्तक्षेप नहीं करता है, जैसे कि सिंगल, कोड> लिंक्ड लिस्ट। इन कार्यों को हल करने के लिए यहां कुछ चरण दिए गए हैं:

1. दो विशेषताओं, डेटा और अगले के साथ एक नोड वर्ग बनाएँ । अगला अगले नोड का संदर्भ है।
2. FirstLast क्लास को दो विशेषताओं, हेड और टेल के साथ बनाएँ ।
3. सूची में एक नया नोड जोड़ने के लिए एक ऐड () विधि बनाएँ। जांचें कि क्या सूची पहले खाली है ( सिर == शून्य )। यदि हां, तो हेड और टेल नए नोड को संदर्भित करते हैं। यदि सूची खाली नहीं है, तो नया नोड अंत में जोड़ा जाएगा, इसलिए पूंछ की अगली विशेषता जोड़े गए नोड को संदर्भित करती है और नया नोड सूची की पूंछ बन जाता है।

वैसे आप एक अभ्यास के रूप में अपनी खुद की LinkedList भी बनाने की कोशिश कर सकते हैं। आपके सीखने में गुड लक।