लिंक्ड सूची प्रविष्टि चलने का समय भ्रम की स्थिति

Question

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

एक लिंक्ड सूची के अंत में एक तत्व डालने के लिए, मुझे लगता है कि यह हे (एन) ले जाएगा के बाद से यह पूंछ तक पहुँचने के लिए सूची के अंत में पार करने के लिए है लगता होगा। लेकिन मैंने देखा कुछ जवाब ओ (1) कहते हैं? क्या वे मानते हैं कि पूंछ के लिए एक सूचक के सभी लिंक सूचियों का कार्यान्वयन? यदि हां, तो क्या यह स्वीकार्य धारणा है?

दूसरा, कुछ स्थान यह भी सुझाव देते हैं कि एक लिंक्ड सूची के बीच में एक तत्व सम्मिलित करना ओ (1) है जिसे मैं सूची के बीच में घुमाने के समान तर्क के कारण उलझन में हूं।

कोई स्पष्ट कर सकते हैं? धन्यवाद।

Answer 1

किसी लिंक किए गए सूची में सम्मिलित करना हे है (1) आप नोड जहां आइटम सम्मिलित करना चाहते हैं के लिए सूचक है। ढूँढना यह नोड ओ (एन) हो सकता है जो आप करना चाहते हैं उसके आधार पर।

आप सूची की पूंछ के लिए सूचक रखने तो आप इसे देखने के लिए की जरूरत नहीं है और फिर प्रविष्टि हे (1) है।

और नहीं, नहीं सभी लिंक्ड सूची कार्यान्वयन सूची के अंत में एक सूचक है।

उदाहरण

मान लीजिए आप एक खाली सूची है जो आप एक एकल नोड, x जोड़ने के लिए। फिर आप x से पहले और बाद में सूची में n नोड्स जोड़ें। तुम अब भी बस अपने next सूचक को अपडेट करके x के बाद एक भी नोड सम्मिलित कर सकते हैं (और नए नोड के), भले ही कितने नोड्स सूची थे कर रहे हैं। ,, नोड संकेत

लिंक्ड सूची में बदलकर

1. नोड लगाने
2. को नए नोड वास्तव में नोड जोड़कर संलग्न करने के लिए:

Answer 2

लिंक्ड सूची में संशोधन दो आपरेशन शामिल दूसरा ऑपरेशन O(1) ऑपरेशन है, इसलिए यह पहले संचालन की लागत का मामला है।

जब पिछले नोड के लिए जोड़कर, लिंक्ड सूची की भोली कार्यान्वयन O(n) यात्रा समय में परिणाम होगा। हालांकि, अच्छी तरह से जुड़ी सूची पुस्तकालय सबसे आम उपयोगों के लिए जिम्मेदार होंगे, और अंतिम नोड तक पहुंचने वाला विशेष मामला होगा। इस अनुकूलन के परिणामस्वरूप O(1) अंतिम तत्व की पुनर्प्राप्ति होगी, जिसके परिणामस्वरूप कुल O(1) सम्मिलन समय समाप्त हो जाएगा।

बीच का सवाल है, अपने विश्लेषण में नोड लगाने वह भी O(n) ले जाएगा सही है। हालांकि, कुछ पुस्तकालयों के लिए एक विधि है कि जहां नए नोड सूचकांक (जैसे C++list) के बजाय डाला जाना चाहिए करने के लिए एक सूचक ले जाएगा बेनकाब। यह रैखिक लागत को समाप्त करता है, जिसके परिणामस्वरूप सभी O(1) से अधिक होता है।

जबकि मध्य में सम्मिलन आमतौर पर O(n) ऑपरेशन के रूप में सोचा जाता है, इसे कुछ मामलों में O(1) पर अनुकूलित किया जा सकता है।यह सरणी सूची के विपरीत है, जहां सम्मिलन ऑपरेशन स्वयं (दूसरा ऑपरेशन) O(n) है, क्योंकि उच्च स्थानों के सभी तत्वों को स्थानांतरित करने की आवश्यकता है। इस ऑपरेशन को अनुकूलित नहीं किया जा सकता है।

डालने के लिए एक लिंक्ड सूची के एक निष्पक्ष कार्यान्वयन के परिणामस्वरूप O(n) सम्मिलन समय होगा। हालांकि, अच्छी तरह से जुड़ी सूची लाइब्रेरी लेखकों को आम मामलों के लिए अनुकूलित किया जाएगा, इसलिए वे अंतिम तत्वों (या एक गोलाकार लिंक सूची कार्यान्वयन) के संदर्भ में रहेंगे, जिसके परिणामस्वरूप O(1) सम्मिलन समय होगा।

