🥚 🏇🏽 🤟 एक लिंक की गई सूची को फैलाएं। स्विफ्ट संस्करण ✊🏽 🦕 🖖🏾

यह कोई रहस्य नहीं है कि सॉफ्टवेयर डेवलपर के लिए पसंदीदा अतीत में से एक नियोक्ताओं का साक्षात्कार कर रहा है। हम सभी समय-समय पर और पूरी तरह से अलग कारणों से ऐसा करते हैं। और उनमें से सबसे स्पष्ट - नौकरी की खोज - मुझे लगता है, सबसे आम नहीं है। एक साक्षात्कार में भाग लेने के लिए फिट रखने के लिए एक अच्छा तरीका है, भूल गए मूल बातें दोहराएं और कुछ नया सीखें। और सफल होने पर आत्मविश्वास भी बढ़ाएं। हम ऊब गए हैं, हमने अपने आप को "लिंक्डइन" जैसे किसी भी तरह के "व्यापार" सामाजिक नेटवर्क में "ऑफ़र की खुली" की स्थिति निर्धारित की है - और मानव संसाधन प्रबंधकों की सेना पहले से ही आने वाले संदेशों के लिए हमारे इनबॉक्स पर हमला कर रही है।

इस प्रक्रिया में, जबकि यह सब बेडलैम चल रहा है, हमें कई सवालों का सामना करना पड़ रहा है, जैसा कि वे स्पष्ट रूप से ढह गए पर्दे के दूसरी तरफ कहते हैं, "रिंग अ बेल" हैं, और उनका विवरण युद्ध के कोहरे के पीछे छिपा है। उन्हें अक्सर केवल एल्गोरिदम और डेटा संरचनाओं द्वारा परीक्षणों पर याद किया जाता है (व्यक्तिगत रूप से, मेरे पास ऐसा कोई डेटा नहीं है) और वास्तव में साक्षात्कार।

किसी भी विशेषज्ञता के प्रोग्रामर के लिए एक साक्षात्कार में सबसे आम सवालों में से एक सूची है। उदाहरण के लिए, एकल लिंक की गई सूचियाँ। और संबंधित बुनियादी एल्गोरिदम। उदाहरण के लिए, एक यू-टर्न। और आमतौर पर यह किसी भी तरह से होता है: "अच्छा है, लेकिन आप एक एकल लिंक की गई सूची का विस्तार कैसे करेंगे?" मुख्य बात यह है कि इस सवाल से आश्चर्यचकित होकर आवेदक को पकड़ा जाए।

वास्तव में, इस सबने मुझे निरंतर अनुस्मारक और संपादन के लिए इस संक्षिप्त समीक्षा को लिखने के लिए प्रेरित किया। तो, एक तरफ मजाक करता है, निहारना!

एकल रूप से जुड़ी हुई सूची

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

सूचियों के बारे में कहा जाने वाला बहुत कुछ है, ज़ाहिर है: वे परिपत्र हो सकते हैं (यानी, अंतिम तत्व पहले के लिए एक लिंक संग्रहीत करता है) या नहीं (यानी अंतिम तत्व के लिए कोई लिंक नहीं है)। सूची टाइप की जा सकती है, अर्थात एक ही प्रकार के डेटा शामिल हैं या नहीं। वगैरह वगैरह।

कुछ कोड लिखने का बेहतर प्रयास करें। उदाहरण के लिए, किसी तरह आप एक सूची नोड की कल्पना कर सकते हैं:

final class Node<T> { let payload: T var nextNode: Node? init(payload: T, nextNode: Node? = nil) { self.payload = payload self.nextNode = nextNode } }

"जेनेरिक" एक प्रकार है जो payload क्षेत्र में किसी भी प्रकार के पेलोड को स्टोर करने में सक्षम है।

सूची को पहले नोड द्वारा अपने आप पहचाना जाता है:

 final class SinglyLinkedList<T> { var firstNode: Node<T>? init(firstNode: Node<T>? = nil) { self.firstNode = firstNode } }

