इतनी देर पहले मैंने गिनती नहीं की थी। java.util.LinkedList का उपयोग java.util.LinkedList के कार्यान्वयन के रूप में करने के लिए कोई बहाना नहीं है। लेकिन कुछ ने मुझे उसके लिए खोजा। चलिए इसका पता लगाते हैं। किसी भी सक्षम जावा विशेषज्ञ को पता है कि java.util.ArrayList का उपयोग तब किया जाना चाहिए जब हमें सूचकांक द्वारा त्वरित पहुंच की आवश्यकता हो, और java.util.LinkedList अगर हमें सूची के बीच में तत्वों को सम्मिलित करने या हटाने की आवश्यकता है। उनमें से बहुतों का अनुमान नहीं है कि यदि हम सूची के मध्य में तत्वों को सम्मिलित करते हैं या हटाते हैं remove(int index) और add(int index, E element) विधियों का, तो सूची O(N) के आकार के लिए आवश्यक तत्व आनुपातिक की खोज में औसत समय लगेगा। । तो java.util.LinkedList का उपयोग करने का लाभ कब है?

पुनरावृत्तियों का उपयोग करते समय। अधिक सटीक रूप से, जब आप java.util.ListIterator माध्यम से तत्वों को हटाते या सम्मिलित करते हैं। अंत में, बहाने की तलाश में, मुझे एक बहुत ही वास्तविक कोड उदाहरण मिला, जिस पर java.util.LinkedList पर एक महत्वपूर्ण लाभ देता है। यह सबसे सरल फ़िल्टरिंग एल्गोरिथ्म है जो सूची से उन सभी तत्वों को हटा देता है जो निर्दिष्ट स्थिति को संतुष्ट नहीं करते हैं।

 for (Iterator<E> i = list.iterator(); i.hasNext(); ) { E val = i.next(); if (!condition(val)) { i.remove(); } } 

एक ही कोड को आसानी से एक अतिरिक्त सूची का उपयोग करके फिर से लिखा जा सकता है, और फिर java.util.ArrayList साथ एल्गोरिदम, कम से कम, मूल आकार पर एक द्विघात निर्भरता नहीं होगी।

 List<E> list1 = new ArrayList<E>(); for (Iterator<E> i = list.iterator(); i.hasNext(); ) { E val = i.next(); if (condition(val)) { list1.add(val); } } list.clear(); list.addAll(list1); 

लेकिन यह सही नहीं है कि डेटा संरचना हमारे लिए एक एल्गोरिथ्म तय करती है। लेकिन यह एल्गोरिथ्म था जिसने मुझे यह सोचने के लिए प्रेरित किया कि एक ऐसी सूची कैसे बनाई जाए जो कि O(1) दौरान अधिकांश संचालन करेंगे।

ऐसा करने के लिए, हमें इस धारणा की आवश्यकता है: "ऑपरेशन सम्मिलित करें और हटाएं। कंधे से कंधा मिलाकर।" बेशक, हम एक ऐसी स्थिति की कल्पना कर सकते हैं जिसमें सम्मिलित और हटाए जाने वाले ऑपरेशन बेतरतीब ढंग से घटित होंगे, लेकिन इस मामले में न तो java.util.ArrayList और न ही java.util.ArrayList हमें बचाएगा। java.util.LinkedList कि हम लड़ते हैं। दरअसल, एक मनमाना तत्व जोड़ने या हटाने के लिए, java.util.ArrayList को आमतौर पर सरणी के तत्वों की संख्या को O (N) के आकार के आनुपातिक रूप से स्थानांतरित करना चाहिए, और java.util.LinkedList को इसे O(N) करना चाहिए।

विचार यह है। सूची एक सरणी में संग्रहीत नहीं है, लेकिन 2x में है। इसके अलावा, प्रत्येक सरणी इसे अपनी संपूर्णता में समायोजित कर सकती है।



