آپ Linked Lists استعمال نہیں کرتے، لیکن وہ آپ کے آدھے سافٹ ویئر کو چلا رہی ہیں۔

غالباً آپ کسی پروڈکشن JavaScript پروجیکٹ میں کبھی Linked List نہیں لکھیں گے۔ آپ کی زبان کے بلٹ ان (built-in) arrays ڈائنامک سائزنگ کو زیادہ تیزی سے سنبھالتے ہیں۔ انٹرویو لینے والے آپ کو وائٹ بورڈ پر انہیں بنانا سکھاتے ہیں، لیکن یہ ایک غلط ذہنی تصور (mental model) پیدا کرتا ہے۔

آپ کو Linked Lists انہیں نافذ (implement) کرنے کے لیے نہیں سیکھنی چاہئیں۔ آپ انہیں ان ٹولز کو سمجھنے کے لیے سیکھتے ہیں جو آپ روزانہ استعمال کرتے ہیں۔

وہ ہر جگہ موجود ہیں: • براؤزر کے back اور forward بٹن۔ • ٹیکسٹ ایڈیٹر کی undo ہسٹری۔ • ویب سرورز اور ڈیٹا بیسز میں LRU caches۔ • Redis list commands۔ • Linux kernel process scheduler۔

یہ کوئی قدیم باقیات نہیں ہیں۔ یہ انفراسٹرکچر ہیں۔

Linked Lists کے ساتھ اصل مسئلہ cache locality کا ہے۔ آپ کا CPU RAM کو ایک وقت میں ایک بائٹ کے حساب سے نہیں پڑھتا۔ یہ 64-بائٹ کا ایک ٹکڑا اٹھاتا ہے جسے cache line کہا جاتا ہے۔

Arrays اس لیے تیز ہوتے ہیں کیونکہ وہ میموری میں ایک ساتھ ہوتے ہیں۔ CPU پہلے ایلیمنٹ کو پڑھتا ہے اور اگلے 15 ایلیمنٹس مفت میں حاصل کر لیتا ہے۔

Linked Lists اس عمل کو تباہ کر دیتی ہیں۔ ہر node میموری کے ایک مختلف مقام پر ہوتا ہے۔ ایک pointer کا پیچھا کرنے سے CPU کو ایک نئے ایڈریس پر چھلانگ لگانے پر مجبور ہونا پڑتا ہے۔ اس سے RAM سے نیا ڈیٹا منگوانا (fetch) پڑتا ہے، جس کی قیمت سینکڑوں CPU cycles کی صورت میں چکانی پڑتی ہے۔

جدید ہارڈ ویئر پر، array traversal، linked list traversal کے مقابلے میں 10 سے 100 گنا زیادہ تیز ہو سکتا ہے۔ Big-O notation اس مستقل لاگت (constant cost) کو نظر انداز کر دیتا ہے۔

تو آپ انہیں کب استعمال کرتے ہیں؟

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 ایسا نہیں کر سکتا کیونکہ آئٹمز کو منتقل کرنے کے لیے باقی تمام چیزوں کو شفٹ کرنا پڑتا ہے۔ صرف ایک hash map بھی ایسا نہیں کر سکتا کیونکہ اس میں کوئی ترتیب (order) نہیں ہوتی۔

اس کا حل ایک مجموعہ (combination) ہے۔ ایک hash map lookup فراہم کرتا ہے۔ ایک doubly linked list ترتیب کو برقرار رکھتی ہے۔ Hash map node reference کو محفوظ کرتا ہے۔ جب آپ کسی key تک رسائی حاصل کرتے ہیں، تو آپ براہ راست list سے node نکالتے ہیں اور اسے شروع میں لے جاتے ہیں۔ نہ کوئی تلاش، نہ کوئی شفٹنگ۔

صرف انٹرویوز پاس کرنے کے لیے data structures سیکھنا بند کریں۔ انہیں یہ سمجھنے کے لیے سیکھیں کہ سافٹ ویئر ہارڈ ویئر کے ساتھ کیسے تعامل (interact) کرتا ہے۔

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