आप Linked Lists का उपयोग नहीं करते। लेकिन वे आपके आधे सॉफ़्टवेयर को चला रहे हैं।
संभावना है कि आप किसी प्रोडक्शन JavaScript प्रोजेक्ट में कभी भी linked list नहीं लिखेंगे। आपकी भाषा के built-in arrays डायनामिक साइजिंग को तेज़ी से संभालते हैं। इंटरव्यू लेने वाले आपको व्हाइटबोर्ड पर इन्हें बनाना सिखाते हैं, लेकिन इससे एक गलत मानसिक मॉडल (mental model) बनता है।
आपको linked lists को लागू (implement) करने के लिए नहीं सीखना चाहिए। आप उन्हें उन टूल्स को समझने के लिए सीखते हैं जिनका आप हर दिन उपयोग करते हैं।
वे हर जगह हैं: • ब्राउज़र के बैक और फॉरवर्ड बटन। • टेक्स्ट एडिटर की undo हिस्ट्री। • वेब सर्वर और डेटाबेस में LRU caches। • Redis list commands। • Linux kernel process scheduler।
वे कोई अवशेष (relics) नहीं हैं। वे इंफ्रास्ट्रक्चर हैं।
Linked lists के संघर्ष करने का असली कारण cache locality है। आपका CPU RAM को एक बार में एक बाइट करके नहीं पढ़ता है। यह 64-बाइट का एक टुकड़ा खींचता है जिसे cache line कहा जाता है।
Arrays तेज़ होते हैं क्योंकि वे मेमोरी में एक साथ स्थित होते हैं। CPU पहले एलिमेंट को पढ़ता है और अगले 15 को मुफ्त में प्राप्त कर लेता है।
Linked lists इसे नष्ट कर देते हैं। प्रत्येक node मेमोरी के एक अलग स्थान पर स्थित होता है। एक pointer का अनुसरण करने के लिए CPU को एक नए पते (address) पर कूदने के लिए मजबूर होना पड़ता है। इससे एक नया RAM fetch शुरू हो जाता है। इसमें सैकड़ों CPU cycles खर्च होते हैं।
आधुनिक हार्डवेयर पर, array traversal, linked list traversal की तुलना में 10 से 100 गुना तेज़ हो सकता है। Big-O notation इस निरंतर लागत (constant cost) को नज़रअंदाज़ कर देता है।
तो आप इनका उपयोग कब करते हैं?
Stacks या सरल task queues के लिए singly linked list का उपयोग करें जहाँ आप केवल एक छोर से जोड़ते या हटाते हैं।
Doubly linked list का उपयोग तब करें जब आपको direct node reference के साथ O(1) deletion की आवश्यकता हो। यही LRU cache का रहस्य है।
एक LRU cache को चाहिए:
- O(1) lookup।
- O(1) insertion।
- O(1) eviction।
- O(1) promotion।
एक array ऐसा नहीं कर सकता क्योंकि आइटम्स को मूव करने के लिए बाकी सब कुछ शिफ्ट करना पड़ता है। केवल एक hash map भी ऐसा नहीं कर सकता क्योंकि इसमें कोई क्रम (order) नहीं होता।
समाधान एक संयोजन (combination) है। एक hash map lookup प्रदान करता है। एक doubly linked list क्रम बनाए रखती है। hash map node reference को स्टोर करता है। जब आप किसी key को एक्सेस करते हैं, तो आप सीधे list से node निकालते हैं और उसे सबसे आगे ले जाते हैं। कोई searching नहीं। कोई shifting नहीं।
केवल इंटरव्यू पास करने के लिए data structures सीखना बंद करें। उन्हें यह समझने के लिए सीखें कि सॉफ़्टवेयर हार्डवेयर के साथ कैसे इंटरैक्ट करता है।
स्रोत: https://dev.to/islamhafez0/you-dont-use-linked-lists-but-theyre-running-half-your-software-4b37