ArrayList ও LinkedList ক্লাস দুটি লিস্ট ইন্টারফেসকে ইমপ্লিমেন্ট করে। যার ফলে এদের মেথড ও ফলাফল একইরকম হলেও ইম্প্লিমেন্টেশনের দিক থেকে এদের মধ্যে বেশ কিছু পার্থক্য রয়েছে। পার্থক্যগুলো নিয়ে আলোচনা করার আগে লিস্ট ইন্টারফেসের প্রধান মেথডগুলো দেখা যাক-
1 2 3 4 5 6 | public interface List{ public E get(int index); public void add(E element); public void add(E element, int index); public void remove(int index); } |
উপরের এই মেথডগুলোর ইমপ্লিমেন্টেশন অ্যারেলিস্ট ও লিংকডলিস্ট দুটো ক্লাসেই রয়েছে। ব্যবহারের দিক থেকে এই মেথডগুলোর কোনো পার্থক্য নেই। উদাহরণ-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class TemplateService { public static void main(String[] args) { //using LinkedList List<String> countries = new ArrayList<>(); //adding elements to the ArrayList countries.add("Bangladesh"); countries.add("India"); countries.add("Bhutan"); countries.add("Pakistan"); // searching element by index String bangladesh = countries.get(0); //adding element by index countries.add(2, "Indonesia"); //removing element countries.remove(4); //using LinkedList List<String> cities = new LinkedList<>(); //adding elements to the LinkedList cities.add("Dhaka"); cities.add("London"); cities.add("Beijing"); // searching element by index String dhaka = cities.get(0); //adding element by index cities.add(3, "Islamabad"); //removing element cities.remove(3); } } |
ইমপ্লিমেন্টেশনের দিক থেকে ArrayList উপাদানগুলো রাখার জন্য একটি অ্যারে ব্যবহার করে এবং অ্যারের সাইজ প্রয়োজন অনুযায়ী বড় করতে পারে। অন্যদিকে LinkedList ডাবলি-লিকংডলিস্ট ডেটা স্ট্রাকচার ব্যবহার করে ইমপ্লিমেন্ট করা হয়ছে।
এবার উপরের মেথডগুলোর টাইম কমপ্লেক্সিটি দেখা যাক -
মেথডের নাম | অ্যারেলিস্ট | লিংকডলিস্ট |
E get(int index) | O(1) | O(n) |
void add(E element) | O(1) amortized | O(1) |
void add(E element, int index) | O(n) | O(1) |
void remove(int index) | O(n) | O(1) |
উপরের চার্ট থেকে দেখতে পারি যে, অ্যারেলিস্ট থেকে কোনো উপাদান খুব দ্রুত খুঁজে বের করা যায় লিংকলিস্টের চেয়ে। এর কারণ, অ্যারেলিস্ট উপাদানগুলো রাখার জন্য একটি অ্যারে ব্যবহার করে যা থেকে কোনো উপাদানের ইনডেক্স জানা থাকলে কনস্ট্যান্ট টাইমে বের করে আনা যায়। অপর দিকে লিংকলিস্ট যেহেতু ডাবলি-লিংকলিস্ট ডেটা স্ট্রাকচার ব্যবহার করে, তাই কোনো উপাদান খুঁজে বের করতে সবগুলো উপাদান খুঁজতে হয়। এজন্যে লিংকলিস্টে কোনো উপাদান অ্যাকসেস করার সময় সময় O(n)।
অ্যারেলিস্টে ডাইনামিক অ্যারে ব্যবহার করা হয়। আমরা জানি যে অ্যারে একটি নির্দিষ্ট দৈর্ঘ্যের (length) উপাদান রাখতে পারে। তবে ডাইনামিক অ্যারের দৈর্ঘ্য প্রয়োজন মতো বাড়ানো বা কমানো যায়। এটি করার পদ্ধতিটি হলো - প্রথমে একটি নির্দিষ্ট দৈর্ঘ্যের অ্যারে তৈরি করা হয়। অ্যারেটি উপাদান পূর্ণ হয়ে গেলে একটি নতুন দৈর্ঘ্যের অ্যারে তৈরি করা হয় যা আগের অ্যারের দৈর্ঘ্যের চেয়ে বড়। আগের অ্যারে থেকে উপাদানগুলো কপি করে নতুন অ্যারেতে রাখা হয় এবং এতে যে অতিরিক্ত ফাঁকা ঘরগুলো রয়ে যায় সেগুলোতে নতুন উপাদান রাখা হয়। এভাবে আবার অ্যারিটি পুর্ণ হয়ে গেলে নতুন দৈর্ঘ্যের অ্যারে তৈরি করা হয়। তবে নতুন দৈর্ঘ্য একটি চিন্তা ভাবনা করে নেওয়া হয় যাতে প্রতিবার নতুন উপাদান যুক্ত করার জন্য অ্যারের দৈর্ঘ্য বৃদ্ধি করার প্রয়োজন না পারে। যেমন- প্রতিবার অ্যারের দৈর্ঘ্য বৃদ্ধির সময় আমরা আগের দৈর্ঘ্যের চেয়ে দিগুণ নেওয়া পারে। এর ফলে প্রতিবার নতুন উপাদান যুক্ত করার সময় নতুন অ্যারে তৈরি এবং আগের অ্যারে থেকে কপি করার কাজ করতে হয় না, বরং এটি একটি নির্দিষ্ট সময় পর পর প্রয়োজন হয়।
অ্যারেলিস্টের অ্যারেতে প্রথমে একটি 10 দৈর্ঘ্যের অ্যারে থাকে। এটি পূর্ণ হয়ে গেলে নতুন অ্যারে তৈরি করা হয় যা আগের অ্যারে থেকে দেড় গুণ হয়। এই অ্যারের দৈর্ঘ্যের বৃদ্ধির ফরমুলা হলো -
int newCapacity = oldCapacity + (oldCapacity >> 1);
এখানে capacity হচ্ছে অ্যারেলিস্টের ভেতরের অ্যারের দৈর্ঘ্য।
অর্থাৎ আমরা যদি 10 টি উপাদান অ্যারেতে যুক্ত করতে চাই, তাহলে এই অ্যারের দৈর্ঘ্য বৃদ্ধি করার প্রয়োজন নেই। তবে যদি n টি উপাদান যুক্ত করতে চাই, তাহে বেশ কতবার দৈর্ঘ্য বৃদ্ধি করা ও আগের অ্যারে থেকে উপাদান কপি কররে আনার প্রয়োজন পরবে।
তাহলে n সংখ্যক উপাদান যুক্ত করার সময় O(n) + মাঝে মধ্যে কপি অপারেশন (একটি লুপের মাধ্যমে আগের n আইটেম কপি করা)আমরা সাধারণভাবে বলতে পারি, গড়ে এর টাইম কমপ্লেক্সিটি (amortized) O(1)
অ্যারেলিস্টের শেষে যুক্ত না করে মাঝে কেনাে উপাদান যুক্ত করতে হলে যেই উপাদান থেকে পরের উপাদানগুলো শিফট (কপি করে এক ঘর সরানো) করার প্রয়োজন হবে। একদম শুরুতে যদি উপাদান যুক্ত করতে হয় তাহলে সবগুলো উপাদান প্রথমে থেকে ডান দিকে শিফট করতে হবে সেক্ষেত্রে এর কম্প্লিক্সিটি হবে O(n)
অ্যারেলিস্ট থেকে কোনো উপাদান রিমুভ করতে হলেও এই শিফ্টিং বা কপি করার প্রয়োজন পরে। অ্যারের লিস্টের মাঝ থেকে কোনো উপাদান রিমুভ করতে হলে, মাঝ থেকে পরবর্তি উপাদানগুলো কপি করে একঘর সামনে আনতে হয়। উপাদানটি যদি প্রথমে হয়, তাহলে সবগুলো উপাদান কপি করে সামনে আনতে হয়। তবে শেষ থেকে উপাদান রিমুভ করলে এর টাইম কমপ্লেক্সিটি হয় O(1) কারণ এতে কোনো কপি বা শিফটিংয়ের প্রয়োজন হয় না।
সুতরাং দেখা যাচ্ছে যে, অ্যারেলিস্ট থেকে কোনো উপাদান রিমুভ করার করার কমপ্লেক্সিটি সাধারণভাবে O(n)
অপরদিকে লিংকলিস্টে কোনো উপাদান যুক্ত করার সময় O(1) । লিংকলিস্ট যেহেতু ডাবলিলিংকলিস্ট ডেটা স্ট্রাকচার ব্যবহার করে তাই এর প্রত্যেকটি নোড এর আগের এবং পরের নোডের রেফারেন্স ধরে রাখে। এক্ষেত্রে কোনো উপাদান যুক্ত করার ক্ষেত্রে কোনো কপি বা শিফটিংয়ের প্রয়োজন নেই, বরং শুধুামাত্র দুটি পয়েন্টারের পরিবর্তন ছাড়া।
একইভাবে লিংকলিস্ট থেকে কোনো উপাদান রিমুভ করার ক্ষেত্রে কোনো কপি বা শিফটিংয়ের প্রয়োজন নেই, শুধুমাত্র দুটি রেফারেন্সের পরিবর্তন হয়। তাই এর টাইম কমপ্লেক্সিটি O(1)।
এখন প্রশ্ন হচ্ছে তাহলে কখন কোনটি ব্যবহার করা উত্তম।
সাধারণভাবে আমরা সব কাজেই অ্যারেলিস্ট ব্যবহার করে থাকি। তবে কোনটি করা উচিৎ তা নির্ভর করে কী কাজ করছি তার উপর। যেমন- উপাদান যুক্ত করার চেয়ে অনেক বেশিবার অ্যাকসেস করার প্রয়োজন হলে অথবা আগে থেকেই কতগুলো উপাদান রাখার প্রয়োজন হবে তা সম্পর্কে ধারণা থাকলে অ্যারেলিস্ট ব্যবহার করা উচিত।
অন্যদিকে আমাদের যদি অ্যাকসেস করার চেয়ে অনেক বেশি উপাদান যুক্ত বা রিমুভ করার প্রয়োজন হয় তাহলে লিংকলিস্ট ব্যবহার করা উত্তম।
