ನೀವು ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್‌ಗಳನ್ನು (Linked Lists) ಬಳಸುವುದಿಲ್ಲ. ಆದರೆ ಅವು ನಿಮ್ಮ ಸಾಫ್ಟ್‌ವೇರ್‌ನ ಅರ್ಧದಷ್ಟು ಭಾಗವನ್ನು ನಡೆಸುತ್ತಿವೆ.

ನೀವು ಪ್ರೊಡಕ್ಷನ್ JavaScript ಪ್ರಾಜೆಕ್ಟ್‌ನಲ್ಲಿ ಬಹುಶಃ ಎಂದಿಗೂ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಅನ್ನು ಬರೆಯುವುದಿಲ್ಲ. ನಿಮ್ಮ ಭಾಷೆಯ ಬಿಲ್ಟ್-ಇನ್ ಅರೇಗಳು (arrays) ಡೈನಾಮಿಕ್ ಸೈಸಿಂಗ್ ಅನ್ನು ವೇಗವಾಗಿ ನಿರ್ವಹಿಸುತ್ತವೆ. ಸಂದರ್ಶಕರು ವೈಟ್‌ಬೋರ್ಡ್‌ಗಳ ಮೇಲೆ ಅವುಗಳನ್ನು ಹೇಗೆ ನಿರ್ಮಿಸಬೇಕೆಂದು ನಿಮಗೆ ಕಲಿಸುತ್ತಾರೆ, ಆದರೆ ಇದು ತಪ್ಪು ಮಾನಸಿಕ ಮಾದರಿಯನ್ನು (mental model) ಸೃಷ್ಟಿಸುತ್ತದೆ.

ನೀವು ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್‌ಗಳನ್ನು ಕೇವಲ ಅವುಗಳನ್ನು ಅಳವಡಿಸಲು (implement) ಕಲಿಯಬಾರದು. ನೀವು ಪ್ರತಿದಿನ ಬಳಸುವ ಪರಿಕರಗಳನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಅವುಗಳನ್ನು ಕಲಿಯಬೇಕು.

ಅವು ಎಲ್ಲೆಡೆ ಇವೆ: • ಬ್ರೌಸರ್‌ನ ಬ್ಯಾಕ್ ಮತ್ತು ಫಾರ್ವರ್ಡ್ ಬಟನ್‌ಗಳು. • ಟೆಕ್ಸ್ಟ್ ಎಡಿಟರ್‌ನ ಅಂಡೂ (undo) ಇತಿಹಾಸ. • ವೆಬ್ ಸರ್ವರ್‌ಗಳು ಮತ್ತು ಡೇಟಾಬೇಸ್‌ಗಳಲ್ಲಿನ LRU ಕ್ಯಾಶೆಗಳು (caches). • Redis ಲಿಸ್ಟ್ ಕಮಾಂಡ್‌ಗಳು. • Linux ಕರ್ನಲ್ ಪ್ರೊಸೆಸ್ ಶೆಡ್ಯೂಲರ್.

ಅವು ಹಳೆಯ ಅವಶೇಷಗಳಲ್ಲ. ಅವು ಮೂಲಸೌಕರ್ಯಗಳು (infrastructure).

ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್‌ಗಳು ಹಿನ್ನಡೆ ಅನುಭವಿಸಲು ನಿಜವಾದ ಕಾರಣ 'ಕ್ಯಾಶ್ ಲೋಕಲಿಟಿ' (cache locality). ನಿಮ್ಮ CPU ಪ್ರತಿ ಬೈಟ್ ಅನ್ನು ಒಂದೊಂದಾಗಿ ಓದುವುದಿಲ್ಲ. ಅದು 'ಕ್ಯಾಶ್ ಲೈನ್' (cache line) ಎಂದು ಕರೆಯಲ್ಪಡುವ 64-ಬೈಟ್‌ನ ತುಣುಕನ್ನು ಒಟ್ಟಿಗೆ ಎತ್ತಿಕೊಳ್ಳುತ್ತದೆ.

ಅರೇಗಳು ವೇಗವಾಗಿರುತ್ತವೆ ಏಕೆಂದರೆ ಅವು ಮೆಮೊರಿಯಲ್ಲಿ ಒಟ್ಟಿಗೆ ಇರುತ್ತವೆ. CPU ಮೊದಲ ಎಲಿಮೆಂಟ್ ಅನ್ನು ಓದಿದಾಗ, ಮುಂದಿನ 15 ಎಲಿಮೆಂಟ್‌ಗಳನ್ನು ಉಚಿತವಾಗಿ ಪಡೆಯುತ್ತದೆ.

ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್‌ಗಳು ಇದನ್ನು ಹಾಳುಮಾಡುತ್ತವೆ. ಪ್ರತಿ ನೋಡ್ (node) ಮೆಮೊರಿಯ ವಿಭಿನ್ನ ಸ್ಥಳದಲ್ಲಿ ಇರುತ್ತದೆ. ಪಾಯಿಂಟರ್ ಅನ್ನು ಅನುಸರಿಸುವುದು CPU ಅನ್ನು ಹೊಸ ವಿಳಾಸಕ್ಕೆ (address) ಜಿಗಿಯುವಂತೆ ಮಾಡುತ್ತದೆ. ಇದು ಹೊಸ RAM ಫೆಚ್ ಅನ್ನು ಪ್ರಚೋದಿಸುತ್ತದೆ. ಇದು ನೂರಾರು CPU ಸೈಕಲ್‌ಗಳನ್ನು ವ್ಯಯಿಸುತ್ತದೆ.

