লিঙ্কডলিস্ট সংগ্রহের সাথে পরিচয় করিয়ে দেওয়া হচ্ছে

1. এর ইতিহাসLinkedList

জাভা C++ ভাষা থেকে উত্তরাধিকারসূত্রে প্রাপ্ত আরেকটি কালেকশন ক্লাস জাভা রয়েছে। এটি হল LinkedListক্লাস, যা একটি "লিঙ্কড তালিকা" প্রয়োগ করে।

বাহ্যিকভাবে, একটি LinkedListএকটি হিসাবে একই বলে মনে হচ্ছে ArrayList। ক্লাসে ক্লাসের LinkedListমতো একই পদ্ধতি রয়েছে ArrayList। নীতিগতভাবে, আপনি সর্বদা LinkedListএকটি এর পরিবর্তে একটি ব্যবহার করতে পারেন ArrayListএবং সবকিছু কাজ করবে।

তাই কেন আমরা অন্য তালিকা ক্লাস প্রয়োজন?

উত্তরটি ক্লাসের অভ্যন্তরীণ কাঠামোর সাথে সম্পর্কিত সবকিছুই রয়েছে LinkedList। একটি অ্যারের পরিবর্তে, এটি একটি দ্বিগুণ লিঙ্কযুক্ত তালিকা ব্যবহার করে । আমরা একটু পরে যে কি ব্যাখ্যা করব.

ক্লাসের LinkedListবিভিন্ন অভ্যন্তরীণ কাঠামো তালিকার মাঝখানে উপাদান সন্নিবেশ করাতে এটিকে দ্রুততম করে তোলে।

ইন্টারনেটে, আপনি প্রায়শই ArrayListএবং LinkedListক্লাসের তুলনা খুঁজে পেতে পারেন:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

সবকিছু যথেষ্ট পরিষ্কার বলে মনে হচ্ছে: যদি আপনাকে প্রায়ই তালিকায় উপাদান সন্নিবেশ করতে হয়, ব্যবহার করুন LinkedList; যদি খুব কমই হয়, তাহলে ArrayList ব্যবহার করুন। কিন্তু বাস্তবতা একটু ভিন্ন।

2. কেউ ব্যবহার করে নাLinkedList

কেউ ব্যবহার করে না LinkedList।

এমনকি ক্লাসের লেখক LinkedListসম্প্রতি টুইট করেছেন: "কেউ কি আসলে ব্যবহার করে LinkedList? আমি এটি লিখেছি, এবং আমি এটি ব্যবহার করি না।"

তাহলে চুক্তি কি?

প্রথমত, ক্লাস ArrayListখুব দ্রুত তালিকার মাঝখানে উপাদান সন্নিবেশ করতে সক্ষম হতে শুরু করে। তালিকার মাঝখানে একটি উপাদান সন্নিবেশ করার সময়, আপনাকে তালিকার শেষের দিকে 1 দ্বারা সন্নিবেশ বিন্দুর পরে সমস্ত উপাদান স্থানান্তর করতে হবে। এতে সময় লাগতো।

কিন্তু এখন সবকিছু বদলে গেছে। একটি অ্যারের সমস্ত উপাদান মেমরির একই ব্লকে একে অপরের কাছাকাছি থাকে, তাই উপাদানগুলি স্থানান্তর করার অপারেশনটি খুব দ্রুত নিম্ন-স্তরের কমান্ড দ্বারা সঞ্চালিত হয়: .System.arraycopy()

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

দ্বিতীয়ত, ক্লাসটি LinkedListদ্রুত উপাদানগুলি সন্নিবেশ করতে পারে যদি আপনি সেগুলিকে একটি পুনরাবৃত্তিকারী ব্যবহার করে সন্নিবেশ করেন। আপনি যদি একটি ইটারেটার ব্যবহার করেন LinkedListএবং ক্রমাগত নতুন উপাদান সন্নিবেশ করেন (অথবা বিদ্যমানগুলি সরান), অপারেশনটি অতি দ্রুত।

