লিংকড লিস্ট বুঝার আগে, C প্রোগ্রামিং ভাষায় অ্যারে এর ডিসঅ্যাডভান্টেজ এবং পয়েন্টারের অ্যাডভান্টেজ সম্পর্কে জানা দরকার।
অ্যারের ডিসঅ্যাডভান্টেজ
- স্ট্যাটিক মেমরি অ্যালোকেশন থাকে।
- অ্যারেতে মেমরি বর্জনা হতে পারে।
- মেমরির অভাব অ্যারের একটি গুরুত্বপূর্ণ ডিসঅ্যাডভান্টেজ।
পয়েন্টারের অ্যাডভান্টেজ
- ডাইনামিক মেমরি অ্যালোকেশন থাকে।
- পয়েন্টারে মেমরির কার্যকর ব্যবহার সম্ভব।
লিংকড লিস্ট
লিংকড লিস্ট ডাইনামিক মেমরি অ্যালোকেশন ব্যবহার করে, অর্থাৎ এটি প্রয়োজন অনুযায়ী বড় ও ছোট হয়। এটি নোডের একটি সংগ্রহ হিসাবে সংজ্ঞায়িত। এখানে প্রতিটি নোডের দুটি অংশ থাকে—ডেটা এবং লিংক। ডেটা, লিংক এবং লিংকড লিস্টের রিপ্রেজেন্টেশন নিচে দেওয়া হলো—
লিংকড লিস্টের প্রকারভেদ
লিংকড লিস্টের চারটি প্রকার আছে—
- সিঙ্গলি লিংকড লিস্ট (Single / Singly linked lists)
- ডাবলি লিংকড লিস্ট (Double / Doubly linked lists)
- সার্কুলার সিঙ্গল লিংকড লিস্ট (Circular single linked list)
- সার্কুলার ডাবল লিংকড লিস্ট (Circular double linked list)
সিঙ্গলি লিংকড লিস্ট
নিচের রিপ্রেজেন্টেশনটি দেখুন—
নোডের দুটি অংশ থাকে—
- ডেটা (Data)
- লিংক (Link)
লিংক ফিল্ড সবসময় লিস্টের পরবর্তী নোডকে পয়েন্ট করে।
শেষ নোডের লিংক ফিল্ড হলো NULL।
ডাবলি লিংকড লিস্ট
নিচের রিপ্রেজেন্টেশনটি দেখুন—
নোডের তিনটি অংশ থাকে—
- ডেটা পার্ট (Data part)
- লেফট লিংক (Left link)
- রাইট লিংক (Right link)
লেফট লিংক সবসময় লিস্টের বামপাশের নোডকে পয়েন্ট করে এবং রাইট লিংক ডানপাশের নোডকে।
প্রথম নোডের লেফট লিংক এবং শেষ নোডের রাইট লিংক অবশ্যই NULL হতে হবে।
সার্কুলার সিঙ্গল লিংকড লিস্ট
নিচের রিপ্রেজেন্টেশনটি দেখুন—
নোডের দুটি অংশ থাকে—
- ডেটা পার্ট (Data part)
- লিংক পার্ট (Link part)
লিংক ফিল্ড সবসময় লিস্টের পরবর্তী নোডকে পয়েন্ট করে।
শেষ নোডের লিংক পার্ট সবসময় প্রথম নোডকে পয়েন্ট করে।
সার্কুলার ডাবল লিংকড লিস্ট
নিচের রিপ্রেজেন্টেশনটি দেখুন—
নোডের তিনটি অংশ থাকে—
- ডেটা পার্ট (Data part)
- লেফট লিংক (Left link)
- রাইট লিংক (Right link)
লেফট লিংক সবসময় বামপাশের নোডকে এবং রাইট লিংক ডানপাশের নোডকে পয়েন্ট করে।
প্রথম নোডের লেফট লিংক শেষ নোডকে পয়েন্ট করে এবং শেষ নোডের রাইট লিংক প্রথম নোডকে পয়েন্ট করে।