ಆಧುನಿಕ ಹಾರ್ಡ್‌ವೇರ್‌ನಲ್ಲಿ, ಅರೇ ಟ್ರಾವರ್ಸಲ್ (array traversal) ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಟ್ರಾವರ್ಸಲ್ ಗಿಂತ 10 ರಿಂದ 100 ಪಟ್ಟು ವೇಗವಾಗಿರಬಹುದು. Big-O ನೋಟೇಶನ್ ಈ ಸ್ಥಿರ ವೆಚ್ಚವನ್ನು (constant cost) ನಿರ್ಲಕ್ಷಿಸುತ್ತದೆ.

ಹಾಗಾದರೆ ನೀವು ಅವುಗಳನ್ನು ಯಾವಾಗ ಬಳಸಬೇಕು?

ನೀವು ಕೇವಲ ಒಂದು ಬದಿಯಿಂದ ಮಾತ್ರ ಸೇರಿಸುವ ಅಥವಾ ತೆಗೆದುಹಾಕುವ ಸ್ಟ್ಯಾಕ್‌ಗಳು (stacks) ಅಥವಾ ಸರಳ ಟಾಸ್ಕ್ ಕ್ಯೂ (task queues) ಗಾಗಿ ಸಿಂಗಲಿ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ (singly linked list) ಬಳಸಿ.

ನೇರ ನೋಡ್ ರೆಫರೆನ್ಸ್‌ನೊಂದಿಗೆ O(1) ಡಿಲೀಷನ್ ಅಗತ್ಯವಿದ್ದಾಗ ಡೌಬ್ಲಿ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ (doubly linked list) ಬಳಸಿ. ಇದು LRU ಕ್ಯಾಶ್‌ನ ರಹಸ್ಯವಾಗಿದೆ.

ಒಂದು LRU ಕ್ಯಾಶ್‌ಗೆ ಇವು ಬೇಕು:

  • O(1) ಲುಕ್‌ಅಪ್ (lookup).
  • O(1) ಇನ್ಸರ್ಶನ್ (insertion).
  • O(1) ಎವಿಕ್ಷನ್ (eviction).
  • O(1) ಪ್ರಮೋಷನ್ (promotion).

ಅರೇ ಇದನ್ನು ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ ಏಕೆಂದರೆ ಐಟಂಗಳನ್ನು ಚಲಾಯಿಸಲು ಉಳಿದ ಎಲ್ಲವನ್ನೂ ಶಿಫ್ಟ್ ಮಾಡಬೇಕಾಗುತ್ತದೆ. ಹ್ಯಾಶ್ ಮ್ಯಾಪ್ (hash map) ಮಾತ್ರ ಇದನ್ನು ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ ಏಕೆಂದರೆ ಅದರಲ್ಲಿ ಯಾವುದೇ ಕ್ರಮ (order) ಇರುವುದಿಲ್ಲ.

ಇದಕ್ಕೆ ಪರಿಹಾರವೆಂದರೆ ಸಂಯೋಜನೆ (combination). ಹ್ಯಾಶ್ ಮ್ಯಾಪ್ ಲುಕ್‌ಅಪ್ ಅನ್ನು ಒದಗಿಸುತ್ತದೆ. ಡೌಬ್ಲಿ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಕ್ರಮವನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ. ಹ್ಯಾಶ್ ಮ್ಯಾಪ್ ನೋಡ್ ರೆಫರೆನ್ಸ್ ಅನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ನೀವು ಕೀಯನ್ನು (key) ಪ್ರವೇಶಿಸಿದಾಗ, ನೀವು ಲಿಸ್ಟ್‌ನಿಂದ ನೇರವಾಗಿ ನೋಡ್ ಅನ್ನು ಎತ್ತಿಕೊಂಡು ಅದನ್ನು ಮುಂಭಾಗಕ್ಕೆ ಸರಿಸುತ್ತೀರಿ. ಯಾವುದೇ ಹುಡುಕಾಟವಿಲ್ಲ (searching). ಯಾವುದೇ ಶಿಫ್ಟಿಂಗ್ ಇಲ್ಲ.

ಕೇವಲ ಸಂದರ್ಶನಗಳನ್ನು ಪಾಸ್ ಮಾಡಲು ಡೇಟಾ ಸ್ಟ್ರಕ್ಚರ್‌ಗಳನ್ನು ಕಲಿಯುವುದನ್ನು ನಿಲ್ಲಿಸಿ. ಸಾಫ್ಟ್‌ವೇರ್ ಹಾರ್ಡ್‌ವೇರ್‌ನೊಂದಿಗೆ ಹೇಗೆ ಸಂವಹನ ನಡೆಸುತ್ತದೆ ಎಂಬುದನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಅವುಗಳನ್ನು ಕಲಿಯಿರಿ.

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