पहला नोड वैकल्पिक घोषित किया गया है, क्योंकि सूची अच्छी तरह से खाली हो सकती है।

सिद्धांत रूप में, निश्चित रूप से, कक्षा में आपको सभी आवश्यक विधियों को लागू करने की आवश्यकता होती है - सम्मिलन, विलोपन, नोड्स तक पहुंच आदि, लेकिन हम इसे कुछ और समय करेंगे। उसी समय, हम यह जांच करेंगे कि क्या struct का उपयोग करना (जो कि Apple सक्रिय रूप से हमारे उदाहरण से हमें प्रोत्साहित करता है) एक बेहतर विकल्प है, और शायद "कॉपी-ऑन-राइट" दृष्टिकोण को याद करते हैं।

एकल-लिंक सूची फैली हुई है

पहला तरीका। चक्र

आज हम यहाँ हैं, जिसके लिए व्यवसाय में उतरने का समय आ गया है! और इससे निपटने का सबसे प्रभावी तरीका दो तरीके हैं। पहला एक साधारण लूप है, पहली से आखिरी नोड तक।

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

शब्दों में, निश्चित रूप से, यह सब अजीब और समझ से बाहर है, इसलिए बेहतर कोड देखें:

 extension SinglyLinkedList { func reverse() { var previousNode: Node<T>? = nil var currentNode = firstNode var nextNode = firstNode?.nextNode while nextNode != nil { currentNode?.nextNode = previousNode previousNode = currentNode currentNode = nextNode nextNode = currentNode?.nextNode } currentNode?.nextNode = previousNode firstNode = currentNode } }

सत्यापन के लिए, हम उन नोड्स की एक सूची का उपयोग करते हैं जिनके पेलोड सरल पूर्णांक पहचानकर्ता हैं। दस तत्वों की सूची बनाएँ:

 let node = Node(payload: 0) // T == Int let list = SinglyLinkedList(firstNode: node) var currentNode = node var nextNode: Node<Int> for id in 1..<10 { nextNode = Node(payload: id) currentNode.nextNode = nextNode currentNode = nextNode }

सब कुछ ठीक लग रहा है, लेकिन आप और मैं लोग हैं, कंप्यूटर नहीं, और यह हमारे लिए अच्छा होगा कि बनाई गई सूची की शुद्धता और ऊपर वर्णित एल्गोरिथ्म का एक दृश्य प्रमाण प्राप्त करें। शायद एक साधारण प्रिंट पर्याप्त होगा। आउटपुट को पठनीय बनाने के लिए, पूर्णांक पहचानकर्ता के साथ नोड में CustomStringConvertible प्रोटोकॉल का कार्यान्वयन जोड़ें:

 extension Node: CustomStringConvertible where T == Int { var description: String { let firstPart = """ Node \(Unmanaged.passUnretained(self).toOpaque()) has id \(payload) and """ if let nextNode = nextNode { return firstPart + " next node \(nextNode.payload)." } else { return firstPart + " no next node." } } }

... और क्रम में सभी नोड्स प्रदर्शित करने के लिए संबंधित सूची:

 extension SinglyLinkedList: CustomStringConvertible where T == Int { var description: String { var description = """ List \(Unmanaged.passUnretained(self).toOpaque()) """ if firstNode != nil { description += " has nodes:\n" var node = firstNode while node != nil { description += (node!.description + "\n") node = node!.nextNode } return description } else { return description + " has no nodes." } } }

हमारे प्रकारों के स्ट्रिंग प्रतिनिधित्व में मेमोरी में एक पता और एक पूर्णांक पहचानकर्ता होगा। उनका उपयोग करते हुए, हम दस नोड्स की उत्पन्न सूची के मुद्रण का आयोजन करते हैं:

 print(String(describing: list)) /* List 0x00006000012e1a60 has nodes: Node 0x00006000012e2380 has id 0 and next node 1. Node 0x00006000012e8d40 has id 1 and next node 2. Node 0x00006000012e8d20 has id 2 and next node 3. Node 0x00006000012e8ce0 has id 3 and next node 4. Node 0x00006000012e8ae0 has id 4 and next node 5. Node 0x00006000012e89a0 has id 5 and next node 6. Node 0x00006000012e8900 has id 6 and next node 7. Node 0x00006000012e8a40 has id 7 and next node 8. Node 0x00006000012e8a60 has id 8 and next node 9. Node 0x00006000012e8820 has id 9 and no next node. */

