ਤੁਸੀਂ Linked Lists ਦੀ ਵਰਤੋਂ ਨਹੀਂ ਕਰਦੇ। ਪਰ ਉਹ ਤੁਹਾਡੇ ਅੱਧੇ ਸਾਫਟਵੇਅਰ ਨੂੰ ਚਲਾ ਰਹੇ ਹਨ।

ਸੰਭਵ ਹੈ ਕਿ ਤੁਸੀਂ ਕਿਸੇ production JavaScript ਪ੍ਰੋਜੈਕਟ ਵਿੱਚ ਕਦੇ ਵੀ linked list ਨਾ ਲਿਖੋ। ਤੁਹਾਡੀ ਭਾਸ਼ਾ ਦੇ built-in arrays dynamic sizing ਨੂੰ ਤੇਜ਼ੀ ਨਾਲ ਸੰਭਾਲਦੇ ਹਨ। ਇੰਟਰਵਿਊ ਲੈਣ ਵਾਲੇ ਤੁਹਾਨੂੰ ਵ੍ਹਾਈਟਬੋਰਡ 'ਤੇ ਇਹਨਾਂ ਨੂੰ ਬਣਾਉਣਾ ਸਿਖਾਉਂਦੇ ਹਨ, ਪਰ ਇਹ ਇੱਕ ਗਲਤ ਮਾਨਸਿਕ ਮਾਡਲ (mental model) ਬਣਾਉਂਦਾ ਹੈ।

ਤੁਹਾਨੂੰ linked lists ਨੂੰ ਲਾਗੂ (implement) ਕਰਨ ਲਈ ਨਹੀਂ ਸਿੱਖਣਾ ਚਾਹੀਦਾ। ਤੁਸੀਂ ਉਹਨਾਂ ਨੂੰ ਉਹਨਾਂ ਟੂਲਜ਼ ਨੂੰ ਸਮਝਣ ਲਈ ਸਿੱਖਦੇ ਹੋ ਜੋ ਤੁਸੀਂ ਹਰ ਰੋਜ਼ ਵਰਤਦੇ ਹੋ।

ਉਹ ਹਰ ਜਗ੍ਹਾ ਹਨ: • Browser ਦੇ back ਅਤੇ forward ਬਟਨ। • Text editor ਦੀ undo history। • Web servers ਅਤੇ databases ਵਿੱਚ LRU caches। • Redis list commands। • Linux kernel process scheduler।

ਉਹ ਕੋਈ ਪੁਰਾਣੀਆਂ ਯਾਦਗਾਰਾਂ ਨਹੀਂ ਹਨ। ਉਹ ਇਨਫਰਾਸਟ੍ਰਕਚਰ (infrastructure) ਹਨ।

Linked lists ਦੇ ਪਿੱਛੇ ਅਸਲ ਕਾਰਨ cache locality ਹੈ। ਤੁਹਾਡਾ CPU RAM ਨੂੰ ਇੱਕ ਵਾਰ ਵਿੱਚ ਇੱਕ ਬਾਈਟ (byte) ਨਹੀਂ ਪੜ੍ਹਦਾ। ਇਹ 64-byte ਦਾ ਇੱਕ ਟੁਕੜਾ ਖਿੱਚਦਾ ਹੈ ਜਿਸ ਨੂੰ cache line ਕਿਹਾ ਜਾਂਦਾ ਹੈ।

Arrays ਤੇਜ਼ ਹੁੰਦੇ ਹਨ ਕਿਉਂਕਿ ਉਹ ਮੈਮੋਰੀ ਵਿੱਚ ਇਕੱਠੇ ਹੁੰਦੇ ਹਨ। CPU ਪਹਿਲੇ element ਨੂੰ ਪੜ੍ਹਦਾ ਹੈ ਅਤੇ ਅਗਲੇ 15 ਬਿਲਕੁਲ ਮੁਫ਼ਤ ਵਿੱਚ ਪ੍ਰਾਪਤ ਕਰ ਲੈਂਦਾ ਹੈ।

