लिंक्डलिस्ट संग्रह का परिचय

1. का इतिहासLinkedList

जावा में एक अन्य संग्रह वर्ग जावा है जो सी ++ भाषा से विरासत में मिला है। यह वह LinkedListवर्ग है, जो "लिंक की गई सूची" को लागू करता है।

बाह्य रूप से, LinkedListएक के समान प्रतीत होता है ArrayList। कक्षा में कक्षा LinkedListके समान सभी विधियाँ हैं ArrayList। सिद्धांत रूप में, आप हमेशा LinkedLista के बजाय a का उपयोग कर सकते हैं ArrayListऔर सब कुछ काम करेगा।

तो हमें दूसरी सूची वर्ग की आवश्यकता क्यों है?

LinkedListउत्तर का कक्षा की आंतरिक संरचना से सब कुछ लेना-देना है । एक सरणी के बजाय, यह एक दोगुनी लिंक्ड सूची का उपयोग करता है । हम थोड़ी देर बाद समझाएंगे कि वह क्या है।

वर्ग LinkedListकी विभिन्न आंतरिक संरचना सूची के मध्य में तत्वों को सम्मिलित करने में इसे सबसे तेज़ बनाती है।

इंटरनेट पर, आप अक्सर ArrayListऔर LinkedListकक्षाओं की तुलना पा सकते हैं:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

सब कुछ पर्याप्त स्पष्ट लगता है: यदि आपको अक्सर सूची में तत्वों को सम्मिलित करने की आवश्यकता होती है, तो उपयोग करें LinkedList; यदि शायद ही कभी, तो ArrayList का उपयोग करें। लेकिन हकीकत थोड़ी अलग है।

2. कोई उपयोग नहीं करताLinkedList

कोई उपयोग नहीं करता LinkedList।

यहां तक ​​कि कक्षा के लेखक ने भी LinkedListहाल ही में ट्वीट किया: "क्या वास्तव में कोई इसका उपयोग करता है LinkedList? मैंने इसे लिखा है, और मैं इसका उपयोग कभी नहीं करता हूं।"

तो सौदा क्या है?

सबसे पहले, कक्षा ArrayListबहुत जल्दी सूची के बीच में तत्वों को सम्मिलित करने में सक्षम होने लगी। सूची के बीच में एक तत्व सम्मिलित करते समय, आपको सूची के अंत की ओर सम्मिलन बिंदु के बाद सभी तत्वों को 1 से स्थानांतरित करना होगा। इसमें समय लगता था।

लेकिन अब सब कुछ बदल गया है. एक सरणी के सभी तत्व मेमोरी के एक ही ब्लॉक में एक दूसरे के पास होते हैं, इसलिए तत्वों को स्थानांतरित करने के लिए ऑपरेशन बहुत तेज़ निम्न-स्तरीय कमांड द्वारा किया जाता है :।System.arraycopy()

इसके अलावा, आज के प्रोसेसर में एक बड़ा कैश होता है जो आमतौर पर पूरे एरे को होल्ड कर सकता है, जो एरे एलिमेंट्स को मेमोरी के बजाय कैश के अंदर स्थानांतरित करने की अनुमति देता है। एक मिलीसेकंड में एक लाख तत्व आसानी से स्थानांतरित हो जाते हैं।

दूसरा, यदि आप एक पुनरावर्तक का उपयोग करके उन्हें सम्मिलित करते हैं, तो वर्ग तत्वों को जल्दी से सम्मिलित कर सकता है । LinkedListयदि आप a के माध्यम से जाने के लिए एक पुनरावर्तक का उपयोग करते हैं LinkedListऔर लगातार नए तत्व सम्मिलित करते हैं (या मौजूदा वाले को हटाते हैं), तो ऑपरेशन सुपर फास्ट है।

यदि आप केवल LinkedListलूप के अंदर किसी ऑब्जेक्ट में तत्व जोड़ते हैं, तो प्रत्येक तेज़ इंसर्ट ऑपरेशन एक धीमी "गेट एलिमेंट" ऑपरेशन के साथ होता है।

हकीकत इसके काफी करीब है:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

LinkedListइतने धीमे ऑपरेशन से तत्व क्यों प्राप्त हो रहा है ?

आप उस प्रश्न का उत्तर थोड़ा परिचित होने के बाद दे सकते हैं कि कैसे LinkedListसंरचित किया जाता है।

3. कैसे LinkedListसंरचित है

LinkedListकी तुलना में एक अलग आंतरिक संरचना है ArrayList। तत्वों को संग्रहित करने के लिए इसमें आंतरिक सरणी नहीं है। इसके बजाय, यह एक दोगुनी स्याही वाली सूची नामक डेटा संरचना का उपयोग करता है ।

