5
एकल लिंक वाली सूचियों (ओ (एन)) में नोड हटाने से दोगुनी लिंक्ड सूचियों (ओ (1)) में नोड हटाने की समय जटिलता क्यों है?एकल-और दोगुनी-लिंक्ड सूचियों में नोड हटाने की समय जटिलता
A
उत्तर
1
इसे आपके द्वारा हटाए जा रहे किसी भी नोड में अगले पॉइंटर को ठीक करने की जटिलता के साथ करना है।
2
क्योंकि आप पीछे की ओर नहीं देख सकते ...
15
समस्या मानता है कि नोड हटाए जाने के लिए जाना जाता है और उस नोड के लिए एक सूचक उपलब्ध है।
नोड को हटाने और पिछले और अगले नोड को एक साथ जोड़ने के लिए, आपको उनके पॉइंटर्स को जानने की आवश्यकता है। एक दोगुनी-लिंक्ड सूची में, दोनों पॉइंटर्स नोड में उपलब्ध होते हैं जिन्हें हटाया जाना है। इस मामले में समय जटिलता स्थिर है, यानी, ओ (1)।
जबकि एकल-लिंक्ड सूची में, पिछले नोड का सूचक अज्ञात है और केवल तब तक सूची से ट्रैवर करके पाया जा सकता है जब तक कि वह उस नोड तक पहुंच जाए जिसमें नोड को अगले नोड पॉइंटर को हटाया जाना है । इस मामले में समय जटिलता ओ (एन) है।
उन मामलों में जहां नोड को हटाया जाना चाहिए केवल मूल्य के आधार पर जाना जाता है, सूची की खोज की जानी चाहिए और समय जटिलता अकेले और दोगुनी-लिंक्ड सूचियों में ओ (एन) बन जाती है।
+0
ओ (एन) जटिलता की आवश्यकता वाली एक सिंगल लिंक्ड सूची से नोड को हटाने के संबंध में यह गलत है - नीचे मेरा उत्तर देखें। एक चाल है जहां आप हटाए जा रहे से अगले नोड से मूल्य की प्रतिलिपि बनाते हैं और उसके बाद नोड को इंगित करने के लिए उस को छोड़ दें, इस प्रकार सूची को पार करने की किसी भी आवश्यकता को समाप्त कर दें। – Ben
2
ज्ञात स्थिति में सम्मिलन और हटाना ओ (1) है। हालांकि, उस स्थिति को ढूंढना ओ (एन) है, जब तक यह सूची का सिर या पूंछ न हो।
जब हम सम्मिलन और हटाने की जटिलता के बारे में बात करते हैं, तो हम आम तौर पर मानते हैं कि हम पहले ही जानते हैं कि यह कहां होने जा रहा है।
1
जब तक तत्व को हटाने के लिए सिर (या पहले) नोड होता है, तो हमें हटाए जाने से पहले नोड पर जाने की आवश्यकता होती है। इसलिए, सबसे बुरे मामले में, यानी, जब हमें अंतिम नोड को हटाने की आवश्यकता होती है, तो पॉइंटर को दूसरे अंतिम नोड में सभी तरह से जाना पड़ता है जिससे ट्रैवर्सिंग (एन -1) स्थितियां होती हैं, जो हमें ओ (एन) की समय जटिलता देती है। ।
0
वास्तविक रूप से एकल लिंक्ड सूचियों में हटाने को ओ (1) में भी कार्यान्वित किया जा सकता है।
निम्नलिखित राज्य के साथ एक अकेले लिंक्ड सूची को देखते हुए:
SinglyLinkedList:
Node 1 -> Node 2
Node 2 -> Node 3
Node 3 -> None
Head = Node 3
हम इस तरह से delete Note 2 लागू कर सकते हैं:
Node 2 Value <- Node 3 Value
Node 2 -> None
यहाँ हम अपनी अगली के मूल्य के साथ Node 2 का मूल्य की जगह नोड (Node 3) और Node 3 (None) के अगले मूल्य सूचक में अपना अगला मान सूचक सेट करें, अब प्रभावी ढंग से "डुप्लिकेट" Node 3 पर छोड़ दें। इस प्रकार कोई ट्रैवर्सल की आवश्यकता नहीं है।
गृहकार्य? एक सिंगल लिंक्ड सूची से नोड को हटाने के लिए कोड लिखें, और फिर यह स्पष्ट होगा। –
मुझे लगता है कि शीर्षक में डीएलएल की तरह कमी नहीं होनी चाहिए, लेकिन मैं बेहतर नहीं सोच सकता। –