ArrayList
FrontendMasters က data structure and alogrithm video တစ်ပုဒ်ကြည့်ပီး ArrayList အကြောင်းနားလည်သလောက်ရေးမယ်ဆိုတဲ့စိတ်ကူးပေါက်လာတာနဲ့ရေးထားတာပါ။
Disclaimer: ဒီ article ကိုအကောင်းဆုံးရေးထားပေမယ့် information အမှားများ စာလုံးပေါင်းအမှားများပါနိုင်ပါတယ်။ အကယ်၍မှားနေသည်ရှိသော် လွဲနေသည်ရှိသော် ဝေဖန်အကြံပေးနိုင်ပါသည်။
များသောအားဖြစ် static typed programing language တွေရဲ့ Array တွေက fixed size တွေဖြစ်ကြတယ်။ သူတို့ရဲ့ size တွေကိုကြီးချင်တာ၊ သေးချင်တာတို့ကိုလုပ်လို့မရဘူး။ အဲ့ဒါကိုဖြေရှင်းဖို့အတွက်က ArrayList ဆိုတဲ့ data structure က Array ကို dynamic ဖြစ်အောင် လုပ်ဆောင်ပေးတယ်။
ArrayList ကဘယ်လို dynamic ဖြစ်အောင်ဘယ်လိုလုပ်ဆောင်ပေးလဲမပြောခင် fixed size ဖြစ်တယ်ဆိုတာဘယ်လိုမျိုးလဲအရင်သိဖို့လိုအပ်တယ်။
Static Typed Programing language တွေဖြစ်တဲ့ Java, C, C++, etc. တွေမှာ Array တွေကိုသုံးတော့မယ်ဆိုရင် သူ့ထဲထည့်မယ့် data type ပြီးရင် သူ့ရဲ့ ဘယ်နခု (သို့) ဘယ်နခန်း သိမ်းမယ်ဆိုတာကိုသတ်မှတ်ပေးရတယ်။
ဥပမာ - Java မှာဆိုရင်
int[] num = new int[5];လို့သတ်မှတ်လိုက်ရင် Array ငါးခန်းထက်ပိုသိမ်းခွင့်မရှိဘူး။
အကယ်၍ပိုသိမ်းချင်တယ် ဒါမှမဟုတ် လိုအပ်လာရင် ArrayList ဆိုတဲ့ data structure ရဲ့အခန်းကဏ္ဍကအရေးပါလာတယ်။
အဲ့ဒါဆို ArrayList ကဘယ်လိုအလုပ်လုပ်တာလဲ။ ဘာကြောင့်မလို့ Array ကို dynamic ဖြစ်လာစေတာလဲ။
ArrayList ကအရင်ဦးဆုံး memory မှာ Array ကဲ့သို့နေရာယူတယ် ဒါပေမယ့် Array လို fixed-size ဖြစ်မနေပဲ အစနဲ့အဆုံး(Index 0, Last index) တွေရဲ့ဘေးတွေမှာ ပိုပြီးနေရာ(memory) ကိုပိုပြီး ယူ(allocate)လုပ်ထားတယ်။ အောက်ကပုံမှာကြည့်နိုင်တယ်။

အပေါ်က ArrayList ရဲ့ပုံမှာ Capacity ကသူအမှန်တကယ်နေရာယူထားတဲ့ size ဖြစ်ပြီး length သူ data သိမ်းထားတဲ့အရေအတွက်ဖြစ်တယ်။ ArrayList ကပိုပြီးနေရာယူထားတဲ့အတွက် data ကိုအနောက်မှာသို့မဟုတ်အရှေ့မှာထည့်တဲ့အခါမှပိုမိုလွယ်ကူသွားတယ်၊ ပိုမြန်သွားတယ်။
အဲ့ဒါဆိုဘာလို့ Array ထက်ပိုမြန်တယ် ပိုလွယ်ကူတယ်ပြောတာလဲ။
အောက်ကဥပမာမှာကြည့်ကြည့်ပါ။

Array ထဲကို value အသစ်ထည့်မရဘူး။ သို့ပေမယ့်ထည့်လို့ရတဲ့နည်းတော့ရှိပါတယ်။ အဲ့ဒါကတော့
- Array အသစ်ကို length အသစ်နဲ့ဆောက်မယ်။
- Array အဟောင်းထဲက value တွေတစ်ခုချင်းကို copy ကူးထည့်သွားရမယ်။
- နောက်ဆုံးမှာတော့ ထည့်ချင်တဲ့ value အသစ်ကိုထည့်မယ်။
အဲ့လိုနည်းက Array ကို clone လုပ်ပြီး data အသစ်ကိုထည့်တယ်လို့ပြောလို့ရတယ်။ အဲ့နည်းက data အသစ်ထည့်ဖို့အတွက် Array အဟောင်းထဲက data တစ်ခုချင်းစီကို Array အသစ်ထဲကူးထည့်ရတယ်။ အဲ့ဒါကြောင့် Time complexity ကပိုများသွားစေတယ်။ data အသစ်ကို Array အဆုံးမှာထည့် (push operation) ဖို့အတွက် O(N) Linear Time Complexity ဖြစ်တယ်။
Array ရဲ့အစမှာ data ထည့်ချင်လဲထိုနည်းတူပါပဲ သူကတစ်ဆင့်တော့ပိုပါလာတယ်။ အဲ့ဒါကတော့ Array value အားလုံးကိုနောက်ကိုတဆင့်ပို့လိုက်ရတာပါပဲ။ သူရဲ့ Time Complexity ကလဲ O(N) ပါပဲ။
အဲ့ဒါဆို ArrayList ကအဲ့လို operation မှာပိုမြန်တယ်လို့ပြောရတာလဲ။
ArrayList ရဲ့ data အသစ်ကိုနောက်ဆုံးမှာဘယ်လိုထည့်လဲ တနည်းအားဖြင့် push operation ဘယ်လိုလုပ်လဲဆိုတာအောက်ပုံမှတချက်ကြည့်ကြည့်ပါ။