दोगुनी लिंक्ड सूची का प्रत्येक तत्व पिछले तत्व और अगले तत्व के संदर्भ को संग्रहीत करता है। यह कुछ-कुछ दुकान पर लगी एक लाइन की तरह है, जहां प्रत्येक व्यक्ति अपने सामने खड़े व्यक्ति को भी याद करता है और साथ ही अपने पीछे खड़े व्यक्ति को भी।

स्मृति में ऐसी सूची कैसी दिखती है:

सिर और पूंछ (भूरे रंग की पृष्ठभूमि वाली कोशिकाएं) firstऔर lastचर हैं, जो Nodeवस्तुओं के संदर्भों को संग्रहीत करते हैं।

बीच में, आपके पास Nodeवस्तुओं की एक श्रृंखला होती है (वस्तुएं, चर नहीं)। उनमें से प्रत्येक में तीन फ़ील्ड होते हैं:

• prev- पिछली वस्तु (पीले रंग की पृष्ठभूमि वाली कोशिकाओं) के संदर्भ (लिंक) को संग्रहीत करता है।Node
• value- सूची के इस तत्व (हरे रंग की पृष्ठभूमि वाली कोशिकाओं) के मूल्य को संग्रहीत करता है।
• next- अगली वस्तु के लिए एक संदर्भNode (लिंक) संग्रहीत करता है (नीली पृष्ठभूमि वाली कोशिकाएं)

दूसरी वस्तु (पता F24) nextपहली वस्तु के लिए अगली ( ) और prevतीसरी वस्तु के लिए पिछली ( ) है। तीसरी वस्तु के पीले क्षेत्र में पता F24 होता है और पहली वस्तु के नीले क्षेत्र में पता F24 होता है।

पहली और तीसरी वस्तुओं के तीर एक ही दूसरी वस्तु की ओर इशारा करते हैं। इसलिए इस तरह तीर खींचना ज्यादा सही होगा।

4. किसी लिंक की गई सूची में कोई तत्व डालें

किसी को इस तरह से लाइन में जोड़ने के लिए, आपको बस एक दूसरे के बगल में खड़े दो लोगों की अनुमति लेनी होगी। पहला व्यक्ति नवागंतुक को "मेरे पीछे वाले व्यक्ति" के रूप में याद करता है, और दूसरा व्यक्ति उन्हें "मेरे सामने वाले व्यक्ति" के रूप में याद करता है।

आपको केवल दो पड़ोसी वस्तुओं के संदर्भों को बदलने की आवश्यकता है:

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

किसी तत्व को हटाना और भी आसान है: यदि हम सूची से 100वीं वस्तु को हटाना चाहते हैं, तो हमें केवल 99वीं वस्तु के लिए फ़ील्ड बदलने की आवश्यकता है ताकि यह 101वीं वस्तु की ओर इशारा करे, nextऔर prev101वीं वस्तु के लिए फ़ील्ड बदलें ऑब्जेक्ट ताकि यह 99 वें की ओर इशारा करे। इतना ही।

लेकिन 100वीं वस्तु प्राप्त करना इतना आसान नहीं है।

5. किसी सूची से एक तत्व निकालें

किसी लिंक की गई सूची का 100वाँ तत्व प्राप्त करने के लिए, आपको चाहिए:

पहली वस्तु प्राप्त करें: आप इसे वस्तु firstमें चर का उपयोग करके करते हैं। LinkedListपहली वस्तु का क्षेत्र nextदूसरी वस्तु के संदर्भ को संग्रहीत करता है। इसी तरह हमें दूसरी वस्तु मिलती है। दूसरी वस्तु में तीसरे का संदर्भ है, और इसी तरह।

यदि हमें 100वीं वस्तु का संदर्भ प्राप्त करने की आवश्यकता है, तो हमें पहली से 100वीं वस्तु तक क्रमिक रूप से सभी वस्तुओं के माध्यम से जाने की आवश्यकता है। और अगर हमें किसी सूची में दस लाखवें तत्व की आवश्यकता है, तो हमें एक के बाद एक दस लाख से अधिक वस्तुओं को पुनरावृत्त करने की आवश्यकता है!

और अगर इन वस्तुओं को अलग-अलग समय पर सूची में जोड़ा गया था, तो वे स्मृति के विभिन्न हिस्सों में स्थित होंगे और प्रोसेसर के कैश में एक ही समय में समाप्त होने की संभावना नहीं है। इसका मतलब यह है कि एक लिंक की गई सूची के तत्वों पर पुनरावृति न केवल धीमी है, बल्कि बहुत धीमी है।

हम इससे निपट रहे हैं।

तो हम आपको यह क्यों सिखा रहे हैं कि यह धीमा कैसे LinkedListकाम करता है?

ठीक है, नौकरी के साक्षात्कार के दौरान आपसे पूछा जाएगा कि यह कैसे LinkedListसे अलग हैArrayList । निश्चित रूप से।