ডেটা স্ট্রাকচার: XOR লিংকড লিস্ট

XOR বাইনারি অপারেশনটা দিয়ে বেশ মজার মজার সব কাজ করা যায় যেগুলো প্রথম দেখায় ম্যাজিকের মত মনে হয়, কিন্তু একটু ভিতরের দিকে তাকালেই বোঝা যায় কি হচ্ছে। যেমন ধরা যাক গেম থিওরির কথা, তোমরা যারা নিম গেমের সাথে পরিচিত তারা জান যে কিভাবে শুধু XOR অপারেশন দিয়ে বের করে ফেলা যায় খেলায় কে জিতবে বা হারবে। প্রোগ্রামিং কনটেস্টে XOR রিলেটেড প্রবলেম খুবই কমন, আমি নিজেই বেশ কিছু কনটেস্টে এধরণের প্রবলেম সেট করেছি। আজকে দেখাবো কিভাবে XOR  ব্যবহার করে লিংকড লিস্টের মেমরি কমিয়ে ফেলা যায়। বাস্তবে তুমি কখনোই হয়তো এরকম লিংকড লিস্ট লিখবে না, কিন্তু এই লেখাটা পড়ার পর XOR  এর প্রোপার্টিগুলোর ব্যবহার নিয়ে তোমার ধারণা আরো শক্ত হবে।

এই লেখাটা পড়তে হলে তোমাকে লিংকড লিস্টের বেসিক নিয়ে জানা থাকতে হবে।

ডাবলি-লিংকড লিস্টের প্রতিটা নোডে তার সামনের এবং পিছনের নোডের মেমরি অ্যাড্রেস রাখা থাকে, যেগুলো ব্যবহার করে আমরা সামনে বা পিছন দিকে যেতে পারি। ছবিতে একটা ডাবলি-লিংকড লিস্ট দেখা যাচ্ছে যেটার ৩টা মাত্র নোড। প্রতিটা নোডের উপরে লাল রং দিয়ে নোডটা মেমরি অ্যাড্রেস দেখিয়েছি। প্রতিটা নোডে দুটি পয়েন্টার আছে সামনের এবং পিছনের নোডের অ্যাড্রেসের ঠিকানা রাখার জন্য।

XOR লিংকড লিস্টে পয়েন্টার দুটোর বদলে একটা রাখা থাকে।   প্রতিটা নোডে রাখা থাকে তার সামনের এবং পিছনের নোডের অ্যাড্রেসের XOR  ভ্যালু।

উপরের ছবিতে একটা উদাহরণ দেখা যাচ্ছে। এবার প্রতিটা নোড একটা মাত্র পয়েন্টার এবং সেখানে সামনের এবং পিছের নোডের অ্যাড্রেসের XOR   রাখা হয়েছে। প্রথম এবং শেষ নোডের ক্ষেত্রে নাল এর জায়গায় শূন্য ব্যবহার করেছি।

লিংকড লিস্ট ট্রাভার্স করা হয় যেকোন একটা মাথা থেকে, হঠাৎ করে কোন নোডে র‌্যান্ডম এক্সেস করা যায় না। তারমানে তুমি যখন কোন একটা নোডে আছে তখন সেই নোডের আগের নোডের অ্যাড্রেস তুমি অলরেডি জানো। এই তথ্য ব্যবহার করে তুমি কি পরের নোডে যেতে পারবে? হিন্টস:

$X \oplus X = 0$
$X \oplus 0 = 0$

মনে করো তুমি নোড B তে আছো। B এর পয়েন্টারের ভ্যালু হবে:

$ptr(B) =  address(A) \oplus address(C)$

তুমি যদি $A$ এর অ্যাড্রেস জানো তাহলে কিন্তু খুব সহজেই $C$ এর অ্যাড্রেস বের করে ফেলতে পারবে। তোমাকে খালি $A$ এর অ্যাড্রেসের সাথে $ptr(B)$ কে XOR  করে ফেলতে হবে। নিচের ছবিটা দেখো:

ইকুয়েশন দিয়ে দেখাতে গেলে:

$address(A) \oplus ptr(B)$
$ =  address(A) \oplus address(A) \oplus address(C) $
$ = 0 \oplus address(C) = address(C)$

এভাবে যেকোন নোডে বসেই তুমি তার পরের নোডের অ্যাড্রেস বের করে ফেলতে পারবে, খালি তোমার লাগছে আগের নোডের মেমরি অ্যাড্রেস এবং বর্তমান নোডে সেভ করে রাখা পয়েন্টারের ভ্যালু। এটাই হলো XOR লিংকড লিস্ট।

আগেই বলেছি, এধরণের লিংকড লিস্ট বাস্তবে কাজে লাগার সম্ভাবনা খুবই কম। বর্তমানে মেমরি জিনিসটা খুবই সস্তা, একটা মাত্র পয়েন্টার কমিয়ে আমাদের সিগনিফিকেন্ট কোন মেমরি সেভ হবে না, বরং কোড মেইনটেইনেন্সের ঝামেলা বেড়ে যাবে। এছাড়াও আরো সমস্যা আছে, সেটা হলো গার্বেজ কালেকশন নিয়ে। গার্বেজ কালেক্টর অ্যালগরিদম তোমার লিংকলিস্টে ট্র্যাভার্স করতে পারবে না, XOR  করা পয়েন্টারের অর্থই সে বুঝতে পারবে না। কিন্তু তুমি XOR  এর মজার একটা ব্যবহার শিখলে, এটাই তোমার লাভ, হয়তো এই ধারণা কাজে লাগিয়ে পরের প্রোগ্রামিং কনটেস্টে কোন প্রবলেম সলভ করে ফেলতে পারবে!

হ্যাপি কোডিং!

 

Print Friendly, PDF & Email

ফেসবুকে মন্তব্য

comments

Powered by Facebook Comments

2,769 times read (exlcuding bots)

Leave a Reply

Your email address will not be published. Required fields are marked *