तुम्ही Linked Lists वापरत नाही. पण ते तुमच्या अर्ध्या सॉफ्टवेअरला चालवत आहेत.

तुम्ही कदाचित एखाद्या प्रोडक्शन JavaScript प्रोजेक्टमध्ये कधीही linked list लिहिणार नाही. तुमच्या भाषेतील इन-बिल्ट arrays डायनॅमिक साईझिंग अधिक वेगाने हाताळतात. मुलाखतकार तुम्हाला व्हाईटबोर्डवर ते तयार करायला शिकवतात, पण यामुळे एक चुकीचा मानसिक दृष्टिकोन (mental model) तयार होतो.

तुम्ही linked lists फक्त ते लागू (implement) करण्यासाठी शिकू नये. तुम्ही ते दररोज वापरत असलेल्या साधनांना समजून घेण्यासाठी शिकले पाहिजे.

ते सर्वत्र आहेत: • ब्राउझरचे back आणि forward बटणे. • टेक्स्ट एडिटरची undo history. • वेब सर्व्हर्स आणि डेटाबेस मधील LRU caches. • Redis list commands. • Linux kernel process scheduler.

ते अवशेष नाहीत. ते पायाभूत सुविधा (infrastructure) आहेत.

linked lists च्या अडचणीचे खरे कारण 'cache locality' हे आहे. तुमचा CPU RAM मधून एका वेळी एक बाईट वाचत नाही. तो 'cache line' नावाचा ६४-बाईटचा तुकडा (chunk) एकत्र घेतो.

Arrays वेगाने काम करतात कारण ते मेमरीमध्ये एकत्र असतात. CPU पहिला घटक वाचतो आणि पुढचे १५ घटक विनामूल्य मिळवतो.

Linked lists हे वैशिष्ट्य नष्ट करतात. प्रत्येक node मेमरीमध्ये वेगवेगळ्या ठिकाणी असतो. एका pointer चा पाठलाग करताना CPU ला नवीन ॲड्रेसवर उडी मारावी लागते. यामुळे नवीन RAM fetch ट्रिगर होते. यासाठी शेकडो CPU cycles खर्च होतात.

आधुनिक हार्डवेअरवर, array traversal हे linked list traversal पेक्षा १० ते १०० पटीने वेगाने असू शकते. Big-O notation या स्थिर खर्चाकडे (constant cost) दुर्लक्ष करते.

मग तुम्ही त्यांचा वापर कधी करता?

stacks किंवा साध्या task queues साठी singly linked list वापरा, जिथे तुम्ही फक्त एका टोकाकडून घटक जोडता किंवा काढून टाकता.

जेव्हा तुम्हाला थेट node reference सह O(1) deletion हवे असते, तेव्हा doubly linked list वापरा. हेच LRU cache चे रहस्य आहे.

LRU cache साठी आवश्यक आहे:

  • O(1) lookup.
  • O(1) insertion.
  • O(1) eviction.
  • O(1) promotion.

Array हे करू शकत नाही कारण घटक हलवण्यासाठी इतर सर्व गोष्टी शिफ्ट (shift) कराव्या लागतात. केवळ hash map हे करू शकत नाही कारण त्याला कोणताही क्रम (order) नसतो.

याचे समाधान एक संयोजन (combination) आहे. Hash map 'lookup' प्रदान करते. Doubly linked list क्रम राखते. Hash map node reference साठवते. जेव्हा तुम्ही एखादी key ॲक्सेस करता, तेव्हा तुम्ही थेट list मधून तो node बाहेर काढता आणि त्याला सुरुवातीला नेता. कोणतीही शोधण्याची (searching) किंवा शिफ्ट करण्याची (shifting) गरज पडत नाही.

फक्त मुलाखती पास होण्यासाठी डेटा स्ट्रक्चर्स शिकणे थांबवा. सॉफ्टवेअर हार्डवेअरशी कसे संवाद साधते, हे समजून घेण्यासाठी ते शिका.

Source: https://dev.to/islamhafez0/you-dont-use-linked-lists-but-theyre-running-half-your-software-4b37