ArrayList နဲ့နောက်ဆုံး index(tail) ရဲ့နောက်မှာကြိုတင်နေရာ (memory) ယူထားတဲ့နေရာမှာ ကိုယ့်ရဲ့ value အသစ်ကိုထည့်တယ်။ ArrayList Length ကိုတစ်တိုးလိုက်ပါတယ်။
ArrayList မှာ push operation ကိုလုပ်ဖို့ step တွေနည်းပြီး time complexity နည်းတယ်။ ဘာလို့ဆို Array အဟောင်းကြီးကိုပြန် copy စရာမလိုတော့ပဲထည့်ချင်တဲ့ value ကိုထည့်ရုံပါပဲ။ သူ့ရဲ့ပုံမှန် Time complexity ကတော့ O(1) Constant Time Complexity ပါ။
သူ့မှာအားနည်းချက်တစ်ခုရှိပါတယ် အဲ့ဒါကဘာလဲဆိုရင် ကြိုတင်ယူထားတဲ့နေရာ (memory) တွေကုန်သွားတာမျိုးဖြစ်နိုင်ပါတယ်။

အပေါ်ကလို new data ကရှိတဲ့နေရာထပ်ပိုများနေတဲ့အခါ ထည့်မရတော့ပါဘူး။ အဲ့ပြဿနာကိုဖြည့်ရှင်းဖို့ကတော့ Array တုန်းကလုပ်သလိုလုပ်မှရပါတော့မယ်။ ဆိုလိုတာက ArrayList အသစ်ကို Capacity အသစ် နဲ့လုပ်ပြီး data တွေကိုတစ်ခုချင်း ArrayList အဟောင်းထဲကနေ ArrayList အသစ်ထဲကိုထည့်ရပါတော့တယ်။ အဲ့ဒီလိုပြန်လုပ်ရတဲ့အတွက်သေချာတာကတော့ Time complexity ကတော့ O(N) ဖြစ်သွားပါတယ်။ ဆိုလိုတာပိုကြာသွားပါမယ်။
အဲ့လိုပါပဲ new value ကိုအရှေ့ကနေထည့်မယ်ဆိုလဲ Value တွေကိုနောက်တစ်ခုချင်းစီရွှေ့ရပါတယ် အဲ့ဒီ့နေရာမှာလဲ Time complexity ကတော့ O(N) ပါပဲ Array ရဲ့ time complexity နဲ့တူတူဖြစ်သွားပါတယ်။
မှတ်ရမှာတစ်ခုတော့ရှိပါတယ်
အဲ့ဒါကတော့ Java နဲ့တချို့သော Programing Language မှာ Array နဲ့ ArrayList ဆိုပြီးခွဲခြားမြင်တွေ့ရနိုင်ပြီး JavaScript မှာတော့ Array လို့ခေါ်ပေမယ့် သူက dynamic array ဖြစ်တဲ့အတွက် ArrayList ကဲ့သိုပြုမူပါတယ်။ အဲ့ဒါကတော့ကျွန်တော်တို့မသိပဲသုံးနေတဲ့ JavaScript Array အလုပ်လုပ်ပုံပါပဲ။
ဆိုတော့က Array, ArrayList, Linked List တို့ရဲ့ Time complexity တွေကသိပ်မကွာဘူး။ အဲ့တော့ဘယ်ဟာသုံးရမှာလဲ။ အဖြေကတော့အခြေအနေအရပါပဲ။ အကြမ်းဖျင်းအားဖြင့် -
- Array: Data size ဘယ်လောက်ထည့်မလဲဆိုတာသိတယ်၊ index နဲ့ value တွေဆွဲထုတ်ချင်တယ်၊ push/pop operation တွေသိပ်မလုပ်ဘူးဆိုရင် Array ကိုသုံးနိုင်တယ်။
- ArrayList: Array လိုသုံးဖို့လဲလိုအပ်မယ် push/pop operation တွေလုပ်ဖို့လဲလိုမယ်ဆိုရင် ArrayList ကပိုသင့်တော်တယ်။
- Linked List: Data တွေကို ဖျက်တာ အသစ်ထည့်တာ လုပ်ဖို့များမယ်၊ index နဲ့ data ယူတာမျိုးမလိုဘူး၊ data size ကလဲဘယ်လောက်ရှိလဲဆိုတာမသိဘူးဆိုရင် Linked List ကတော့အသင့်တော်ဆုံးဖြစ်ပါတယ်။

This article was inspired by The Last Algorithms Course You'll Need by ThePrimeagen on FrontendMasters.
