एकल-और दोगुनी-लिंक्ड सूचियों में नोड हटाने की समय जटिलता

Question

एकल लिंक वाली सूचियों (ओ (एन)) में नोड हटाने से दोगुनी लिंक्ड सूचियों (ओ (1)) में नोड हटाने की समय जटिलता क्यों है?

Answer 1

इसे आपके द्वारा हटाए जा रहे किसी भी नोड में अगले पॉइंटर को ठीक करने की जटिलता के साथ करना है।

Answer 2

क्योंकि आप पीछे की ओर नहीं देख सकते ...

Answer 3

समस्या मानता है कि नोड हटाए जाने के लिए जाना जाता है और उस नोड के लिए एक सूचक उपलब्ध है।

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

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

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

Answer 4

ज्ञात स्थिति में सम्मिलन और हटाना ओ (1) है। हालांकि, उस स्थिति को ढूंढना ओ (एन) है, जब तक यह सूची का सिर या पूंछ न हो।

जब हम सम्मिलन और हटाने की जटिलता के बारे में बात करते हैं, तो हम आम तौर पर मानते हैं कि हम पहले ही जानते हैं कि यह कहां होने जा रहा है।

Answer 5

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

Answer 6

वास्तविक रूप से एकल लिंक्ड सूचियों में हटाने को ओ (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 पर छोड़ दें। इस प्रकार कोई ट्रैवर्सल की आवश्यकता नहीं है।