স্কিপ লিস্ট (Skip List)
ধরুন আপনি লোকাল ট্রেনে উঠেছেন। সে পথে পড়া সব স্টেশনে থামবে। কিন্তু এর পাশাপাশি একটা এক্সপ্রেস (express) ট্রেনও আছে, যেটা ছোটখাটো সব স্টেশন স্কিপ বা বাদ দিয়ে শুধু বড় বড় স্টেশনেই থামে। আর হয়তো একটা সুপার-এক্সপ্রেসও আছে, যেটা আরও অনেক স্টেশন স্কিপ করে যায়। আপনি যদি খুব দূরের কোনো স্টেশনে যেতে চান, তবে বুদ্ধিমানের কাজ হবে প্রথমে এক্সপ্রেস ট্রেনে ওঠা, এবং গন্তব্যের কাছাকাছি বড় স্টেশনে নেমে তারপর লোকাল ট্রেন ধরা।
একটা স্কিপ লিস্ট (Skip List) ঠিক এই বুদ্ধিটা কাজে লাগিয়েই তৈরি। এর একদম নিচে থাকে একটা সাধারণ লিংকড লিস্ট (linked list) — যেখানে ডেটাগুলো ছোট থেকে বড় সাজানেন থাকে। আর এর ওপরে থাকে ভিআইপি বা এক্সপ্রেস লেন: যেগুলো মূলত ফাঁকা ফাঁকা লিংকড লিস্ট। এগুলোর কাজ হলো অনেকগুলো ডেটাকে স্কিপ করে বা লাফিয়ে লাফিয়ে আপনাকে দ্রুত সামনের দিকে নিয়ে যানয়া।
এর ফলে এখানে খোঁজাখুঁজির এভারেজ বা গড় স্পিড হয়ে যায় O(log n) — যেটা একটা ব্যালান্সড বাইনারি সার্চ ট্রির (BST) সমান ফাস্ট! অথচ এতে ব্যালান্সড ট্রির মতো ঘোরাঘুরি বা রোটেশন (rotation) করার কোনো প্যাঁচ নেই। সবকিছু সুন্দরভাবে ম্যানেজ করা হয় জাস্ট একটা কয়েন বা মুদ্রা টস করার ওপর ভিত্তি করে!
← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন
লেভেল তৈরি করা — কয়েন টস গেম
যখন নতুন কোনো ডেটা লিস্টে ঢোকাবেন, সেটা সবসময় লিস্টের একদম নিচের লেভেলে বা লোকালে তো যাবেই। এরপর আপনি একটা কয়েন টস করবেন। যদি হেড (Heads) পড়ে? তাহলে ডেটাটাকে এর ওপরের লেভেল ১-এও (Level 1) বসিয়ে দেবেন। আবার টস করবেন। যদি আবার হেড পড়ে? তাহলে লেভেল ২-তেও বসাবেন। এভাবে যতক্ষণ হেড পড়বে, ততক্ষণ ওপরের লেভেলে ডেটাটা জমা হতে থাকবে — আর টেইল (Tails) পড়লেই খেলা শেষ। এর ফলে গড়ে অর্ধেক ডেটা লেভেল ১-এ যায়, তার চার ভাগের এক ভাগ লেভেল ২-তে যায়... এভাবেই প্রাকৃতিকভাবে একটা সুন্দর লগারিদমিক (logarithmic) স্ট্রাকচার বা সিঁড়ি তৈরি হয়ে যায়।
খোঁজা বা সার্চ করা (Searching)
সবসময় খেলা শুরু করবেন লিস্টের একদম ওপরের বা-দিকের মাথা থেকে। এরপর ডান দিকে যেতে থাকবেন, যতক্ষণ না সামনের নোডের ভ্যালু আপনার খোঁজা টার্গেটের চেয়ে বড় হয়ে যাচ্ছে। যখন দেখবেন ডানে আর যানয়া যাচ্ছে না (কারণ সামনের জনের ভ্যালু বড়), তখন এক ধাপ নিচে নেমে যাবেন। এভাবে ডান দিকে যানয়া আর নিচে নামতে নামতে একসময় আপনি একদম নিচের লেভেলে পৌঁছে যাবেন। সেখানেই আপনি আপনার কাঙ্ক্ষিত ডেটা পেয়ে যাবেন বা অন্তত কনফার্ম হবেন যে সেটা লিস্টে নেই।
- প্রতি লেভেল নিচে নামার সময় আপনার খোঁজার এলাকা গড়ে অর্ধেক হয়ে যায়।
- মোট লেভেলের সংখ্যা থাকে গড়ে log₂(n)-এর মতো, তাই খোঁজার মোট স্পিডও হয় O(log n)।
নতুন ঢোকানো (Insert) এবং মোছা (Delete)
ইনসার্ট করার সময়: প্রথমে সার্চ করে বের করতে হয় প্রতিটা লেভেলে ডেটাটা ঠিক কার কার মাঝখানে বসবে, এরপর কয়েন টস করে তাকে সেই লেভেলগুলোতে লিংক করে দেওয়া হয়। ডিলিট করার সময়: ঠিক একইভাবে সার্চ করে ডেটাটা যেখানে যেখানে আছে, সেখান থেকে তাকে আনলিংক বা কেটে বাদ দিয়ে দেওয়া হয়। দুটো কাজই সার্চের মতোই গড়ে O(log n) সময় নেয়।
কেন শুধুই একটা ব্যালান্সড BST (যেমন: এভিএল বা রেড-ব্ল্যাক ট্রি) ব্যবহার করছি না?
ব্যালান্সড BST সবসময় (এমনকি সবচেয়ে খারাপ অবস্থাতেও) O(log n) গ্যারান্টি দেয়, কিন্তু ট্রি-টাকে ব্যালান্সড রাখতে গিয়ে তাদের অনেক প্যাঁচানো রোটেশন করতে হয়। অন্যদিকে, স্কিপ লিস্ট অনেক সহজ কোড দিয়েই গড়ের ওপর (average) সেই একই ফাস্ট পারফরম্যান্স দেয়। তাছাড়া মাল্টি-থ্রেডিং (multi-threading) বা কনকারেন্সির (concurrency) ক্ষেত্রে স্কিপ লিস্ট অনেক বেশি সুবিধাজনক — কারণ একসাথে একাধিক প্রসেস এখানে কাজ করতে গেলে পুরো লিস্ট আটকে (lock) রাখতে হয় না।