इस सूची का विस्तार करें और इसे फिर से प्रिंट करें:

 list.reverse() print(String(describing: list)) /* List 0x00006000012e1a60 has nodes: Node 0x00006000012e8820 has id 9 and next node 8. Node 0x00006000012e8a60 has id 8 and next node 7. Node 0x00006000012e8a40 has id 7 and next node 6. Node 0x00006000012e8900 has id 6 and next node 5. Node 0x00006000012e89a0 has id 5 and next node 4. Node 0x00006000012e8ae0 has id 4 and next node 3. Node 0x00006000012e8ce0 has id 3 and next node 2. Node 0x00006000012e8d20 has id 2 and next node 1. Node 0x00006000012e8d40 has id 1 and next node 0. Node 0x00006000012e2380 has id 0 and no next node. */

आप देख सकते हैं कि सूची और नोड्स की स्मृति में पते नहीं बदले गए हैं, और सूची के नोड्स रिवर्स ऑर्डर में मुद्रित किए गए हैं। नोड के अगले तत्व के लिंक अब पिछले एक को इंगित करते हैं (उदाहरण के लिए, नोड "5" का अगला तत्व अब "6" नहीं है, लेकिन "4")। और इसका मतलब है कि हमने यह किया!

दूसरा तरीका। प्रत्यावर्तन

उसी यू-टर्न को करने का दूसरा ज्ञात तरीका पुनरावृत्ति पर आधारित है। इसे लागू करने के लिए, हम एक फ़ंक्शन घोषित करेंगे जो सूची के पहले नोड को लेता है, और "नया" पहला नोड लौटाता है (जो कि पहले अंतिम था)।

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

वास्तव में, मैंने ईमानदारी से शब्दों में पूर्ण एल्गोरिथ्म का वर्णन करने की कोशिश की, लेकिन अंत में मैंने लगभग सब कुछ मिटा दिया, क्योंकि परिणाम को समझना असंभव होगा। फ़्लोचार्ट्स को ड्रा करने के लिए और एल्गोरिथम के चरणों का औपचारिक रूप से वर्णन करें - साथ ही, इस मामले में, मुझे लगता है कि इसका कोई मतलब नहीं है, क्योंकि यह आपके और मेरे लिए सिर्फ पढ़ने और स्विफ्ट कोड को समझने के लिए अधिक सुविधाजनक होगा:

 extension SinglyLinkedList { func reverseRecursively() { func reverse(_ node: Node<T>?) -> Node<T>? { guard let head = node else { return node } if head.nextNode == nil { return head } let reversedHead = reverse(head.nextNode) head.nextNode?.nextNode = head head.nextNode = nil return reversedHead } firstNode = reverse(firstNode) } }

एल्गोरिथ्म ही कॉलिंग की सुविधा के लिए वास्तविक सूची के प्रकार की एक विधि द्वारा "लिपटे" है।

यह छोटा लगता है, लेकिन, मेरी राय में, समझना मुश्किल है।

हम पिछले प्रसार के परिणाम पर इस विधि को कहते हैं और एक नया परिणाम प्रिंट करते हैं:

 list.reverseRecursively() print(String(describing: list)) /* List 0x00006000012e1a60 has nodes: Node 0x00006000012e2380 has id 0 and next node 1. Node 0x00006000012e8d40 has id 1 and next node 2. Node 0x00006000012e8d20 has id 2 and next node 3. Node 0x00006000012e8ce0 has id 3 and next node 4. Node 0x00006000012e8ae0 has id 4 and next node 5. Node 0x00006000012e89a0 has id 5 and next node 6. Node 0x00006000012e8900 has id 6 and next node 7. Node 0x00006000012e8a40 has id 7 and next node 8. Node 0x00006000012e8a60 has id 8 and next node 9. Node 0x00006000012e8820 has id 9 and no next node. */

