🚀 🧑🏿‍🤝‍🧑🏽 ⏰ चित्रों में डेटा संरचनाएं। LinkedList 👄 🐏 🍃

अभिवादन हरजितेली!

मैं जारी रखता हूं कि मैंने क्या शुरू किया था, अर्थात्, मैं यह बताने की कोशिश कर रहा हूं (दृश्य चित्रों का उपयोग करके) कि कैसे जावा में कुछ डेटा संरचनाएं लागू की जाती हैं।

पिछली बार हमने ArrayList के बारे में बात की थी, आज हम LinkedList को देख रहे हैं।

लिंक्डलिस्ट - सूची इंटरफ़ेस को लागू करता है। यह एक द्विदिश सूची का प्रतिनिधि है, जहां संरचना के प्रत्येक तत्व में पिछले और अगले तत्वों के संकेत होते हैं। पुनरावृत्त राउंड ट्रिप का समर्थन करता है। सूची के आरंभ, मध्य और अंत में प्राप्त करने, हटाने और चिपकाने के तरीके। आपको अशक्त सहित किसी भी तत्व को जोड़ने की अनुमति देता है।

वस्तु निर्माण

List<String> list = new LinkedList<String>();

Footprint{Objects=2, References=4, Primitives=[int x 2]}
Object size: 48 bytes

नई बनाई गई सूची ऑब्जेक्ट में हेडर और आकार के गुण हैं।

हेडर - सूची का छद्म तत्व। इसका मान हमेशा शून्य होता है , और इसके बाद वाले गुण क्रमशः सूची के पहले और अंतिम तत्व की ओर इंगित करते हैं। चूंकि सूची अभी भी खाली है, इसलिए अगले और मौजूदा गुण खुद को इंगित करते हैं (यानी, हेडर तत्व के लिए)। आकार सूची का आकार 0 है।

 header.next = header.prev = header;

आइटम जोड़ना

 list.add("0");

Footprint{Objects=5, References=8, Primitives=[int x 5, char]}
Object size: 112 bytes

जोड़ें (मान) , addLast (मान) विधि का उपयोग करके सूची के अंत में एक आइटम जोड़ें
और AddFirst (मान) का उपयोग करके सूची के शीर्ष पर जोड़ना O (1) समय में किया जाता है।

लिंक्डलिस्ट क्लास के अंदर, एक स्टैटिक इनर एंट्री क्लास है जिसके साथ नए तत्व बनाए जाते हैं।

 private static class Entry<E> { E element; Entry<E> next; Entry<E> prev; Entry(E element, Entry<E> next, Entry<E> prev) { this.element = element; this.next = next; this.prev = prev; } }

हर बार जब आप एक नया तत्व जोड़ते हैं, तो वास्तव में, दो चरण किए जाते हैं:

1) एंट्री क्लास का एक नया उदाहरण बनाया गया है

 Entry newEntry = new Entry("0", header, header.prev);

2) पिछले और अगले तत्व के संकेत को फिर से परिभाषित किया गया है

 newEntry.prev.next = newEntry; newEntry.next.prev = newEntry; size++;

कोई अन्य आइटम जोड़ें

 list.add("1");

Footprint{Objects=8, References=12, Primitives=[int x 8, char x 2]}
Object size: 176 bytes

 // header.prev      0 Entry newEntry = new Entry("1", header, header.prev);

सूची के मध्य में आइटम जोड़ना

सूची में एक तत्व को एक विशिष्ट स्थिति में जोड़ने के लिए, आपको ऐड (इंडेक्स, वैल्यू) विधि को कॉल करना होगा। ऐड (मान) से अंतर उस तत्व की परिभाषा है जिसके पहले इंसर्ट किया जाएगा

 (index == size ? header : entry(index))

प्रविष्टि (सूचकांक) विधि निर्दिष्ट सूचकांक के साथ तत्व की तलाश में सूची के माध्यम से चलती है। ट्रैवर्सल दिशा स्थिति (सूचकांक <(आकार >> 1)) द्वारा निर्धारित की जाती है। वास्तव में, यह पता चला है कि वांछित तत्व को खोजने के लिए सूची में से आधे से अधिक की खोज नहीं की गई है, लेकिन स्पर्शोन्मुख विश्लेषण के दृष्टिकोण से, खोज समय रैखिक रूप से बढ़ता है - ओ (एन)।

 private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.prev; } return e; }

