ऐरेलिस्ट की शुरुआत में तत्व जोड़ने की जटिलता क्या है?

Question

मैं इस सरणी में n तत्व के साथ एक ArrayList है कहो, और मैं शुरुआत में एक तत्व जोड़ें:

myArrayList.add(0,'some value'); 

क्या इस आपरेशन के समय जटिलता हो जाएगा?

Java Doc यह निर्दिष्ट नहीं करता है।

इसके अलावा

मैं सिर्फ जावा सीखना प्रारंभ करें, और मैं क्या समर्थित 'के बारे में यहां मतलब वाक्य

An ArrayList in Java is a List that is backed by an array. 

देखा था? धन्यवाद!

Answer 1

सरणी शुरू करने के लिए तत्व जोड़ना ओ (एन) है - इसे सभी मौजूदा तत्वों को एक स्थिति में स्थानांतरित करने की आवश्यकता होगी।

एक सरणी सूची में सभी तत्व एक संगत सरणी में संग्रहीत हैं। यदि आप सरणी के वर्तमान आकार की तुलना में अधिक तत्व जोड़ते हैं - यह नए तत्व को समायोजित करने के लिए स्वचालित रूप से उगाया जाएगा।

अंत में जोड़ ओ (1) एकाधिक प्रविष्टियों पर amortized है।

Answer 2

ArrayList.add(0, element) रैखिक समय लेता है, लेकिन स्थिर बहुत कम है, क्योंकि यह तेज तेज System.arraycopy का उपयोग कर सकता है।

Answer 3

• खरोंच से सूची का निर्माण और द्विघात समय में शुरू रन करने के लिए तत्वों के बहुत सारे जोड़ने: O (n)।
• सूची के अंत में सभी तत्व जोड़ना और फिर Collections.reverse(list) रैखिक समय में चलता है: ओ (एन)।