Linked lists ਇਸ ਨੂੰ ਖ਼ਤਮ ਕਰ ਦਿੰਦੇ ਹਨ। ਹਰ node ਮੈਮੋਰੀ ਦੇ ਵੱਖਰੇ ਸਥਾਨ 'ਤੇ ਹੁੰਦਾ ਹੈ। ਇੱਕ pointer ਦਾ ਪਿੱਛਾ ਕਰਨ ਨਾਲ CPU ਨੂੰ ਇੱਕ ਨਵੇਂ ਪਤੇ (address) 'ਤੇ ਜਾਣਾ ਪੈਂਦਾ ਹੈ। ਇਹ ਇੱਕ ਨਵਾਂ RAM fetch ਸ਼ੁਰੂ ਕਰਦਾ ਹੈ। ਇਸ ਨਾਲ ਸੈਂਕੜੇ CPU cycles ਦਾ ਖਰਚਾ ਹੁੰਦਾ ਹੈ।

ਆਧੁਨਿਕ ਹਾਰਡਵੇਅਰ 'ਤੇ, array traversal, linked list traversal ਨਾਲੋਂ 10 ਤੋਂ 100 ਗੁਣਾ ਤੇਜ਼ ਹੋ ਸਕਦਾ ਹੈ। Big-O notation ਇਸ ਨਿਰੰਤਰ (constant) ਲਾਗਤ ਨੂੰ ਨਜ਼ਰਅੰਦਾਜ਼ ਕਰ ਦਿੰਦਾ ਹੈ।

ਤਾਂ ਤੁਸੀਂ ਉਹਨਾਂ ਦੀ ਵਰਤੋਂ ਕਦੋਂ ਕਰਦੇ ਹੋ?

Stacks ਜਾਂ ਸਧਾਰਨ task queues ਲਈ singly linked list ਦੀ ਵਰਤੋਂ ਕਰੋ ਜਿੱਥੇ ਤੁਸੀਂ ਸਿਰਫ਼ ਇੱਕ ਪਾਸੇ ਤੋਂ ਚੀਜ਼ਾਂ ਜੋੜਦੇ ਜਾਂ ਹਟਾਉਂਦੇ ਹੋ।

Doubly linked list ਦੀ ਵਰਤੋਂ ਉਦੋਂ ਕਰੋ ਜਦੋਂ ਤੁਹਾਨੂੰ ਇੱਕ ਸਿੱਧੇ node reference ਦੇ ਨਾਲ O(1) deletion ਦੀ ਲੋੜ ਹੋਵੇ। ਇਹ 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 order ਨੂੰ ਬਣਾਈ ਰੱਖਦੀ ਹੈ। Hash map node reference ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ। ਜਦੋਂ ਤੁਸੀਂ ਕਿਸੇ key ਨੂੰ access ਕਰਦੇ ਹੋ, ਤਾਂ ਤੁਸੀਂ list ਵਿੱਚੋਂ ਸਿੱਧਾ node ਕੱਢਦੇ ਹੋ ਅਤੇ ਉਸ ਨੂੰ ਸਭ ਤੋਂ ਅੱਗੇ ਲੈ ਆਉਂਦੇ ਹੋ। ਕੋਈ ਖੋਜ ਨਹੀਂ। ਕੋਈ shifting ਨਹੀਂ।

ਸਿਰਫ਼ ਇੰਟਰਵਿਊ ਪਾਸ ਕਰਨ ਲਈ data structures ਸਿੱਖਣਾ ਬੰਦ ਕਰੋ। ਇਹਨਾਂ ਨੂੰ ਇਹ ਸਮਝਣ ਲਈ ਸਿੱਖੋ ਕਿ ਸਾਫਟਵੇਅਰ ਹਾਰਡਵੇਅਰ ਨਾਲ ਕਿਵੇਂ ਮੇਲ ਖਾਂਦਾ ਹੈ (interacts ਕਰਦਾ ਹੈ)।

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