ইতিপূর্বের উদাহরণগুলোতে আমরা পাইথনের বিল্ট-ইন ডাটা স্ট্রাকচার - লিস্টের ব্যবহার দেখে এসেছি। লিংকড লিস্টকে আমরা সেই লিস্টের বিশেষায়িত রূপ বলতে পারি। বিশেষায়িত বলার কারণ হচ্ছে, এই লিস্টের ভিতর কিছু বিশেষ ব্যাপার-স্যাপার রয়েছে।

মোটামুটি চার টাইপের লিংকড লিস্ট রয়েছে: সিম্পল (Simple) বা সিঙ্গলি (Singly) লিংকড লিস্ট, ডাবলি (Doubly) লিংকড লিস্ট, মাল্টিপ্লাই (Multiply) লিংকড লিস্ট ও সার্কুলার (Circular) লিংকড লিস্ট। আজকে আমরা সিঙ্গলি লিংকড লিস্ট সম্পর্কে জানার চেষ্টা করব।

সহজ ভাষায়, সিঙ্গলি লিংকড লিস্ট হল কতগুলো নোডের চেইন বা সমাহার। আরেকটু পুস্তকী ভাষায় বলতে গেলে, সিঙ্গলি লিংকড লিস্ট হল কতগুলো ডাটা এলিমেন্ট বা নোডের ধারাবাহিক সংগ্রহশালা (কালেকশন – collection)। লিনিয়ার সিকুয়েন্স আর কি! এখানে, নোড আসলে একটা বেসিক ইউনিট। প্রতিটি নোডে দুটি ফিল্ড থাকে। প্রথম ফিল্ডে থাকে ডাটা আইটেম আর শেষের ফিল্ডে থাকে পয়েন্টার বা পরবর্তী নোডের লিংক।

ব্যাপারটা সহজে বোঝার জন্য আমরা শিশুবেলায় ফিরে যেতে পারি। সেই স্কুল পালানো দুরন্তপনার দিনগুলো কি মনে আছে আমাদের? বিশেষ করে, হাত ধরাধরি করে দশ-পনেরজন পাশাপাশি দাঁড়িয়ে থাকার দিনগুলো? এটা মনে থাকলেই আপাতত চলবে। যখন আমরা দশ-পনেরজন হাত ধরাধরি করে পাশাপাশি দাঁড়াতাম তখন আমরা আমাদের দু’হাত দিয়ে দুজনকে ধরতাম। একজনের ডানহাত পরবর্তী জনের বামহাত ধরত, তার ডান হাত আবার তার পরের জনের বামহাত। এভাবে একটা হিউম্যান চেইন গঠন করতাম আমরা। এই চেইনে প্রতিটি মানুষকে এক-একটি নোড হিসেবে কল্পনা করতে পারি আমরা। সেই নোডের ডাটা আইটেম আমাদের মূলদেহ আর ডানহাত হল পয়েন্টার। কি এখনো সহজ মনে হচ্ছে না? তাহলে একটা ছবি দেখা যাক।

এতক্ষণ আমরা যে হাত ধরাধরির কাহিনী বর্ণনা করছিলাম, এই চিত্রটা আসলে তারই মানসচিত্র (ভিজুয়ালাইজেশন - visualization)। প্রথম নোড থেকে মূলত সিঙ্গলি লিংকড লিস্টের অগ্রযাত্রা শুরু হয়। প্রথম নোডের ডাটা আইটেম অংশে প্রথম ভ্যালুটা থাকে। প্রথম নোডের পয়েন্টার অংশ দ্বিতীয় নোডকে নির্দেশ করে। এভাবে চলতে থাকে। একটা লিস্টের পরিসমাপ্তিকে মূলত নাল (Null) রেফারেন্স দ্বারা চিহ্নিত করা হয়। অনেক সময় None পরিসমাপ্তি বুঝানো হয়। পরিসমাপ্তি দ্বারা বুঝানো হচ্ছে যে এই নোডের পরে আর কোন নোড নেই।

অপারেশন Link to heading

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

appendleft(item) Link to heading

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

append(item) Link to heading

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

insert(position, item) Link to heading

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

remove(item) Link to heading

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

pop() Link to heading

সাধারণত এই ফাংশন বা মেথড লিস্টের শেষের ডাটা আইটেমটিকে ও সংশ্লিষ্ট নোড অপসারণ করে এবং ডাটা আইটেম রিটার্ন করে। (ধরে নেয়া হয়, লিস্টে অন্ততপক্ষে একটি আইটেম রয়েছে)

is_empty() Link to heading

এটি একটি বুলিয়ান ফাংশন (বা মেথড)। লিস্ট খালি কিনা সেটি চেক করে True বা False রিটার্ন করে। এর কোন প্যারামিটার নেই।

size() Link to heading

এই ফাংশন (বা মেথড) লিংকড লিস্টের মোট আইটেম (নাকি নোড?) সংখ্যা রিটার্ন করে। এরও কোন প্যারামিটার নেই।

search(item) Link to heading

এটি একটি বুলিয়ান ফাংশন (বা মেথড)। একটি আইটেমকে আর্গুমেন্ট বা প্যারামিটার হিসেবে গ্রহণ করে লিংকড লিস্টে সেটি রয়েছে কিনা তা সার্চ করে দেখে এবং True বা False রিটার্ন করে।

index(item) Link to heading

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

printlist() Link to heading

এই ফাংশন বা মেথডটি লিস্টের সবগুলো আইটেমকে প্রিন্ট করবে। (ধরে নেয়া হয়, লিস্টে ন্যূনতম একটি আইটেম রয়েছে।)

ইমপ্লিমেন্টেশন Link to heading

স্টাক, কিউ বা ডেকের মত সিঙ্গলি লিংকড লিস্টের ইমপ্লিমেন্টেশন সরল প্রকৃতির নয়। খানিকটা জটিল হলেও পাইথনে (3.x) ভাল ধারণা থাকলে ইমপ্লিমেন্ট করতে কষ্ট হবার কথা নয়। আসলে ডাটা স্ট্রাকচার বা অ্যালগরিদম দেখে ইমপ্লিমেন্ট করার মত কোন বিষয় নয়। কি হচ্ছে বা কি হবে তা সম্পর্কে স্পষ্ট ধারণা থাকলে সহজেই কোড লিখে ফেলা যায়। তারপরও উদাহরণ হিসেবে এটা দেখা যেতে পারে।

অদূর ভবিষ্যতে আমরা ডাবলি (Doubly) লিংকড লিস্ট ও সার্কুলার (Circular) লিংকড লিস্ট সম্পর্কেও জানব। তবে তার আগে সিঙ্গলি লিংকড লিস্টে হাত পাকাতে হবে আমাদের। সেজন্য সিঙ্গলি লিংকড লিস্ট ব্যবহার করে আমরা স্টাক ও কিউ ইমপ্লিমেন্ট করব। আর হ্যাকারর‍্যাংক ও হ্যাকারআর্থ-এর কিছু প্রব্লেম সলভ করব।