मुझे समझ में नहीं आता कि एक लिंक्ड सूची के अंत में क्यों हटाना ओ (1) समय में जाता है, क्योंकि wikipedia article कहता है।एक लिंक की गई सूची ओ (1) में क्यों हट रहा है?
एक एकल लिंक्ड सूची नोड्स से बाहर होती है। एक नोड में कुछ प्रकार का डेटा होता है, और अगले नोड का संदर्भ होता है। लिंक्ड सूची में अंतिम नोड का संदर्भ शून्य है।
-------------- -------------- --------------
| data | ref | -> | data | ref | -> ... -> | data | ref |
-------------- -------------- --------------
मैं वास्तव में ओ (1) में अंतिम नोड को हटा सकता हूं। लेकिन उस स्थिति में आप नए अंतिम नोड, पिछले एक को संदर्भित नहीं करते हैं, क्योंकि इसमें अभी भी हटाए गए अंतिम नोड का संदर्भ शामिल है। तो मैं सोच रहा था कि क्या वे उपेक्षा करते हैं कि चल रहे समय विश्लेषण में? या यह माना जाता है कि संदर्भ के बाद से आपको इसे बदलने की ज़रूरत नहीं है, ठीक है, बस कुछ भी इंगित नहीं करता है, और इसे शून्य के रूप में देखा जाता है?
क्योंकि अगर इसे उपेक्षित नहीं किया जाएगा तो मैं तर्क दूंगा कि हटाना ओ (एन) है। चूंकि आपको नए अंतिम नोड तक पहुंचने के लिए पूरी सूची में फिर से शुरू करना है और इसके संदर्भ को भी शून्य पर सेट करना है। केवल एक डबल लिंक्ड सूची में यह वास्तव में ओ (1) होगा।
-edit- शायद इस बिंदु का दृश्य कुछ और स्पष्टता देता है। लेकिन मैं नोड को हटाने और पिछले संदर्भ को शून्य के रूप में सेट करने के रूप में "नोड का विलोपन" देखता हूं।
मुझे उस विकिपीडिया आलेख में ओ (1) के दो संदर्भ दिखाई देते हैं, लेकिन उनमें से कोई भी नहीं बताता है कि एकल-लिंक्ड सूची में अंतिम नोड को निकालना ओ (1) ऑपरेशन है। संभवतः, पहले से ही किसी भी नोड को हटाने के लिए आवश्यक हटाने के प्रयास के दौरान आप पहले से नोड को पॉइंटर धारण करते हैं। –