LinkedList vs ArrayList: Insertion, Deletion, and Access Performance
LinkedList vs ArrayList: Insertion, Deletion, and Access Performance
Introduction
जब भी हम Java में data store करने की बात करते हैं, तो दो सबसे ज़्यादा popular classes सामने आती हैं — ArrayList और LinkedList। दोनों List interface को implement करती हैं, लेकिन इनके internal working और performance में बड़ा difference होता है।
Exam point of view से भी यह topic बहुत important है, क्योंकि questions अक्सर आते हैं — “Which is faster: ArrayList or LinkedList?” या “Difference between LinkedList and ArrayList in terms of insertion, deletion, and access performance.”
तो चलिए step by step समझते हैं कि LinkedList और ArrayList में actual difference क्या है, और किस situation में कौन better perform करता है।
ArrayList और LinkedList के Basics
सबसे पहले ये समझो कि ArrayList internally एक dynamic array की तरह काम करता है, जबकि LinkedList एक doubly linked structure पर आधारित होता है।
| Feature | ArrayList | LinkedList |
|---|---|---|
| Internal Structure | Dynamic Array | Doubly Linked Nodes |
| Memory Usage | Less (continuous memory) | More (extra pointers) |
| Access Time | Fast (index-based) | Slow (traversal required) |
| Insertion/Deletion | Slow (shifting needed) | Fast (just link updates) |
| Random Access | Yes (direct access via index) | No (sequential traversal) |
Insertion Performance
1. ArrayList Insertion
जब हम ArrayList में new element add करते हैं, तो वह internally array में store होता है। अगर array में space available है, तो insertion O(1) time में हो जाता है। लेकिन अगर array भर चुका है, तो Java एक नया बड़ा array बनाता है और पुराने elements को उसमें copy करता है — जिससे time complexity O(n) हो जाती है।
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C"); // O(1)
list.add(1, "X"); // O(n) क्योंकि shifting होती है
अगर आप बीच में या शुरुआत में element insert करते हो, तो बाकी सारे elements को shift करना पड़ता है। इसलिए middle या beginning insertion के लिए ArrayList efficient नहीं है।
2. LinkedList Insertion
LinkedList में हर element एक node के रूप में store होता है, जिसमें data और next, previous pointers होते हैं। Insertion के समय केवल pointers को update करना होता है, किसी shifting की जरूरत नहीं पड़ती।
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add(1, "X"); // O(1) (pointer manipulation)
इसलिए LinkedList का insertion performance middle या beginning positions पर ArrayList से कहीं बेहतर होता है।
- ArrayList insertion time complexity: O(n)
- LinkedList insertion time complexity: O(1)
Deletion Performance
1. ArrayList Deletion
ArrayList में अगर आप किसी specific index से element हटाते हैं, तो उसके बाद वाले सारे elements को एक step पीछे shift करना पड़ता है। इसलिए deletion operation भी O(n) time लेता है।
list.remove(1); // O(n)
यह problem इसलिए होती है क्योंकि ArrayList continuous memory block में elements रखता है।
2. LinkedList Deletion
LinkedList में किसी node को हटाने के लिए बस उसके pointers update करने होते हैं। न कोई shifting होती है, न reallocation। इसलिए deletion बहुत तेज होता है।
linkedList.remove(1); // O(1)
बस ध्यान रहे, deletion से पहले उस node तक पहुँचना पड़ेगा, इसलिए index-based removal के case में overall complexity O(n) भी हो सकती है।
- ArrayList deletion time complexity: O(n)
- LinkedList deletion time complexity: O(1) (after node found)
Access Performance
1. ArrayList Access
ArrayList में direct access possible है क्योंकि यह index-based structure है। हर element sequential memory में होता है, इसलिए get(index) operation O(1) time लेता है।
String value = list.get(2); // O(1)
इस वजह से ArrayList को random access के लिए prefer किया जाता है।
2. LinkedList Access
LinkedList में direct index-based access नहीं होता। किसी index तक पहुंचने के लिए उसे starting से traverse करना पड़ता है, जिससे access time O(n) हो जाता है।
String value = linkedList.get(2); // O(n)
इसलिए अगर आपका use case random access पर dependent है, तो ArrayList हमेशा बेहतर रहेगा।
- ArrayList access time: O(1)
- LinkedList access time: O(n)
Memory Usage Comparison
ArrayList memory-efficient होता है क्योंकि यह continuous memory में data store करता है। जबकि LinkedList को हर node के साथ दो extra pointers (next और previous) की जरूरत होती है।
| Parameter | ArrayList | LinkedList |
|---|---|---|
| Memory Requirement | Low | High (extra node overhead) |
| Storage Type | Contiguous block | Non-contiguous block |
अगर dataset बहुत बड़ा है और memory constraint है, तो ArrayList choose करना better option होगा।
Iteration Performance
दोनों lists iteration support करती हैं, लेकिन LinkedList में iterator थोड़ा slow होता है क्योंकि हर बार pointers follow करने पड़ते हैं। जबकि ArrayList में sequential memory होने के कारण iteration fast होता है।
// Iterating ArrayList
for(String val : list){
System.out.println(val);
}
इसलिए अगर आपका use case heavy iteration से जुड़ा है, तो ArrayList का performance बेहतर रहेगा।
Use Cases (कहाँ कौन सी List बेहतर है)
अब देखते हैं कि किस situation में कौन सी list को use करना चाहिए —
| Use Case | Recommended List | Reason |
|---|---|---|
| Frequent read operations | ArrayList | Fast random access |
| Frequent insert/delete in middle | LinkedList | No shifting required |
| Memory-sensitive applications | ArrayList | Less overhead |
| Queue or stack implementation | LinkedList | Efficient insertion/removal |
| Simple, fixed data storage | ArrayList | Compact and fast |
Real World Example
मान लीजिए आप एक library management system बना रहे हैं जिसमें आपको books की list maintain करनी है। अगर books rarely add या delete होती हैं और ज्यादातर access करनी होती हैं — तो ArrayList सही रहेगा।
लेकिन अगर system में लगातार books add/delete करनी पड़ती हैं (जैसे queue), तो LinkedList बेहतर रहेगा क्योंकि वो frequent modifications को efficiently handle करता है।
Time Complexity Summary Table
| Operation | ArrayList | LinkedList |
|---|---|---|
| Access (get) | O(1) | O(n) |
| Insert (at end) | O(1) | O(1) |
| Insert (in middle) | O(n) | O(1) |
| Delete (by index) | O(n) | O(1) |
| Iteration | O(n) | O(n) |
| Memory usage | Low | High |
Exam Specific Important Notes
- ArrayList internally dynamic array use करता है।
- LinkedList doubly linked nodes use करता है।
- ArrayList में insertion/deletion slow होती है क्योंकि shifting होती है।
- LinkedList में insertion/deletion fast होती है क्योंकि केवल pointers बदलते हैं।
- Access के लिए ArrayList तेज है, क्योंकि index-based direct access possible है।
- LinkedList memory ज़्यादा consume करता है क्योंकि हर node में extra pointers होते हैं।
- अगर data frequently modify हो रहा है, तो LinkedList use करो।
- अगर data static या rarely बदलता है, तो ArrayList best रहेगा।
- Random access के लिए हमेशा ArrayList prefer करें।
- LinkedList का use stack, queue, या graph representation में ज्यादा होता है।
Quick Summary Table
| Parameter | ArrayList | LinkedList |
|---|---|---|
| Data Structure | Dynamic Array | Doubly Linked List |
| Insertion | Slow (O(n)) | Fast (O(1)) |
| Deletion | Slow (O(n)) | Fast (O(1)) |
| Access | Fast (O(1)) | Slow (O(n)) |
| Memory Efficiency | Better | Worse |
| Best For | Read-heavy operations | Insert/delete-heavy operations |
Key Takeaway
अगर आपका focus fast access पर है तो ArrayList चुनिए। अगर आपका focus fast insertion और deletion पर है तो LinkedList best choice है। Java Developer के लिए दोनों को समझना जरूरी है क्योंकि दोनों की use case-specific strengths अलग हैं।
