সিঙ্গলি লিংকড লিস্ট
ধরুন আপনি গুপ্তধন খুঁজছেন। আপনাকে প্রথম একটা ক্লু (clue) বা চিরকুট দেওয়া হলো। সেই চিরকুটে গুপ্তধন নেই — সেখানে লেখা আছে পরের চিরকুটটা কোথায় পাবেন। পরেরটা আপনাকে তার পরেরটার ঠিকানা দেবে, আর এভাবেই চলতে চলতে একদম শেষের চিরকুটে লেখা থাকবে "এখানেই গুপ্তধন লুকানো আছে!"
একটা সিঙ্গলি লিংকড লিস্ট (Singly Linked List) ঠিক এভাবেই কাজ করে। এখানকার প্রতিটা আইটেমকে বলা হয় নোড (Node), যা মূলত ছোট একটা বাক্স। আর এই বাক্সে দুটো জিনিস থাকে: একটা হলো ভ্যালু (আসল ডেটা বা গুপ্তধন) এবং অন্যটা হলো পয়েন্টার (ভেতরের চিরকুট, যেটা বলে দেয় শেকলের পরের বাক্সটা কোথায়)। একদম শেষের নোডের পয়েন্টারে লেখা থাকে null — মানে হলো, শেকল এখানেই শেষ।
এখানে ঢোকার একটাই রাস্তা, আর সেটা হলো হেড (Head) পয়েন্টার। এই হেড সবসময় একদম প্রথম নোডটাকে চেনে। অন্য যেকোনো নোডে যেতে হলে আপনাকে এই হেড থেকেই শুরু করতে হবে, আর চিরকুট পড়ে পড়ে একটা একটা করে বাক্স পার হতে হবে।
অ্যারের সাথে এর পার্থক্য কী?
অ্যারেতে, সবগুলো বাক্স মেমোরিতে পাশাপাশি গা ঘেঁষে বসে থাকে — আপনি চাইলেই লাফ দিয়ে ৫ নম্বর বাক্সে চলে যেতে পারেন। কিন্তু লিংকড লিস্টে বাক্সগুলো মেমোরির যেখানে-সেখানে ছড়ানো-ছিটানো থাকতে পারে। ওদের মধ্যে একমাত্র যোগাযোগ হলো ওই পয়েন্টার বা চিরকুট। এর কারণে মাঝখানের কাউকে খুঁজে পাওয়াটা একটু স্লো বা সময়সাপেক্ষ কাজ, কিন্তু একদম সামনে নতুন কাউকে যোগ করা বা বাদ দেওয়া রকেটের গতিতে করা যায়।
← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন
কাউকে খুঁজে পাওয়া (Access) কেন O(n) হয়?
আপনার ৪ নম্বর নোডটা লাগবে? কোনো শর্টকাট নেই ভাই। আপনাকে হেড থেকে শুরু করতে হবে, তার পয়েন্টার ধরে ২ নম্বরে যেতে হবে, সেখান থেকে ৩ নম্বরে, তারপর ৪ নম্বরে। প্রতিটা ধাপ পেরোতে আপনকে একটা করে পয়েন্টার পড়তে হবে। লিস্টে যদি ১০০০টা নোড থাকে আর আপনার শেষেরটা লাগে, তবে আপনাকে ১০০০টা চিরকুট পড়তে হবে। এটাকে বলা হয় O(n) — মানে লিস্ট যত বড় হবে, খুঁজতে সময় তত বেশি লাগবে।
অ্যারের সাথে তুলনা করলে: arr[999] হলো চোখের পলকে কাজ, কারণ কম্পিউটার গাণিতিক হিসাব করে সরাসরি ওই জায়গায় চলে যেতে পারে। লিংকড লিস্ট এই সুপারপাওয়ারটা বিসর্জন দিয়েছে শুধু একটা কারণে: অনেক বেশি ফ্লেক্সিবিলিটি বা নমনীয়তা পাওয়ার জন্য।
একদম সামনে (Head) কিছু যোগ করা কেন O(1)?
আসল ম্যাজিকটা এখানেই। একদম সামনে নতুন একটা নোড যোগ করতে আপনার শুধু দুটো কাজ করতে হবে:
- নতুন নোডের চিরকুটে (পয়েন্টার) বলে দিন যে সে বর্তমান হেডকে চেনে।
- এবার হেড পয়েন্টারকে আপডেট করে নতুন নোডটার দিকে ঘুরিয়ে দিন।
ব্যস, এটুকুতেই কাজ শেষ — শেকল যত বড়ই হোক না কেন, মাত্র দুটো পয়েন্টার চেঞ্জ করলেই হলো। কাউকে ধাক্কা দিয়ে সরাতে হবে না, কপি করতে হবে না। পেছনের বাকি নোডগুলো টেরও পাবে না যে সামনে কী ঘটে গেল!
নোড ডিলিট বা মুছে ফেলা
মাঝখান থেকে কোনো নোড মুছে ফেলার জন্য, প্রথমে আপনাকে সেটা খুঁজে বের করতে হবে — এই খোঁজার কাজের সময় হলো O(n)। একবার খুঁজে পেয়ে গেলে আর তার ঠিক আগের নোডটাকে ধরতে পারলে ডিলিট করাটা জাস্ট পয়েন্টার ঘোরানোর খেলা: আগের নোডের পয়েন্টারকে ডিলিট হওয়া নোডটার পরেরটার দিকে ঘুরিয়ে দিন। এখানে ডিলিট করার কাজটা O(1), কিন্তু ওই পর্যন্ত হেঁটে যানয়ার কাজটা O(n)।
Complexity
সিঙ্গলি লিংকড লিস্ট কখন ব্যবহার করবেন?
- যখন আপনাকে বারবার ডেটার একদম শুরুতে কিছু যোগ করতে বা মুছতে হবে।
- যখন আপনার ইনডেক্স ধরে সরাসরি খোঁজার দরকার পড়বে না।
- যখন আপনি একটা স্ট্যাক (Stack) বা সাধারণ কিউ (Queue) বানাতে চাইবেন।
- যখন ডেটার সাইজ কখন কত হবে তার কোনো ঠিক নেই, আর আপনি ফিক্সড বড় মেমোরি আটকে রাখতে চান না।
কখন এটা এড়িয়ে চলবেন?
- যখন ইনডেক্স বা পজিশন ধরে প্রচুর জিনিস খুঁজতে হয় — তখন অ্যারে ব্যবহার করাই ভালো।
- যখন শেকল ধরে সামনে এবং পেছনে দুই দিকেই যাতায়াত করার দরকার পড়ে — এই কাজের জন্য ডাবলি লিংকড লিস্ট ভালো।
- যখন মেমোরি অনেক কম থাকে — কারণ লিস্টের প্রতিটা নোডে ডেটার পাশাপাশি পয়েন্টারের জন্য এক্সট্রা মেমোরি লাগে।
ছোট কুইজ
পড়া চালিয়ে যান