ArrayList Internal Structure: Backing Array, Capacity, and Growth Strategy
ArrayList Internal Structure: Backing Array, Capacity, and Growth Strategy
ArrayList Internal Structure क्या है?
Java में ArrayList एक बहुत ही popular और powerful class है जो dynamic array की तरह काम करती है। इसका मतलब है कि जब आपको पता नहीं होता कि कितने elements store करने हैं, तब ArrayList automatically अपनी size को adjust कर लेती है। यही इसकी सबसे बड़ी खासियत है — Dynamic Resizing।
ArrayList internally एक Array के ऊपर काम करता है, लेकिन ये array fixed नहीं रहता। जैसे-जैसे elements add होते हैं, ArrayList अपने internal array को resize करता है ताकि नए elements store हो सकें।
तो चलिए step-by-step समझते हैं कि ArrayList के अंदर data कैसे store होता है, उसकी capacity कैसे बढ़ती है और growth strategy कैसे काम करती है।
Backing Array (Internal Array)
जब भी आप कोई नया ArrayList object बनाते हैं, उसके अंदर एक hidden Object type array होता है — यही उसका Backing Array कहलाता है।
ये backing array वो जगह होती है जहाँ actual elements store किए जाते हैं। जब आप कोई नया element add करते हैं, तो वो इसी array में stored होता है।
Example:
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
ऊपर के example में internally ArrayList के पास एक Object[] array होता है जो कुछ इस तरह दिखता है:
| Index | Element |
|---|---|
| 0 | "A" |
| 1 | "B" |
| 2 | "C" |
| 3 | null |
| 4 | null |
यहाँ null वाले entries empty slots हैं, जो future में fill होंगी जब आप और elements add करेंगे।
ArrayList Capacity क्या होती है?
Capacity का मतलब है — ArrayList के internal array की current size। यानी कि उसमें कितने elements store करने की space available है।
जब आप बिना size specify किए ArrayList बनाते हैं, तो इसकी initial capacity होती है 10।
Example:
ArrayList<Integer> numbers = new ArrayList<>();
यहाँ numbers list की initial capacity 10 होती है। यानी internally Object[10] create होता है। अगर आप 11वां element add करते हैं तो ArrayList automatically grow हो जाती है।
Custom Capacity Set करना:
ArrayList<String> names = new ArrayList<>(20);
ऊपर वाले example में हमने manually initial capacity को 20 set किया है। इसका मतलब है कि जब तक 20 elements नहीं जुड़ते, array resize नहीं होगा।
ArrayList Growth Strategy (कैसे बढ़ती है Capacity?)
अब सबसे important part — जब ArrayList की capacity खत्म हो जाती है तो क्या होता है?
Java की ArrayList class automatically अपने internal array की size बढ़ा लेती है। ये process Automatic Resizing कहलाता है।
Growth Formula:
जब ArrayList भर जाती है, तो उसकी new capacity इस formula से तय होती है:
newCapacity = oldCapacity + (oldCapacity >> 1)
इसका मतलब — new capacity होती है 1.5 गुना (यानि 50% extra) पुरानी capacity से।
Example:
- अगर old capacity = 10 है, तो new capacity = 10 + (10 / 2) = 15
- अगर old capacity = 15 है, तो new capacity = 15 + (15 / 2) = 22
- अगर old capacity = 22 है, तो new capacity = 22 + (22 / 2) = 33
इस तरह ArrayList धीरे-धीरे grow होती है ताकि हर बार पूरी array को double न करना पड़े और memory का सही इस्तेमाल हो।
Old Array से New Array में Copy कैसे होती है?
जब ArrayList resize होती है, तो Java internally एक नया बड़ा array बनाता है और पुराना array उसमें copy कर देता है।
ये copy process बहुत fast होती है क्योंकि Java में System.arraycopy() method का इस्तेमाल किया जाता है जो low-level optimized है।
Example Process:
- Old array capacity = 10
- New array capacity = 15
- Old array के सारे elements new array में copy कर दिए जाते हैं
- New array अब backing array बन जाता है
Performance Consideration
ArrayList का performance बहुत अच्छा होता है, लेकिन कुछ cases में resizing performance को थोड़ा affect कर सकती है क्योंकि हर resize पर copy operation करना पड़ता है।
Performance Tips:
- अगर आपको approximate elements की संख्या पता है, तो constructor में initial capacity set करें।
- Frequent addition वाले cases में ArrayList की जगह LinkedList consider करें।
- ArrayList random access के लिए perfect है क्योंकि ये internally array पर based है।
Memory Management in ArrayList
जब ArrayList grow होती है, तो पुराना array garbage collector के द्वारा clean कर दिया जाता है। इससे unused memory वापस मिल जाती है।
Java की Garbage Collection mechanism इस पूरे process को manage करती है ताकि memory leak न हो।
ArrayList के Internal Methods
कुछ important internal methods जो ArrayList के resizing और capacity management में role निभाते हैं:
| Method | Description |
|---|---|
| ensureCapacity(int minCapacity) | यह check करता है कि ArrayList की capacity sufficient है या नहीं। अगर नहीं है, तो resize करता है। |
| grow(int minCapacity) | ArrayList को 1.5x size तक बढ़ाता है जब capacity कम पड़ती है। |
| elementData | ये internal Object[] array है जिसमें data store होता है। |
| trimToSize() | Extra unused capacity को remove करता है ताकि memory efficient बने। |
Default Capacity Initialization
जब आप पहली बार element add करते हैं, तो ArrayList lazy initialization करता है। यानी Object[0] array नहीं बनता जब तक कोई element add न हो जाए।
पहले element के add होने पर default capacity initialize होती है जो कि 10 होती है।
ArrayList vs Array (Difference)
| Feature | Array | ArrayList |
|---|---|---|
| Size | Fixed | Dynamic |
| Type | Primitive & Objects | Objects only |
| Resizing | Manual | Automatic |
| Performance | Fast (no overhead) | Slightly slower on resize |
| Ease of Use | Low | High |
ArrayList Internal Working Example (Step-by-Step)
Step 1: Create ArrayList
ArrayList<String> list = new ArrayList<>();
→ Internal array अभी null है (lazy initialization)।
Step 2: Add First Element
list.add("Java");
→ अब internal array create होता है जिसकी capacity = 10 होती है।
Step 3: Add More Elements
list.add("C++");
list.add("Python");
list.add("C#");
list.add("Kotlin");
→ अब array के 5 slots fill हो गए, बाकी 5 empty हैं।
Step 4: Cross Capacity
→ जब 11वां element add होगा, capacity बढ़ेगी (10 → 15)। सभी elements नए array में copy हो जाएंगे।
ArrayList Growth Analysis (Data View)
| Operation | Old Capacity | New Capacity |
|---|---|---|
| First resize | 10 | 15 |
| Second resize | 15 | 22 |
| Third resize | 22 | 33 |
| Fourth resize | 33 | 49 |
ArrayList Memory Optimization Tips
- Always use trimToSize() जब आपको elements add करना बंद करना हो। इससे extra memory release हो जाएगी।
- अगर आपको पता है कितने elements आने वाले हैं, तो ensureCapacity(n) use करें ताकि resizing overhead से बच सकें।
- Frequent remove operations के लिए LinkedList बेहतर होती है क्योंकि ArrayList में shifting होती है।
Real-World Usage Example
ArrayList का internal structure इतना efficient है कि इसे हर modern Java application में data storage, caching और UI elements की list में इस्तेमाल किया जाता है।
ArrayList<String> students = new ArrayList<>();
students.add("Ravi");
students.add("Suman");
students.add("Neha");
students.trimToSize();
यहाँ trimToSize() extra capacity को हटा देता है ताकि memory utilization efficient रहे।
ArrayList Internal Structure Summary
- ArrayList internally Object array पर based होता है।
- Default capacity 10 होती है।
- Capacity 1.5x formula से बढ़ती है।
- Resizing के दौरान पुराने elements नए array में copy होते हैं।
- System.arraycopy() fast copy operation करता है।
- trimToSize() और ensureCapacity() memory optimization में मदद करते हैं।
