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

बुनियादी संचालन और उनकी जटिलताएं

लिंक्ड सूची संचालन में सम्मिलन, विलोपन और ट्रैवर्सल शामिल हैं। प्रत्येक ऑपरेशन की समय जटिलता इस बात पर निर्भर करती है कि क्या सूची अकेले है या दोगुना जुड़ा हुआ है और क्या ऑपरेशन की स्थिति ज्ञात है।

प्रवेशन संचालन

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

विलंब ऑपरेशन

पहले नोड को हटाने एक O(1) ऑपरेशन है, क्योंकि इसमें केवल पॉइंटर अपडेट शामिल हैं। एक विशिष्ट स्थिति पर एक नोड को हटाने के लिए उस नोड के विपरीत की आवश्यकता होती है, जिसके परिणामस्वरूप एक O(n) ] जटिलता।

एक विशिष्ट तत्व खोजने के लिए एक लिंक्ड सूची को ट्रैक करना या अंत तक पहुंचने में एक बार प्रत्येक नोड का दौरा करना शामिल है, जिसके परिणामस्वरूप O(n) ] की रैखिक समय जटिलता होती है।

  • सिर पर प्रवेश: O(1)]
  • स्थिति में प्रवेशन: O(n)
  • सिर पर हटाने: O(1)]
  • स्थिति में विलंब: O(n)
  • अनुप्रस्थ/अनुसंधान: O(n)