Module ৫ · list আর forward_list: যখন element নড়ে কিন্তু position নড়া চলবে না
ভেতরের কথা: list-এর node, sentinel, আর একটা walk-এর আসল খরচ
Proপড়া
Kenji ওর পরীক্ষার নম্বরগুলো vector থেকে list-এ সরিয়ে নিয়েছে, কারণ list নাকি "O(1)-এ insert করে"। এখন দশ লাখ নম্বর যোগ করার program-টা আগের চেয়ে ধীর, অথচ ও মাঝখানে কিছুই insert করে না। "Walk তো দুইটাতেই O(n)। তাহলে সময়টা গেল কোথায়?" Amara বলে, O বলে খরচ কীভাবে বাড়ে, একটা ধাপের দাম কত সেটা বলে না। এই lesson list-কে node ধরে ধরে খুলবে, আর প্রতিটা ধাপ মাপবে।
আপনার জন্য এই lesson টা খোলা কি না দেখা হচ্ছে…
ভেতরের কথা: list-এর node, sentinel, আর একটা walk-এর আসল খরচ এর ভেতরে কী আছে
- একটা node: দুইটা link আর একটা মান
- List object আর তার sentinel
- forward_list: একটা pointer আর মাথার একটা ঘর
- size() কেন O(1), আর কোন splice তার দাম দেয়
- list::sort node-এর link বদলায়, মান কখনো copy করে না
- Insert বা erase কী ভাঙে: শুধু মুছে যাওয়া node-টা
- Performance lab