जावा में, एक लिंक्ड सूची में एक निरंतर समय ऑपरेशन क्यों सम्मिलन या हटाना है? क्या यह भ्रामक नहीं है?

Question

किसी सूची के किसी विशिष्ट बिंदु पर किसी तत्व का सम्मिलन या हटाना, यह मानते हुए कि हमारे पास पहले से ही नोड के लिए सूचक है, निरंतर समय का ऑपरेशन है। - एक लिंक्ड सूची में से the Wikipedia Article on Linked list

लिंक्ड सूची ट्रेवर्सल हमेशा सिर से शुरू होता है। हमें तब तक जारी रखना होगा जब तक कि हम किसी दिए गए शर्त को पूरा न करें।

तो इससे कोई भी ऑपरेशन सबसे खराब मामला ओ (एन) नहीं करेगा जब तक कि हम हेड नोड से निपट रहे हों।

हम सीधे एक लिंक्ड सूची में किसी दिए गए सूचक पर नहीं जा सकते हैं। तो यह क्यों कहा जाता है कि यह एक निरंतर समय ऑपरेशन है?

संपादित करें: भले ही हमारे पास नोड के लिए सूचक है, हमें केवल सिर से ही शुरुआत करना है? तो यह निरंतर समय ऑपरेशन कैसे है

Answer 1

सबसे पहले: LinkedList सूर्य JDK में लागू प्रभावी रूप से पिछले तत्व के साथ ही पहला तत्व के लिए एक लिंक (वहाँ केवल एक head प्रविष्टि है, लेकिन पिछले तत्व के लिए head.previous अंक) है। इसका मतलब यह है कि किसी सूचकांक द्वारा संकेतित तत्व को सूची के माध्यम से नेविगेट करने वाले सबसे बुरे मामले में भी एन/2 ऑपरेशन लेना चाहिए। यह एक दोगुनी जुड़ी सूची भी है।

इसके अलावा: LinkedList की शुरुआत या अंत में डालने से तुच्छ ओ (1) होता है, क्योंकि आपको सभी तत्वों को पार करने की आवश्यकता नहीं होती है।

कहीं भी सम्मिलित/निकालना इस बात पर निर्भर करता है कि आप इसे कैसे करते हैं! यदि आप Iterator (ListIterator जोड़ने के लिए) का उपयोग करते हैं तो ऑपरेशन ओ (1) भी हो सकता है, क्योंकि Iterator में पहले से ही प्रासंगिक प्रविष्टि का संदर्भ होगा।

अगर, हालांकि, आप add(int, E) या remove(int) उपयोग कर रहे हैं, तो LinkedListकरना होगा प्रासंगिक प्रविष्टि (ओ (एन)) और पाते हैं तो तत्व (ओ (1)), इसलिए पूरे हटाने ऑपरेशन ओ (एन) होगा।

Answer 2

आपने यह स्वयं कहा: "मान लीजिए कि हमारे पास पहले से ही नोड के लिए सूचक है"। यह उन ट्रैवर्सल से बचाता है जिन्हें आप रैखिक समय के कारण के रूप में पहचानते हैं।

मान लीजिए, विकिपीडिया टेक्स्ट थोड़ा अस्पष्ट है, क्योंकि इसमें दो नोड शामिल हैं: एक डाला जा रहा है, और सूची में से एक इसे कहां डालना है।

Answer 3

आप पहली बार इस धारणा को याद "यह सोचते हैं कि हम पहले से ही नोड के लिए एक सूचक है, एक निरंतर समय ऑपरेशन है", ऐसा लगता है।

Answer 4

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