लिंक किए गए सूची को 1 मिलियन नोड्स के साथ कैसे कार्यान्वित करें?

Question

मैंने हाल ही में माइक्रोसॉफ्ट साक्षात्कार में भाग लिया।

मुझे लिंक किए गए सूची को 1 मिलियन नोड्स के साथ लागू करने के लिए कहा गया था? आप 99 99 99 वें नोड तक कैसे पहुंचेंगे?

ऐसे प्रश्न के लिए इष्टतम डिजाइन रणनीति और कार्यान्वयन क्या है?

Answer 1

एक लिंक्ड सूची में काफी कुछ भिन्नताएं हैं, क्योंकि बहुत भिन्नता का मतलब है कि यह एक लिंक की गई सूची के अलावा कुछ और होगा।

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

यदि आपके पास एक डबल लिंक्ड सूची है तो सूची पूंछ (अंतिम नोड) के साथ-साथ सिर के लिए एक सूचक को बनाए रखना अर्थपूर्ण है, जिसका मतलब है कि अंतिम तत्व तक पहुंच सस्ता है, और अंत के तत्व सस्ता हैं, क्योंकि आप पीछे या आगे काम कर सकते हैं ... लेकिन ... आपको यह जानना होगा कि आप सूची के अंत में क्या चाहते हैं ... और दिन के अंत में एक लिंक की गई सूची अभी भी है, और यदि यह बहुत बड़ा हो रहा है और यह इसके उपयोग के मामले की प्रकृति की वजह से एक समस्या है, तो एक लिंक्ड सूची के अलावा एक भंडारण संरचना शायद चुना जाना चाहिए।

आप अपनी लिंक्ड सूची को संकरित कर सकते हैं, ताकि आप इसे उदाहरण के लिए या कुछ उदाहरण दे सकें, और सिद्धांत में इसके साथ कुछ भी गलत नहीं है, लेकिन यदि आप सभी नोड्स को इंडेक्स करते हैं तो लिंक की गई सूची प्रकृति अब अधिक मूल्य नहीं है , और यदि आप केवल कुछ इंडेक्स करते हैं, तो अनुक्रमित नोड्स के बीच नोड्स को सॉर्ट किया जाना चाहिए या कुछ ऐसा है ताकि आप एक करीबी नोड पा सकें और लक्ष्य नोड की ओर काम कर सकें ... शायद यह कभी भी इष्टतम नहीं होगा और बेहतर डेटा संरचना होना चाहिए चुना।

वास्तव में एक लिंक की गई सूची का उपयोग तब किया जाना चाहिए जब आप एक विशिष्ट नोड प्राप्त करने जैसी चीजें नहीं करना चाहते हैं, लेकिन बिना किसी नोड को फिर से चालू करना चाहते हैं।

Answer 2

मुझे लगता है मैं क्या कहने जा रहा हूँ के बारे में पता नहीं है, लेकिन, यहाँ जाता है:

आप कर सकते थे conceptually विभाजित है कि आप "संदर्भ संकेत" होता sqrt(1000000)ब्लॉक, इस तरह से में सूची हर 1000 तत्व। 1000 elements साथ 1000 linked lists प्रत्येक होने 1000000 elements के साथ अपनी सूची का प्रतिनिधित्व के रूप में यह की

Think।

यह दिमाग में आता है!

Answer 3

जैसा कि माइकल ने कहा था कि आपको पहले लिंक की गई सूची के दो क्लासिक बदलाव प्रस्तुत करना चाहिए। अगली चीज़ जो आपको करना चाहिए वह सम्मिलन, खोज और हटाने के पैटर्न के बारे में पूछना है।

ये पैटर्न आपको एक बेहतर फिट डेटा संरचना की दिशा में मार्गदर्शन करेंगे, क्योंकि कोई भी एक मिलियन नोड्स के साथ एक साधारण या डबल लिंक्ड सूची चाहता है।