Question:
What is the time complexity to insert a new node at the end of a singly linked list if only the head pointer is maintained?
यदि केवल हेड (Head) पॉइंटर बनाए रखा गया हो, तो सिंगल लिंक्ड लिस्ट के अंत में एक नया नोड डालने की समय जटिलता (Time complexity) क्या होगी?
Options:
- \(O(n)\)
- \(O(1)\)
- \(O(\log n)\)
- \(O(n^2)\)
- \(O(n)\)
- \(O(1)\)
- \(O(\log n)\)
- \(O(n^2)\)
Correct Answer: a)
Explanation:
Without a tail pointer, one must traverse all \(n\) nodes from the head to find the last node, requiring **\(O(n)\)** time. (If a tail pointer is maintained, it is \(O(1)\)) (Option a).
टेल पॉइंटर न होने पर हेड से शुरू करके अंत तक सभी \(n\) नोड्स को पार करना पड़ता है, इसलिए समय जटिलता **\(O(n)\)** होती है (विकल्प a)।