আপনি লিঙ্কড লিস্ট ব্যবহার করেন না। কিন্তু আপনার সফটওয়্যারের অর্ধেকই এগুলো দিয়ে চলছে।

আপনি সম্ভবত কোনো প্রোডাকশন JavaScript প্রজেক্টে কখনো লিঙ্কড লিস্ট লিখবেন না। আপনার ল্যাঙ্গুয়েজের বিল্ট-ইন অ্যারেগুলো (arrays) ডাইনামিক সাইজিং আরও দ্রুতভাবে হ্যান্ডেল করতে পারে। ইন্টারভিউয়াররা আপনাকে হোয়াইটবোর্ডে এগুলো তৈরি করতে শেখান, কিন্তু এটি একটি ভুল মানসিক ধারণা (mental model) তৈরি করে।

লিঙ্কড লিস্ট শুধু সেগুলো ইমপ্লিমেন্ট করার জন্য শেখা উচিত নয়। আপনি এগুলো শিখবেন প্রতিদিন ব্যবহৃত টুলগুলো বোঝার জন্য।

এগুলো সবখানেই আছে: • ব্রাউজারের ব্যাক (back) এবং ফরওয়ার্ড (forward) বাটন। • টেক্সট এডিটরের আনডু (undo) হিস্ট্রি। • ওয়েব সার্ভার এবং ডেটাবেসের LRU ক্যাশ (caches)। • Redis লিস্ট কমান্ড। • Linux কার্নেল প্রসেস শিডিউলার।

এগুলো কোনো সেকেলে জিনিস নয়। এগুলো হলো অবকাঠামো (infrastructure)।

লিঙ্কড লিস্টের সমস্যার আসল কারণ হলো ক্যাশ লোকালিটি (cache locality)। আপনার CPU একবারে মাত্র এক বাইট করে RAM থেকে ডেটা পড়ে না। এটি একটি ৬৪-বাইটের চাঙ্ক (chunk) নিয়ে আসে যাকে 'ক্যাশ লাইন' (cache line) বলা হয়।

অ্যারেগুলো দ্রুত কাজ করে কারণ সেগুলো মেমরিতে পাশাপাশি থাকে। CPU প্রথম এলিমেন্টটি পড়ার সাথে সাথেই পরবর্তী ১৫টি এলিমেন্ট বিনামূল্যে পেয়ে যায়।

লিঙ্কড লিস্ট এই সুবিধাটি নষ্ট করে দেয়। প্রতিটি নোড (node) মেমরির ভিন্ন ভিন্ন স্থানে থাকে। একটি পয়েন্টার অনুসরণ করতে CPU-কে নতুন একটি অ্যাড্রেসে লাফ দিতে হয়। এটি নতুন একটি RAM ফেচ (fetch) ট্রিগার করে, যা শত শত CPU সাইকেল খরচ করে ফেলে।

আধুনিক হার্ডওয়্যারে, লিঙ্কড লিস্ট ট্রাভার্সালের (traversal) তুলনায় অ্যারে ট্রাভার্সাল ১০ থেকে ১০০ গুণ বেশি দ্রুত হতে পারে। 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)।

একটি অ্যারে এটি করতে পারে না কারণ আইটেম মুভ করার জন্য বাকি সব কিছু শিফট (shift) করতে হয়। আবার শুধুমাত্র একটি হ্যাশ ম্যাপ (hash map) দিয়েও এটি সম্ভব নয় কারণ এতে কোনো ক্রম (order) থাকে না।

এর সমাধান হলো একটি সমন্বয়। একটি হ্যাশ ম্যাপ লুকআপ প্রদান করে। একটি ডাবলি লিঙ্কড লিস্ট ক্রম বজায় রাখে। হ্যাশ ম্যাপটি নোড রেফারেন্স সংরক্ষণ করে। যখন আপনি একটি কী (key) অ্যাক্সেস করেন, আপনি সরাসরি লিস্ট থেকে নোডটি নিয়ে সামনে নিয়ে আসেন। কোনো সার্চিং নয়। কোনো শিফটিং নয়।

শুধু ইন্টারভিউ পাস করার জন্য ডেটা স্ট্রাকচার শেখা বন্ধ করুন। সফটওয়্যার কীভাবে হার্ডওয়্যারের সাথে কাজ করে তা বোঝার জন্য এগুলো শিখুন।

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