चित्रों में डेटा संरचनाएं। ArrayList

मैं आपको नमस्कार करता हूं, हेब्रालुडी!

जावा में कुछ डेटा संरचनाएं कैसे कार्यान्वित की जाती हैं, इसके बारे में कुछ लेख लिखने के लिए यह मेरे दिमाग में आया। मुझे उम्मीद है कि लेख विजुअल्स के लिए उपयोगी होंगे (हमारी तस्वीरें सब कुछ हैं), शुरुआती जावा विजुअल्स, और उन लोगों के लिए भी जो पहले से ही जानते हैं कि कैसे नए ArrayList () लिखना है, लेकिन अंदर क्या हो रहा है, इसका थोड़ा पता है।



आज बात करते हैं ArrayLists की

ArrayList - सूची इंटरफ़ेस को लागू करता है। जैसा कि आप जानते हैं, जावा सरणियों में एक निश्चित लंबाई होती है, और सरणी बनने के बाद, यह बढ़ या सिकुड़ नहीं सकता है। ArrayList कार्यक्रम के निष्पादन के दौरान अपना आकार बदल सकता है, और ऑब्जेक्ट बनाते समय आयाम को निर्दिष्ट करना आवश्यक नहीं है। ArrayList तत्व किसी भी प्रकार के हो सकते हैं, जिसमें null भी शामिल है।

वस्तु निर्माण

ArrayList<String> list = new ArrayList<String>(); 

नई बनाई गई सूची ऑब्जेक्ट में तत्व और आकार गुण होते हैं।

एलीमेंटडैटा वैल्यूज का स्टोरेज एक निश्चित प्रकार (जेनेरिक में निर्दिष्ट) के एक सरणी से ज्यादा कुछ नहीं है, हमारे मामले में स्ट्रिंग [] । यदि मापदंडों के बिना एक निर्माता को बुलाया जाता है, तो डिफ़ॉल्ट रूप से प्रकार के 10 तत्वों की एक सरणी बनाई जाएगी वस्तु (एक डाली से एक प्रकार, निश्चित रूप से)।

 elementData = (E[]) new Object[10]; 

आप ArrayList (क्षमता) कंस्ट्रक्टर का उपयोग कर सकते हैं और अपनी प्रारंभिक सूची क्षमता निर्दिष्ट कर सकते हैं।

आइटम जोड़ना

 list.add("0"); 

ऐड (मान) विधि के अंदर, निम्नलिखित चीजें होती हैं:

1) यह जाँच की जाती है कि क्या नया तत्व डालने के लिए सरणी में पर्याप्त जगह है;

 ensureCapacity(size + 1); 

2) एक तत्व सरणी के अंत ( आकार मूल्य के अनुसार) में जोड़ा जाता है।

 elementData[size++] = element; 

हम संपूर्ण सुनिश्चितता (न्यूनतम क्षमता) विधि पर विचार नहीं करेंगे, हम केवल कुछ दिलचस्प स्थानों पर ध्यान केंद्रित करेंगे। यदि सरणी में पर्याप्त स्थान नहीं है, तो नई क्षमता की गणना सूत्र (पुरानेता * 3) / 2 + 1 द्वारा की जाती है । दूसरा बिंदु तत्वों की नकल है। यह मूल System.arraycopy () पद्धति का उपयोग करके लागू किया गया है , जो जावा में नहीं लिखा गया है।

 // newCapacity -    elementData = (E[])new Object[newCapacity]; // oldData -       System.arraycopy(oldData, 0, elementData, 0, size); 

निम्नलिखित 15 तत्वों को जोड़कर एक लूप प्रदर्शित करता है:

 list.add("1"); 

...

 list.add("9"); 

 list.add("10"); 

11 वें तत्व को जोड़ते समय, चेक दिखाता है कि सरणी में कोई जगह नहीं है। तदनुसार, एक नया सरणी बनाया जाता है और System.arraycopy () कहा जाता है।