আপনি যদি লুপের ভিতরে একটি বস্তুতে উপাদান যোগ করেন LinkedList, তাহলে প্রতিটি দ্রুত সন্নিবেশ অপারেশনের সাথে একটি ধীর "গেট এলিমেন্ট" অপারেশন হয়।

বাস্তবতা এর অনেক কাছাকাছি:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

কেন একটি যেমন একটি ধীর অপারেশন থেকে একটি উপাদান পাচ্ছেন LinkedList?

LinkedListকিভাবে গঠন করা হয় তার সাথে একটু পরিচিত হওয়ার পরে আপনি সেই প্রশ্নের উত্তর দিতে পারেন ।

3. কিভাবে LinkedListগঠন করা হয়

LinkedListতুলনায় একটি ভিন্ন অভ্যন্তরীণ গঠন আছে ArrayList. উপাদান সংরক্ষণের জন্য এটিতে একটি অভ্যন্তরীণ অ্যারে নেই। পরিবর্তে, এটি একটি ডাটা স্ট্রাকচার ব্যবহার করে যাকে ডাবললি ইনকড তালিকা বলা হয় ।

দ্বিগুণ লিঙ্কযুক্ত তালিকার প্রতিটি উপাদান পূর্ববর্তী উপাদান এবং পরবর্তী উপাদানের একটি রেফারেন্স সংরক্ষণ করে। এটি কিছুটা দোকানে একটি লাইনের মতো, যেখানে প্রতিটি ব্যক্তি তাদের সামনে দাঁড়িয়ে থাকা ব্যক্তির পাশাপাশি তাদের পিছনে দাঁড়িয়ে থাকা ব্যক্তিটিকে মনে রাখে।

এই ধরনের একটি তালিকা মেমরির মত দেখায়:

মাথা এবং লেজ (ধূসর পটভূমি সহ কোষ) হল firstএবং lastভেরিয়েবল, যা Nodeবস্তুর উল্লেখ সংরক্ষণ করে।

মাঝখানে, আপনার কাছে Nodeঅবজেক্টের একটি চেইন রয়েছে (বস্তু, ভেরিয়েবল নয়)। তাদের প্রতিটি তিনটি ক্ষেত্র গঠিত:

• prev— পূর্ববর্তী বস্তুর একটি রেফারেন্সNode (লিঙ্ক) সঞ্চয় করে (একটি হলুদ পটভূমি সহ কোষ)।
• value— তালিকার এই উপাদানটির মান সংরক্ষণ করে (সবুজ পটভূমি সহ ঘর)।
• next- পরবর্তী বস্তুর একটি রেফারেন্সNode (লিঙ্ক) সঞ্চয় করে (নীল পটভূমি সহ কোষ)

দ্বিতীয় অবজেক্ট (ঠিকানা F24) হল nextপ্রথম অবজেক্টের পরবর্তী ( ) এবং prevতৃতীয় অবজেক্টের জন্য আগের ( )। তৃতীয় অবজেক্টের হলুদ ক্ষেত্রটিতে F24 ঠিকানা রয়েছে এবং প্রথম বস্তুর নীল ক্ষেত্রটিতে F24 ঠিকানা রয়েছে।

প্রথম এবং তৃতীয় বস্তুর তীরগুলি একই দ্বিতীয় বস্তুর দিকে নির্দেশ করে। তাই এইভাবে তীর আঁকা আরো সঠিক হবে।

4. লিঙ্ক করা তালিকায় একটি উপাদান সন্নিবেশ করান

এই ধরনের লাইনে কাউকে যুক্ত করতে, আপনাকে কেবল একজন আরেকজনের পাশে দাঁড়ানো দুই ব্যক্তির অনুমতি নিতে হবে। প্রথম ব্যক্তিটি নবাগতকে "আমার পিছনের ব্যক্তি" হিসাবে স্মরণ করে এবং দ্বিতীয় ব্যক্তিটি তাদের "আমার সামনের ব্যক্তি" হিসাবে স্মরণ করে।

