লিংকড লিস্ট

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে


কম্পিউটার বিজ্ঞানে, লিংকড লিস্ট (Linked List) বলতে বুঝায় তথ্যাবলীর এক ধরনের তালিকা যার উপাদানগুলির ক্রম মেমরিতে তাদের ভৌত অবস্থান দ্বারা নির্দেশিত নয়। অর্থাৎ মেমরিতে উপাদানগুলি ক্রমানুযায়ী নাও থাকতে পারে। কিন্তু প্রতিটি উপাদান একটি নির্দেশক (reference or link) ব্যবহারের মাধ্যমে তার পরবর্তী উপাদানটিকে নির্দেশ করে। লিংকড লিস্টের প্রতিটি উপাদানকে নোড বলা হয়। নোড গুলির সমন্বয়ে গঠিত হয় লিংকড লিস্ট, যা একত্রে একটি অনুক্রমকে উপস্থাপন করে। প্রতিটি নোড ডাটা বা তথ্য এবং পরবর্তী নোডের নির্দেশক (reference or link) ধারণ করে । এই গঠনের কারণে দক্ষতার সাথে যে কোন অবস্থানে নোড সন্নিবেশ এবং অপসারণ করা যায় সহজেই। আরও জটিল অ্যালগরিদমের সাহায্যে অতিরিক্ত লিংক ব্যাবহারের মাধ্যমে দ্রুত এবং দক্ষতার সাথে নোড সংযোজন ও অপসারণ করাও সম্ভব। লিংকড লিস্টের একটি বড় সমস্যা হলো নোডের তথ্যাবলী ব্যবহার করতে সময় বেশি লাগে । লিংকড লিস্টের ক্ষেত্রে এটা লিনিয়ার (linear) । দ্রুত মেমোরির তথ্য ব্যবহার করা সম্ভবপর হয় না। এক্ষেত্রে অ্যারে (Array) বেশী কার্যকর।

Singly-linked-list.svg একটি লিংকড লিস্ট যার প্রতিটি নোড ডাটা বা উপাত্ত এবং পরবর্তী নোডের একটি নির্দেশক বা লিংক ধারণ করে।

অসুবিধা সমূহ[সম্পাদনা]

  • পয়েন্টারের জন্য মেমরি লাগায় অ্যারের থেকে লিংকড লিস্ট বেশি মেমরি ব্যবহার করে।
  • অনুক্রমিক হওয়ায় নোড গুলো প্রথম থেকে অনুক্রম অনুযায়ী ব্যবহার করতে হয় অর্থাৎ সিকুইন্সিয়াল অ্যাক্সেস (sequential access) পদ্ধতি ।
  • নোড গুলোর অবস্থান মেমরিতে পার্শ্ববর্তী না হওয়ায় এগুলো (নোড) একক ভাবে অ্যাক্সেস করতে সময় বেশি লাগে, বিশেষত সিপিইউ কেইচে (CPU cache) ।
  • বিপরীত দিক থেকে লিংকড লিস্ট ব্যবহার করা অর্থাৎ অ্যাক্সেস করা কঠিন। বিশেষভাবে নোড গুলো কেবল একদিকে লিংকড (singly-linked) হলে এটা করা কষ্টসাধ্য হয়ে যায়। তবে উভয় দিকে লিংক থাকলে ( যাকে বলে doubly linked ) সেক্ষেত্রে উভয় দিকে অ্যাক্সেস করা সহজ, তবে সেক্ষেত্রে পূর্বের নোডের নির্দেশক পয়েন্টারের (pointer) জন্য মেমরিতে জায়গা লাগে। ফলে প্রোগ্রামের জন্য জায়গা বেশি লাগে।