यह आउटपुट से देखा जा सकता है कि मेमोरी में सभी पते फिर से नहीं बदले हैं, और नोड्स अब मूल क्रम में अनुसरण करते हैं (अर्थात, वे "फिर से तैनात" हैं)। और इसका मतलब है कि हम इसे फिर से मिल गया!

निष्कर्ष

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

सामान्यतया, वर्णित दो एल्गोरिदम को इस समस्या को हल करने के लिए सबसे प्रभावी माना जाता है। कम्प्यूटेशनल जटिलता के लिए, कम मूल्य के साथ एक एल्गोरिथ्म के साथ आना संभव नहीं है: एक तरह से या किसी अन्य, आपको लिंक के अंदर संग्रहीत एक नए मूल्य को असाइन करने के लिए प्रत्येक नोड को "विज़िट" करने की आवश्यकता है।

उल्लेख के लायक एक और विशेषता "आवंटित स्मृति जटिलता" है। दोनों प्रस्तावित एल्गोरिदम एक निश्चित संख्या में नए चर बनाते हैं (पहले मामले में तीन और दूसरे में एक)। इसका मतलब है कि आवंटित मेमोरी की मात्रा इनपुट डेटा की मात्रात्मक विशेषताओं पर निर्भर नहीं करती है और इसे एक स्थिर फ़ंक्शन - ओ (1) द्वारा वर्णित किया गया है।

लेकिन, वास्तव में, दूसरे मामले में ऐसा नहीं है। पुनरावृत्ति का खतरा यह है कि स्टैक पर प्रत्येक पुनरावर्ती कॉल के लिए अतिरिक्त मेमोरी आवंटित की जाती है। हमारे मामले में, पुनरावृत्ति की गहराई इनपुट डेटा की मात्रा से मेल खाती है।

और अंत में, मैंने थोड़ा और प्रयोग करने का फैसला किया: एक सरल और आदिम तरीके से मैंने इनपुट डेटा की एक अलग राशि के लिए दो तरीकों का पूर्ण निष्पादन समय मापा। इस तरह:

 let startDate = Date().timeIntervalSince1970 // list.reverse() / list.reverseRecursively() let finishDate = Date().timeIntervalSince1970 let runningTime = finishDate – startDate // Seconds

और यही मुझे मिला (यह प्लेग्राउंड का कच्चा डेटा है):

(दुर्भाग्य से, मेरे कंप्यूटर ने बड़े मूल्यों में महारत हासिल नहीं की है।)

तालिका से क्या देखा जा सकता है? अभी तक कुछ खास नहीं हुआ। हालांकि यह पहले से ही ध्यान देने योग्य है कि पुनरावर्ती विधि अपेक्षाकृत कम संख्या में नोड्स के साथ थोड़ा खराब व्यवहार करती है, लेकिन कहीं न कहीं 100 और 1000 के बीच यह बेहतर दिखाने के लिए शुरू होता है।

मैंने एक पूर्ण सरल "Xcode" प्रोजेक्ट के अंदर एक ही सरल परीक्षण का भी प्रयास किया। परिणाम इस प्रकार हैं:

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

निष्कर्ष

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

अगर किसी को मेरी सामाजिक गतिविधि को ट्रैक करने की इच्छा है, तो यहां मेरे "ट्विटर" के लिए एक लिंक है, जहां सबसे पहले मेरी नई पोस्ट के लिंक और कुछ और हैं।

एक लिंक की गई सूची को फैलाएं। स्विफ्ट संस्करण

एकल रूप से जुड़ी हुई सूची

एकल-लिंक सूची फैली हुई है

पहला तरीका। चक्र

दूसरा तरीका। प्रत्यावर्तन

निष्कर्ष

निष्कर्ष

More articles: