તમે Linked Lists નો ઉપયોગ નથી કરતા. પરંતુ તે તમારા સોફ્ટવેરનો અડધો ભાગ ચલાવી રહ્યા છે.

તમે કદાચ ક્યારેય કોઈ પ્રોડક્શન JavaScript પ્રોજેક્ટમાં linked list લખશો નહીં. તમારી ભાષાના બિલ્ટ-ઇન arrays ડાયનેમિક સાઇઝિંગ વધુ ઝડપથી હેન્ડલ કરે છે. ઇન્ટરવ્યુઅર્સ તમને વ્હાઇટબોર્ડ પર તેને બનાવતા શીખવે છે, પરંતુ આ એક ખોટું માનસિક મોડેલ (mental model) બનાવે છે.

તમારે linked lists ને અમલમાં મૂકવા માટે શીખવું જોઈએ નહીં. તમારે તેને તમે દરરોજ જે સાધનોનો ઉપયોગ કરો છો તેને સમજવા માટે શીખવું જોઈએ.

તે દરેક જગ્યાએ છે: • બ્રાઉઝરના back અને forward બટનો. • ટેક્સ્ટ એડિટરની undo history. • વેબ સર્વર્સ અને ડેટાબેઝમાં LRU caches. • Redis list કમાન્ડ્સ. • Linux kernel process scheduler.

તેઓ અવશેષો નથી. તેઓ ઇન્ફ્રાસ્ટ્રક્ચર છે.

linked lists ને પડકાર આવવાનું સાચું કારણ cache locality છે. તમારું CPU RAM ને એક સમયે એક બાઇટ કરીને વાંચતું નથી. તે 64-બાઇટનો એક ટુકડો ખેંચે છે જેને cache line કહેવામાં આવે છે.

Arrays ઝડપી છે કારણ કે તેઓ મેમરીમાં સાથે રહે છે. CPU પ્રથમ એલિમેન્ટ વાંચે છે અને પછીના 15 એલિમેન્ટ્સ મફતમાં મેળવી લે છે.

Linked lists આને નષ્ટ કરે છે. દરેક node મેમરીના અલગ સ્પોટમાં હોય છે. પોઇન્ટરને ફોલો કરવાથી CPU ને નવા એડ્રેસ પર જંપવા માટે મજબૂર કરવામાં આવે છે. આનાથી નવું RAM fetch ટ્રિગર થાય છે. આમાં સેંકડો CPU cycles ખર્ચાય છે.

આધુનિક હાર્ડવેર પર, array traversal એ linked list traversal કરતા 10 થી 100 ગણું ઝડપી હોઈ શકે છે. Big-O notation આ સતત ખર્ચને અવગણે છે.

તો તમે તેનો ઉપયોગ ક્યારે કરો છો?

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 આ કરી શકતું નથી કારણ કે આઇટમ્સ ખસેડવા માટે બાકીની બધી વસ્તુઓને શિફ્ટ કરવી પડે છે. માત્ર hash map પણ આ કરી શકતું નથી કારણ કે તેમાં કોઈ ક્રમ (order) હોતો નથી.

તેનો ઉકેલ એક સંયોજન (combination) છે. Hash map લુકઅપ પૂરો પાડે છે. Doubly linked list ક્રમ જાળવી રાખે છે. Hash map node reference સ્ટોર કરે છે. જ્યારે તમે કોઈ key ને એક્સેસ કરો છો, ત્યારે તમે લિસ્ટમાંથી સીધો node ખેંચી લો છો અને તેને આગળ ખસેડો છો. કોઈ સર્ચિંગ નહીં. કોઈ શિફ્ટિંગ નહીં.

ફક્ત ઇન્ટરવ્યુ પાસ કરવા માટે ડેટા સ્ટ્રક્ચર્સ શીખવાનું બંધ કરો. સોફ્ટવેર હાર્ડવેર સાથે કેવી રીતે ઇન્ટરેક્ટ કરે છે તે સમજવા માટે તેને શીખો.

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