நீங்கள் Linked Lists-களைப் பயன்படுத்துவதில்லை. ஆனால் அவை உங்கள் மென்பொருளின் பாதியை இயக்குகின்றன.

ஒரு production JavaScript திட்டத்தில் நீங்கள் ஒருபோதும் ஒரு linked list-ஐ எழுத மாட்டீர்கள். உங்கள் மொழியில் உள்ள built-in arrays, dynamic sizing-ஐ மிக வேகமாக கையாளுகின்றன. நேர்காணல் செய்பவர்கள் அவற்றை வெள்ளைப்பலகையில் (whiteboards) உருவாக்குவது எப்படி என்று கற்றுக்கொடுக்கிறார்கள், ஆனால் இது ஒரு தவறான புரிதலை (mental model) உருவாக்குகிறது.

நீங்கள் linked lists-களை அவற்றைச் செயல்படுத்துவதற்காகக் கற்க வேண்டியதில்லை. நீங்கள் தினமும் பயன்படுத்தும் கருவிகளைப் புரிந்துகொள்வதற்காகவே அவற்றைக் கற்க வேண்டும்.

அவை எங்கும் உள்ளன: • Browser-ன் back மற்றும் forward பொத்தான்கள். • Text editor-ன் undo வரலாறு. • Web servers மற்றும் databases-ல் உள்ள LRU caches. • Redis list commands. • Linux kernel process scheduler.

அவை பழங்கால எச்சங்கள் அல்ல. அவை உள்கட்டமைப்பு (infrastructure).

Linked lists-கள் பின்தங்கியிருப்பதற்குக் காரணம் cache locality ஆகும். உங்கள் CPU, RAM-லிருந்து ஒரு நேரத்தில் ஒரு பைட்டை (byte) மட்டும் வாசிப்பதில்லை. அது 'cache line' என்று அழைக்கப்படும் 64-byte அளவுள்ள ஒரு தொகுப்பையே (chunk) எடுத்துக்கொள்கிறது.

Arrays வேகமானவை, ஏனெனில் அவை நினைவகத்தில் (memory) அருகருகே அமைந்துள்ளன. CPU முதல் உறுப்பை (element) வாசிக்கும்போதே, அடுத்த 15 உறுப்புகளையும் இலவசமாகப் பெற்றுவிடுகிறது.

Linked lists இதைச் சிதைத்துவிடுகின்றன. ஒவ்வொரு node-ம் வெவ்வேறு நினைவக இடத்தில்தான் அமர்ந்திருக்கும். ஒரு pointer-ஐப் பின்பற்றுவது, CPU-வை ஒரு புதிய முகவரிக்கு (address) தாவச் செய்கிறது. இது ஒரு புதிய RAM fetch-ஐத் தூண்டுகிறது. இதற்கு நூற்றுக்கணக்கான CPU cycles செலவாகின்றன.

நவீன வன்பொருள்களில் (modern hardware), array traversal என்பது linked list traversal-ஐ விட 10 முதல் 100 மடங்கு வேகமாக இருக்கலாம். 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-ஆல் இதைச் செய்ய முடியாது, ஏனெனில் உறுப்புகளை நகர்த்துவதற்கு மற்ற அனைத்தையும் இடமாற்றம் (shifting) செய்ய வேண்டியிருக்கும். ஒரு hash map மட்டும் இதைச் செய்ய முடியாது, ஏனெனில் அதற்கு வரிசை முறை (order) கிடையாது.

இதற்கான தீர்வு ஒரு கலவை (combination) ஆகும். ஒரு hash map தேடலை (lookup) வழங்குகிறது. ஒரு doubly linked list வரிசை முறையைப் பராமரிக்கிறது. Hash map, node reference-ஐச் சேமித்து வைக்கிறது. நீங்கள் ஒரு key-ஐ அணுகும்போது, அந்த node-ஐ நேரடியாக list-லிருந்து எடுத்து முன்னால் நகர்த்துகிறீர்கள். தேட வேண்டிய அவசியமில்லை. இடமாற்றம் (shifting) செய்ய வேண்டிய அவசியமில்லை.

நேர்காணல்களைத் தேர்ச்சி பெறுவதற்காக மட்டும் data structures-களைக் கற்பதை நிறுத்துங்கள். மென்பொருள் வன்பொருளுடன் (hardware) எவ்வாறு தொடர்பு கொள்கிறது என்பதைப் புரிந்துகொள்ள அவற்றைக் கற்றுக்கொள்ளுங்கள்.

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