उसके बाद, तत्वों को जोड़ना जारी है



...

 list.add("14"); 

सूची के "मध्य" में जोड़ना

 list.add(5, "100"); 

किसी आइटम को किसी विशेष इंडेक्स वाली स्थिति में जोड़ना तीन चरणों में होता है:

1) यह जाँच की जाती है कि क्या नया तत्व डालने के लिए सरणी में पर्याप्त जगह है;

 ensureCapacity(size+1); 

2) System.arraycopy () का उपयोग करके एक नए तत्व के लिए जगह तैयार करें ;

 System.arraycopy(elementData, index, elementData, index + 1, size - index); 

3) निर्दिष्ट सूचकांक के साथ तत्व का मूल्य ओवरराइट किया गया है।

 elementData[index] = element; size++; 

जैसा कि आप अनुमान लगा सकते हैं कि ऐसे मामलों में जब कोई तत्व इंडेक्स द्वारा डाला जाता है और आपके एरे में कोई खाली सीट नहीं होती है, तो System.arraycopy () के लिए कॉल दो बार होगा: सबसे पहले ensCapacity () में , दूसरा ऐड (इंडेक्स, वैल्यू) विधि में, जो स्पष्ट रूप से पूरे ऐड ऑपरेशन की गति को प्रभावित करेगा।

ऐसे मामलों में जब आपको स्रोत सूची में एक और संग्रह जोड़ने की आवश्यकता होती है, और यहां तक ​​कि "मध्य" तक, यह ऐडऑल (सूचकांक, संग्रह) विधि का उपयोग करने के लायक है। और यद्यपि यह विधि System.arraycopy () को तीन बार कॉल करने की संभावना है, अंत में यह तत्व द्वारा जोड़ने की तुलना में बहुत तेज होगा।

आइटम हटाएं

आइटम हटाने के दो तरीके हैं:
- निकालें (अनुक्रमणिका) सूचकांक द्वारा
- मूल्य निकालें (मूल्य) द्वारा

सूचकांक द्वारा एक तत्व को हटाने के साथ, सब कुछ काफी सरल है

 list.remove(5); 

पहले, निर्धारित करें कि कितने आइटम कॉपी करने हैं।

 int numMoved = size - index - 1; 

उसके बाद System.arraycopy () का उपयोग करके तत्वों को कॉपी करें

 System.arraycopy(elementData, index + 1, elementData, index, numMoved); 

सरणी का आकार कम करें और अंतिम तत्व के बारे में भूल जाएं

 elementData[--size] = null; // Let gc do its work 

मान से हटाते समय, एक लूप में सूची के सभी तत्वों का मिलान होने तक स्कैन किया जाता है। केवल पहला आइटम हटा दिया जाएगा।

परिवर्धन 1: जैसा कि माइकमिरज़ायनोव ने सही ढंग से नोट किया है, जब तत्वों को हटाते हैं, तो क्षमता का वर्तमान मूल्य कम नहीं होता है, जिससे अजीब स्मृति लीक हो सकती है। इसलिए, trimToSize () विधि की उपेक्षा न करें।

परिणाम

- हे (1) के दौरान सूचकांक द्वारा वस्तुओं तक त्वरित पहुंच;
- रैखिक समय ओ (एन) में मूल्य से तत्वों तक पहुंच;
- तत्वों को सूची के "मध्य" से डाला और हटाए जाने पर धीमा;
- आप अशक्त सहित किसी भी मूल्यों को संग्रहीत करने की अनुमति देता है;
- सिंक्रनाइज़ नहीं।

संदर्भ

स्रोत ArrayList
JDK7 से ArrayList स्रोत
JDK के स्रोत OpenJDK और व्यापार 6 स्रोत रिलीज़ - बिल्ड b23


टिप्पणियों के सुझावों / टिप्पणियों में लिखें और यह जारी रखने के लिए समझ में आता है या नहीं।