बीच में प्रविष्टि के लिए के रूप में। C++ की तरह कुछ पुस्तकालयों में सम्मिलन के लिए एक सुझाया गया स्थान है। वे सूची नोड में एक सूचक लेते हैं, जहां नया एक जोड़ा जा सकता है। इस तरह के सम्मिलन का खर्च O(1) होगा। मुझे नहीं लगता कि आप इंडेक्स नंबर से O(1) प्राप्त कर सकते हैं।

यह एक सरणी सूची के लिए लगाया गया है, जहां मध्य बलों को सम्मिलन से अधिक सभी तत्वों के पुनर्वितरण में प्रवेश किया जाता है, इसलिए इसे O(n) ऑपरेशन होना चाहिए।

Answer 3

Per the Java LinkedList source code, जावा header.previous के माध्यम से header एंट्री पूंछ तत्व के लिए एक लिंक देकर LinkedList पूंछ के संचालन के लिए हे (1) प्राप्त होता है। तो यदि आप अंतिम तत्व चाहते हैं, तो कक्षा हमेशा header.previous लौटा सकती है, जो निरंतर समय की अनुमति देती है।

मुझे लगता है कि अन्य भाषाओं का एक बहुत ही बुनियादी रणनीति का उपयोग करें।

Answer 4

जाहिर है आप शायद विकिपीडिया प्रविष्टि http://en.wikipedia.org/wiki/Linked_list देखा है। मैं उस तालिका को देखता हूं जहां वे निर्दिष्ट कर रहे हैं कि अंत में और सूची के मध्य में दोनों को डालने/हटाने से ओ (1) प्रदर्शन होता है लेकिन यह निर्धारित करने में विफल रहता है कि उन्होंने इसे कैसे निर्धारित किया है।

एक ऐसी ही सवाल stackoverflow पर यहाँ Why is inserting in the middle of a linked list O(1)? में करने के लिए कुछ रोचक जवाब नहीं है। उस प्रश्न के मूल पोस्टर ने अपनी पोस्ट संपादित की और एक मुद्दा बना दिया कि उनका मानना ​​है कि जब यह कहा जाता है कि सम्मिलन/हटाना ओ (1) है तो वे वास्तविक सम्मिलन संचालन के बारे में बात कर रहे हैं और जहां पर डालने की खोज नहीं है। यह समझ में आता है लेकिन मैंने इस बिंदु पर पाया गया किसी भी लेख में औपचारिक रूप से यह नहीं देखा है।

Answer 5

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

Answer 6

मुझे लगता है कि अपने भ्रम का एक कारण यह है कि आप के रूप में अगर वहाँ एक आदर्श/विहित लिंक्ड सूची, जो या तो है या क्या करता है सोच रहे है कुछ सिर/पूंछ पॉइंटर्स नहीं है। हकीकत यह है कि किसी भी रैखिक (यानी कोई शाखा नहीं) डेटा संरचना जो पिछले तत्वों से पॉइंटर्स के माध्यम से जाकर तत्वों तक पहुंचती है मूल रूप से एक लिंक की गई सूची है। चाहे आप पॉइंटर्स को पहले, आखिरी, के-वें इत्यादि रखें, तत्व पूरी तरह से आपके ऊपर हैं। इसलिए, यदि आपको ऐसी सूची की आवश्यकता है जहां आपको अक्सर 10 वीं स्थिति में तत्वों को सम्मिलित/हटाने की आवश्यकता होती है, तो आप केवल उस व्यक्ति को कार्यान्वित कर सकते हैं जिसमें 9वीं तत्व के लिए अतिरिक्त सूचक है और इसे ओ (1) समय में करें।

एक और बात यह है कि जब एक लिंक्ड-लिस्ट के तत्वों पर पुनरावृत्ति करते हैं, तो आप ओ (1) में वर्तमान तत्व (और इससे पहले कि अगर यह डबल लिंक्ड सूची है) के ठीक बाद एक नया तत्व डालें, क्योंकि आप पहले से ही एक सूचक है।

Answer 7

@ केलेब ब्रसेई बताते हैं कि जावा में पूंछ में डालने से ओ (1) है क्योंकि जावा एक दोगुनी-लिंक्ड सूची का उपयोग LinkedList कार्यान्वयन के रूप में करता है। मुझे लगता है कि यह बहुत सारे एसडीके कार्यान्वयन के लिए काफी आम पसंद है। उदाहरण के लिए, एसटीएल list कार्यान्वयन दोगुना-जुड़ा हुआ है (source)।