सूची के बीच में एक तत्व सम्मिलित करते समय, हम इसे अंतराल में सम्मिलित करते हैं। लेकिन आखिरकार, हम उस तत्व को गलत जगह डालना चाहते हैं जहां अलगाव होता है। ऐसा करने के लिए, हम तत्वों का हिस्सा स्थानांतरित करते हैं ताकि अंतराल सही जगह पर चले।



आप कहेंगे: "हाँ, हमने java.util.ArrayList के मामले की तुलना में कम तत्वों को स्थानांतरित किया है, लेकिन यह अभी भी सूची के आकार के समानुपाती है।" आप सही हैं, लेकिन अगर हम अपनी धारणा को याद करते हैं, तो हर बार, पहले को छोड़कर, हम आगे बढ़ेंगे। तत्वों की एक छोटी संख्या।

डिलीट करते समय भी यही बात होती है। अंतर उस स्थान पर स्थानांतरित कर दिया जाता है जहां से तत्व हटा दिया गया था।

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

ArrayList

आकार	भरण	अनुक्रम	सूची	छानने का काम	पहले हटाओ
20000	0	0	0	94	47
40000	0	0	0	406	187
60000	16	0	0	891	437
80000	0	0	0	1578	782
100000	0	15	0	2453	1219
120000	16	0	15	3516	1750
140000	16	0	0	4796	2391
160000	16	0	15	6219	3125
180000	16	0	15	7969	3984
200000	63	0	0	9859	4844

जैसा कि आप टेबल से देख सकते हैं, java.util.ArrayList को भरने और किसी भी स्कैनिंग के साथ पूरी तरह से मुकाबला करता है, और फ़िल्टरिंग और यहां तक ​​कि सिर से सूची को हटाने पर एक कुचल हार का सामना करना पड़ता है।

LinkedList

आकार	भरण	अनुक्रम	सूची	छानने का काम	पहले हटाओ
20000	0	0	406	0	0
40000	31	0	1985	0	0
60000	15	0	3828	16	0
80000	0	0	8359	0	0
100000	16	0	24,891	0	15
120000	16	0	43,562	16	0
140000	16	15	52,985	0	15
160000	16	0	57,047	15	0
180000	79	0	121,531	0	15
200000	32	15	152,250	16	16

java.util.LinkedList का कमजोर बिंदु इंडेक्स एक्सेस है, लेकिन फ़िल्टरिंग ऑपरेशन बहुत तेज है।

DoubleArrayList

आकार	भरण	अनुक्रम	सूची	छानने का काम	पहले हटाओ
20000	0	0	0	0	0
40000	16	0	0	0	0
60000	0	0	0	15	0
80000	0	0	16	0	0
100000	16	0	0	15	0
120000	16	0	0	15	0
140000	16	16	0	15	0
160000	16	16	0	15	0
180000	47	16	0	15	0
200000	32	0	15	0	16

और अंत में, org.kefirsf.list.DoubleArrayList का मेरा कार्यान्वयन किसी भी परीक्षण पर विफल नहीं होता है।

चलो बड़े संस्करणों पर लिंक्डलिस्ट के साथ तुलना करें।

भरने

छानने

सिर निकालना

इन सभी DoubleArrayList यह देखा जा सकता है कि DoubleArrayList java.util.LinkedList तुलनीय समय के लिए विभिन्न परिचालनों पर काम कर रहा है। भले ही हमेशा बेहतर न हो। मुख्य बात यह है कि सरणी के आकार पर कोई द्विघात निर्भरता नहीं है, और सभी ऑपरेशन O(N) , जिसका अर्थ है कि O(1) में औसतन एकल ऑपरेशन किए जाते हैं। इस प्रकार, लक्ष्य प्राप्त किया जाता है।

कोड org.kefirsf.list.DoubleArrayList GitHub पर उपलब्ध है: github.com/kefirfromperm/multi-array-list
सावधानी: औद्योगिक विकास में इसका उपयोग करने का प्रयास न करें। org.kefirsf.list.DoubleArrayList अभी भी परीक्षणों द्वारा अच्छी तरह से कवर नहीं किया गया है, इसके उपयोग से मेमोरी लीक हो सकती है।