আপনাকে যা করতে হবে তা হল দুটি প্রতিবেশী বস্তুর রেফারেন্স পরিবর্তন করা:

আমরা দ্বিতীয় এবং তৃতীয় বস্তুর রেফারেন্স পরিবর্তন করে আমাদের তালিকায় একটি নতুন আইটেম যোগ করেছি। নতুন অবজেক্টটি পুরানো দ্বিতীয় অবজেক্টের জন্য পরবর্তী এবং পুরানো তৃতীয় অবজেক্টের জন্য আগেরটি। এবং, অবশ্যই, নতুন অবজেক্টের নিজেই সঠিক রেফারেন্সগুলি সংরক্ষণ করতে হবে: এর আগের অবজেক্টটি পুরানো দ্বিতীয় অবজেক্ট এবং এর পরবর্তী অবজেক্টটি পুরানো তৃতীয় অবজেক্ট।

একটি উপাদান অপসারণ করা আরও সহজ: আমরা যদি তালিকা থেকে 100 তম অবজেক্টটি সরাতে চাই, তাহলে আমাদের কেবল next99 তম অবজেক্টের জন্য ক্ষেত্র পরিবর্তন করতে হবে যাতে এটি 101 তম অবজেক্টের দিকে নির্দেশ করে এবং prev101 তম অবজেক্টের জন্য ক্ষেত্রটি পরিবর্তন করে। বস্তু যাতে এটি 99 তম নির্দেশ করে। এটাই.

কিন্তু 100 তম বস্তু পাওয়া এত সহজ নয়।

5. একটি তালিকা থেকে একটি উপাদান সরান

একটি লিঙ্ক করা তালিকার 100 তম উপাদান পেতে, আপনাকে এটি করতে হবে:

১ম অবজেক্ট পান: আপনি firstঅবজেক্টের ভেরিয়েবল ব্যবহার করে এটি করেন LinkedList। ১ম অবজেক্টের ক্ষেত্রটি next২য় অবজেক্টের একটি রেফারেন্স সঞ্চয় করে। এভাবেই আমরা দ্বিতীয় বস্তুটি পাই। 2য় বস্তুর তৃতীয়টির একটি রেফারেন্স আছে, এবং তাই।

আমাদের যদি 100 তম অবজেক্টের একটি রেফারেন্স পেতে হয় তবে আমাদের ক্রমানুসারে 1 ম থেকে 100 তম অবজেক্টের মধ্য দিয়ে যেতে হবে। এবং যদি আমাদের একটি তালিকায় মিলিয়নম উপাদানের প্রয়োজন হয়, তাহলে আমাদের একের পর এক মিলিয়ন বস্তুর পুনরাবৃত্তি করতে হবে!

এবং যদি এই বস্তুগুলি বিভিন্ন সময়ে তালিকায় যুক্ত করা হয় তবে সেগুলি মেমরির বিভিন্ন অংশে অবস্থিত হবে এবং একই সময়ে প্রসেসরের ক্যাশে শেষ হওয়ার সম্ভাবনা নেই। এর মানে হল যে লিঙ্কযুক্ত তালিকার উপাদানগুলির উপর পুনরাবৃত্তি করা কেবল ধীর নয়, তবে খুব ধীর।

যে আমরা সঙ্গে ডিল করছি কি.

তাহলে কেন আমরা আপনাকে শেখাচ্ছি কিভাবে এই ধীর LinkedListকাজ করে?

ঠিক আছে, চাকরির সাক্ষাত্কারের সময় আপনাকে জিজ্ঞাসা করা হবে কিভাবে LinkedListএর থেকে আলাদাArrayList । স্পষ্টভাবে.