Java Academy · पाठ

LinkedList बनाम ArrayList: समझौते

सही list प्रकार चुनने के लिए insertion, deletion और random access के performance की तुलना करें।

पाठ 3, कुल 4 में से13 चरण

LinkedList बनाम ArrayList: समझौते, CoddyKit पर Java Academy का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Java Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Java Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

मूल प्रश्न

ArrayList और LinkedList दोनों List को लागू करते हैं, इसलिए उनका एपीआई समान है। अंतर उनकी आंतरिक डेटा संरचनाओं और उन संचालनों में है जिन्हें प्रत्येक कुशलता से करता है।

ArrayList की आंतरिक संरचना

ArrayList तत्वों को एक सन्निहित सारणी में रखता है। जब सारणी भर जाती है, तो उसे उससे 1.5× बड़ी नई सारणी से बदल दिया जाता है और सभी तत्वों की प्रतिलिपि बनाई जाती है।

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

LinkedList की आंतरिक संरचना पर एक और नज़र

प्रत्येक तत्व अपने अलग Node ऑब्जेक्ट में रहता है, जिसमें पिछले/अगले संकेतक होते हैं। कोई सन्निहित मेमोरी नहीं होती — Node हीप पर कहीं भी हो सकते हैं।

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

यादृच्छिक पहुँच: ArrayList बेहतर

ArrayList.get(i) O(1) है — सारणी इंडेक्स तक सीधी पहुँच। LinkedList.get(i) O(n) है — यह अधिकतम n/2 Nodes का traversal करता है।

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

सिर पर प्रविष्टियाँ: LinkedList बेहतर

ArrayList में इंडेक्स 0 पर जोड़ने के लिए सभी तत्वों को खिसकाना पड़ता है — O(n)। LinkedList केवल दो संकेतकों को अपडेट करता है — O(1)।

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

पूंछ पर प्रविष्टियाँ: लगभग समान

ArrayList और LinkedList दोनों पूंछ पर परिशोधित O(1) में तत्व जोड़ते हैं। ArrayList कभी-कभी आकार बढ़ाने और प्रतिलिपि बनाने की प्रक्रिया शुरू करता है, लेकिन परिशोधित जटिलता फिर भी O(1) रहती है। LinkedList एक नया Node आवंटित करता है — आकार बढ़ाने की आवश्यकता नहीं होती।

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

मेमोरी का उपयोग

ArrayList: प्रति तत्व लगभग 8 बाइट (सारणी में एक संदर्भ)। LinkedList: प्रति तत्व लगभग 48 बाइट (डेटा, पिछले और अगले संकेतकों तथा ऑब्जेक्ट हेडर वाला Node ऑब्जेक्ट)। बड़े डेटा-समुच्चयों के लिए ArrayList बहुत कम मेमोरी उपयोग करता है।

पुनरावृत्ति का प्रदर्शन

क्रमिक पुनरावृत्ति (हर-तत्व पुनरावृत्ति या इटरेटर) दोनों के लिए O(n) है। लेकिन ArrayList को CPU कैश की प्रीफ़ेचिंग से लाभ मिलता है — तत्व मेमोरी में सन्निहित होते हैं। LinkedList के Node हीप पर अलग-अलग स्थानों पर होते हैं, जिससे कैश मिस होते हैं।

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

मध्य में प्रविष्टि/हटाना

दोनों में स्थिति खोजने के लिए O(n) समय चाहिए। स्थिति मिल जाने पर ArrayList तत्वों को O(n) में खिसकाता है; LinkedList केवल O(1) में संबंध हटाता है। इसलिए, जब आपके पास पहले से इटरेटर हो और मध्य में बार-बार बदलाव करने हों, तब LinkedList बेहतर है; अन्यथा दोनों लगभग समान हैं।

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

निर्णय मार्गदर्शिका

अपने प्रमुख संचालन के आधार पर चुनें:

ArrayList: यादृच्छिक पहुँच, पुनरावृत्ति और पूंछ पर जोड़ना — 90% उपयोगों के लिए पर्याप्त
LinkedList: head/tail पर बार-बार प्रविष्टि/हटाना, कतार/डबल-एंड कतार/स्टैक लागू करना
ArrayDeque: शुद्ध कतार या स्टैक की आवश्यकता होने पर, LinkedList से बेहतर

बेंचमार्क का सारांश

प्रदर्शन के लिए मानसिक मॉडल:

get(i): ArrayList O(1) बनाम LinkedList O(n)
add(0,x): ArrayList O(n) बनाम LinkedList O(1)
add(x): दोनों की परिशोधित जटिलता O(1)
इटरेटर से हटाना: स्थिति तय होने के बाद दोनों में O(1)
प्रति तत्व मेमोरी: ArrayList लगभग 8B बनाम LinkedList लगभग 48B

त्वरित जाँच

आप एक कार्य-कतार बना रहे हैं, जिसमें कार्यों को अंत में जोड़कर सामने से प्रति सेकंड लाखों बार हटाया जाता है। कौन-सी डेटा संरचना सबसे उपयुक्त है?

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन: LinkedList बनाम ArrayList

मुख्य बातें:

ArrayList यादृच्छिक अभिगम (O(1)) और कैश-अनुकूल पुनरावृत्ति में उत्कृष्ट है
LinkedList शीर्ष/अंत संचालन O(1) होने के कारण उत्कृष्ट है
मेमोरी: ArrayList लगभग 8B/तत्व; LinkedList लगभग 48B/तत्व
कतारों/स्टैक के लिए LinkedList की तुलना में ArrayDeque को प्राथमिकता दें
अधिकांश परिस्थितियों में ArrayList सही डिफ़ॉल्ट विकल्प है

शुरुआत निःशुल्क

एआई शिक्षक के साथ Java सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 104
पाठ: 374

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “LinkedList बनाम ArrayList: समझौते” पाठ निःशुल्क है?

हाँ—“LinkedList बनाम ArrayList: समझौते” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Java Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Java Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“LinkedList बनाम ArrayList: समझौते” में मैं क्या सीखूँगा?

सही list प्रकार चुनने के लिए insertion, deletion और random access के performance की तुलना करें। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Java Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या Java Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Java Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।

“LinkedList बनाम ArrayList: समझौते” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस Java Academy पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर Java Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← Java Academy पर वापस जाएँ