Data Structure: Linked List - Part 1

Basic

Data Structure এর সবচেয়ে গুরুত্বপূর্ন বিষয় হচ্ছে linked list. এটা C প্রোগ্রাম শেখার পর নতুন একটা অধ্যায়। এটা খুব ভালোভাবে রপ্ত করতে পারা, প্রথামিক অবস্থায় সামান্য কঠিন আছে। যেহেতু আমাদের C প্রোগ্রামের structure সম্পর্কে ধারনা আছে তাই, একটা Node কি তা structure দিয়ে বললে অনেকের কাছে সহজ হবে। আমরা parallel কিছু array দিয়েও Linked list ব্যাখা করতে পারি, তবে তা পরে আলোচনা করা যাবে। C তে integer type variable কে point করার জন্য ওই ধরনের একটা pointer লাগে। একইভাবে structure type variable কে point করার জন্য ওই ধরনের একটা pointer লাগবে।

এবার তুমি প্রোগ্রাম টা আরো পরিবর্তন করে, তোমার structure এবং pointer সম্পর্কে ধারনা পরিষ্কার করে নিতে পারো। কোডে যদি নিচের মত করে পরিবর্তন করা হয় তাহলে কি হবে তা তোমরা নিজেরা দেখবে।)

এবার আরো এক ধাপ এগিয়ে যায়। এবার আমরা structure এর মাঝেই একই structure type pointer declare করব। এটা করব কেন? এটা করার কারন হচ্ছে আমরা চাচ্ছি structure এর ভেতরের pointer টা দিয়ে অন্য একটা একই ধরনে structure type variable কে point করতে। এই ধরনের pointer কে বলে self reference pointer.

উপরের উদাহরণে struct node type একটা variable a যার LINK pointer struct node type একটা variable b কে point করে আছে। আর b এর LINK pointer কাউকেই point করে নাই। অর্থাৎ আমরা একটা ছোট linked list তৈরি করে ফেলেছি। এবার একটা নতুন term নিয়ে আসি। সেটা হচ্ছে header linked list, যার প্রথম node-টি নাম হচ্ছে header. আর একটা head নামের struct node type এর pointer, point করে থাকবে প্রথম node কে অর্থাৎ a node কে।

এখানে linked list বলতে head pointer কেই বোঝাবে। head pointer এর মান হারিয়ে ফেললেই linked list ধবংস হয়ে যাবে। এই ছোট linked list কে traverse করতে চাইলে আমরা head pointer কখনই সামনের node নিয়ে যাব না। তাই traverse/visit করার জন্য আমরা আরো একটা struct node type এর pointer v নিবো যা প্রথম node কে point করবে, তারপর ওই node এর INFO কে process করে, সামনের node কে point করবে। ধরি, v:=head, তাহলে সামনের node কে point করতে চাইলে আমাকে instruction দিতে হবেঃ v:=v↑.LINK. তাহলে এখন v pointer head এর পরের node কে point করে আছে। তাহলে v কতক্ষণ পর্যন্ত next node এ যেতে থাকবে? উত্তর হচ্ছে, v এর মান NULL না হওয়া পর্যন্ত, কারন শেষ node টি NULL কে point করে আছে। তাহলে এই পর্যায়ে traverse/visit এর algorithm হবেঃ

এই algorithm এর flow chart হবেঃ

Fig. Traverse a header linked list

নিচে code সহ ব্যাখা তুলে ধরা হলঃ

এবার আসি, নতুন একটি node নিতে হলে কি করতে হবে? আমাদেরকে memory allocate করতে হবে। এই memory আমরা system হতে নিব। যদি memory না থাকে তাহলে আমরা memory allocate করতে পারব না। ধরি, আমাদের কাছে যে memory আছে সেগুলো নিয়ে একটা linked list তৈরি করা আছে, যার প্রথম node টি struct node type AV ponter variable দ্বারা point করা আছে।