৯-৭ঃ Complexity Analysis

এখন আমরা array, singly linked list, doubly linked list এর বিভিন্ন method/task এর time complexity দেখে নেই। এতে করে আমরা এই 3 ধরনের data structure এর মধ্যে কোনটা বেশি efficient তা বের করা চেষ্টা করবো।

Time Complexity Comparison of Array vs Linked Lists

Insert at head: এই Task এ array তে সবচেয়ে বেশি complexity লাগছে, কারণ array এর ক্ষেত্রে আমাদের বাকি সব valueকে অন্য position এ নিয়ে তারপর head এ value insert করতে হয়। অন্যদিকে singly and doubly linked list এ head node এর সাথে new node এর connection create করলেই হয়ে যায়।

Insert at tail: এইক্ষেত্রে কোনো value shift করতে হচ্ছে না just last এ add করতে হচ্ছে তাই সবক্ষেত্রে same complexity কাজ করছে।

Insert at position: এখানে 3 টা data structure এই same O(n) আসে। কারণ প্রতিবার আমাদের একটা নির্দিষ্ট position এ অব্দি loop চালাতে হচ্ছে।

Delete head: singly ও doubly linked list এ head track রাখা যায় আর delete করা মানে head এ যে node আছে সেটা disconnect করে দেয়া মূলত, তাই এদের বেলায় O(1) complexity. আর array এর বেলায় delete head এ কোনো value delete করতে হলে পরের value গুলোর position shift করতে হবে, তাই array এর জন্য O(n) complexity আসে।

Delete tail: এখানে array এবং doubly linked list এ শেষ position টা আমরা track রাখতে পারি বা সহজে access করতে পারি, তাই শেষ বা tail value delete করতে আমাদের O(1) complexity হয়। কিন্তু singly linked list এর বেলায় tail track রাখা হয় না , তাই tail অব্দি যেতে আমাদের পুরো list ঘুরে যেতে হয়। তাই এর tail delete করার জন্য আমাদের singly list এর জন্য O(n) complexity আসে।

Delete at position: insert এর মতো delete এর বেলায় ও ঠিক একই logic এর জন্য এই 3 data structure (array, signly linked list and doubly linked list) এর জন্য O(n) complexity পাওয়া যাচ্ছে।