जैसा कि आप देख सकते हैं, डेवलपर इंडेक्सऑउटऑफबाउंडएक्ससेप्शन को पकड़ सकता है यदि निर्दिष्ट सूचकांक नकारात्मक या वर्तमान आकार से अधिक है। यह उन सभी तरीकों के लिए सही है जहां सूचकांक मापदंडों में प्रकट होता है।

 list.add(1, "100");

Footprint{Objects=11, References=16, Primitives=[int x 11, char x 5]}
Object size: 248 bytes

 // entry      1, entry.prev     0 Entry newEntry = new Entry("100", entry, entry.prev);

आइटम हटाएं

सूची से आइटम निकालने के कई तरीके हैं:
- हटाने () , हटाने का उपयोग करके सूची की शुरुआत या अंत से, O (1) के दौरान हटाने ( );
- O (n) समय के दौरान निकालें (अनुक्रमणिका) अनुक्रमणिका द्वारा और निकालें (मान) मान द्वारा।

मूल्य से हटाने पर विचार करें

 list.remove("100");

Footprint{Objects=8, References=12, Primitives=[int x 8, char x 2]}
Object size: 176 bytes

हटाने (मान) विधि के अंदर, सूची के सभी तत्व सही के लिए स्कैन किए जाते हैं। केवल पहला आइटम हटा दिया जाएगा।

सामान्य तौर पर, सूची से हटाने को सशर्त रूप से 3 चरणों में विभाजित किया जा सकता है:

1) संबंधित तत्व के साथ पहले तत्व की खोज करें

2) पिछले और अगले तत्व के संकेत को फिर से परिभाषित किया गया है

 //     //         E result = e.element; e.prev.next = e.next; e.next.prev = e.prev;

3) अन्य तत्वों की ओर संकेत को हटाना और स्वयं तत्व का विस्मरण

 e.next = e.prev = null; e.element = null; size--;

iterators

तत्वों की अपनी खुद की गणना के लिए, आप "अंतर्निर्मित" पुनरावृत्त का उपयोग कर सकते हैं। मैं गहराई से नहीं जाऊंगा, अंदर होने वाली प्रक्रियाएं ऊपर वर्णित के समान हैं।

 ListIterator<String> itr = list.listIterator();

ऊपर दिया गया कोड सूची के शीर्ष पर सूचक को रखेगा। आप एक विशिष्ट स्थान से तत्वों पर पुनरावृत्ति भी शुरू कर सकते हैं, इसके लिए आपको इंडेक्स को सूची-सूची (इंडेक्स) विधि में पास करना होगा। यदि आपको सूची के अंत से क्रॉलिंग शुरू करने की आवश्यकता है, तो आप descendingIterator () विधि का उपयोग कर सकते हैं।

यह याद रखने योग्य है कि एक ListIterator एक समवर्ती ModificationException के साथ बंद हो जाएगा यदि, एक इटरेटर बनाने के बाद, सूची को अपने स्वयं के इट्रेटर विधियों के माध्यम से संशोधित नहीं किया गया था।

ठीक है, बस मामले में, तत्वों की गणना का एक आदिम उदाहरण:

 while (itr.hasNext()) System.out.println(itr.next());

परिणाम

- लिंक्डलिस्ट से आप एक्सेस टाइम ओ (1) के साथ एक स्टैक, क्यू या डबल कतार को व्यवस्थित कर सकते हैं;
- यह सूची के बीच से डालने और हटाने के लिए, अनुक्रमणिका या मान द्वारा किसी आइटम को प्राप्त करने के लिए रैखिक समय O (n) लेगा। हालाँकि, ListIterator.add () और ListIterator.remove () का उपयोग करके सूची के मध्य से जोड़ना और निकालना O (1) की आवश्यकता होगी;
- आप अशक्त सहित किसी भी मूल्य को जोड़ने के लिए अनुमति देता है। आदिम प्रकार के भंडारण के लिए संबंधित आवरण वर्ग का उपयोग करता है;
- सिंक्रनाइज़ नहीं।

संदर्भ

लिंक्डलिस्ट सूत्र
JDK7 से लिंक्डलिस्ट
JDK के स्रोत OpenJDK और व्यापार 6 स्रोत रिलीज़ - बिल्ड b23

कब्जे वाली मेमोरी की मात्रा को स्मृति-मापक उपकरण का उपयोग करके मापा गया था। इसका उपयोग करने के लिए आपको अमरूद (Google कोर लाइब्रेरी) की भी आवश्यकता होगी।

चित्रों में डेटा संरचनाएं। LinkedList