LinkedList संग्रह सादर करत आहे

1. चा इतिहासLinkedList

Java मध्ये C++ भाषेतून वारशाने मिळालेला जावा आणखी एक संग्रह वर्ग आहे. हा LinkedListवर्ग आहे, जो "लिंक्ड लिस्ट" लागू करतो.

बाहेरून, a LinkedListसारखेच दिसते ArrayList. वर्गात LinkedListवर्गाप्रमाणेच सर्व पद्धती आहेत ArrayList. तत्वतः, आपण नेहमी a LinkedListऐवजी a वापरू शकता ArrayListआणि सर्वकाही कार्य करेल.

मग आम्हाला दुसर्या यादी वर्गाची आवश्यकता का आहे?

उत्तराचा वर्गाच्या अंतर्गत रचनेशी संबंध आहे LinkedList. अॅरे ऐवजी, ते दुप्पट लिंक केलेली सूची वापरते . ते काय आहे ते आम्ही थोड्या वेळाने स्पष्ट करू.

वर्गाची LinkedListभिन्न अंतर्गत रचना सूचीच्या मध्यभागी घटक घालण्यात सर्वात जलद बनवते.

इंटरनेटवर, आपण अनेकदा ArrayListआणि LinkedListवर्गांची तुलना शोधू शकता:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

सर्व काही पुरेसे स्पष्ट दिसते: जर तुम्हाला सूचीमध्ये बरेचदा घटक घालायचे असल्यास, वापरा LinkedList; क्वचितच, तर ArrayList वापरा. पण वास्तव थोडे वेगळे आहे.

2. कोणीही वापरत नाहीLinkedList

कोणीही वापरत नाही LinkedList.

अगदी वर्गाच्या लेखकाने LinkedListनुकतेच ट्विट केले: "कोणी खरोखर वापरतो का LinkedList? मी ते लिहिले आहे, आणि मी ते कधीही वापरत नाही."

मग करार काय आहे?

प्रथम, वर्ग ArrayListखूप लवकर यादीच्या मध्यभागी घटक घालण्यास सक्षम होऊ लागला. सूचीच्या मध्यभागी एक घटक समाविष्ट करताना, तुम्हाला समाविष्ट करण्याच्या बिंदूनंतरचे सर्व घटक सूचीच्या शेवटी 1 ने हलवावे लागतील. यासाठी वेळ लागत असे.

पण आता सर्व काही बदलले आहे. अॅरेचे सर्व घटक मेमरीच्या समान ब्लॉकमध्ये एकमेकांच्या जवळ असतात, त्यामुळे घटकांचे स्थलांतर करण्याचे ऑपरेशन अतिशय जलद निम्न-स्तरीय कमांडद्वारे केले जाते: .System.arraycopy()

याव्यतिरिक्त, आजच्या प्रोसेसरमध्ये एक मोठा कॅशे आहे जो सामान्यतः संपूर्ण अॅरे ठेवू शकतो, ज्यामुळे अॅरे घटकांना मेमरीऐवजी कॅशेमध्ये हलवता येते. एका मिलिसेकंदात दशलक्ष घटक सहजपणे हलवले जातात.

दुसरे, तुम्ही इटरेटर वापरून घटक घातल्यास वर्ग पटकन समाविष्ट करू शकतो . LinkedListजर तुम्ही इटरेटर वापरत असाल LinkedListआणि सतत नवीन घटक समाविष्ट करा (किंवा विद्यमान घटक काढून टाका), ऑपरेशन अतिशय जलद आहे.

LinkedListजर तुम्ही लूपमधील ऑब्जेक्टमध्ये फक्त घटक जोडले , तर प्रत्येक जलद इन्सर्ट ऑपरेशनमध्ये हळू "गेट एलिमेंट" ऑपरेशन असते.

वास्तविकता याच्या खूप जवळ आहे:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

LinkedListएवढ्या संथ ऑपरेशनमधून एक घटक का मिळत आहे ?

रचना कशी आहे याबद्दल थोडेसे परिचित झाल्यानंतर आपण या प्रश्नाचे उत्तर देऊ शकता LinkedList.

3. LinkedListरचना कशी आहे

LinkedListपेक्षा वेगळी अंतर्गत रचना आहे ArrayList. त्यात घटक संचयित करण्यासाठी अंतर्गत अॅरे नाही. त्याऐवजी, ते दुहेरी इंक केलेली सूची नावाची डेटा रचना वापरते .

दुप्पट लिंक केलेल्या सूचीतील प्रत्येक घटक मागील घटक आणि पुढील घटकाचा संदर्भ संग्रहित करतो. हे काहीसे दुकानातील ओळीसारखे आहे, जिथे प्रत्येक व्यक्तीला त्यांच्या समोर उभी असलेली व्यक्ती तसेच त्यांच्या मागे उभी असलेली व्यक्ती आठवते.

मेमरीमध्ये अशी यादी कशी दिसते:

डोके आणि शेपटी (राखाडी पार्श्वभूमी असलेल्या पेशी) firstआणि lastव्हेरिएबल्स आहेत, जे Nodeवस्तूंचे संदर्भ संग्रहित करतात.

मध्यभागी, आपल्याकडे Nodeवस्तूंची साखळी आहे (वस्तू, चल नाही). त्या प्रत्येकामध्ये तीन फील्ड असतात:

• prev— मागील ऑब्जेक्टचा संदर्भNode (लिंक) संग्रहित करते (पिवळ्या पार्श्वभूमीसह सेल).
• value— सूचीतील या घटकाचे मूल्य संग्रहित करते (हिरव्या पार्श्वभूमीसह सेल).
• next— पुढील ऑब्जेक्टचा संदर्भNode (लिंक) संग्रहित करते (निळ्या पार्श्वभूमीसह सेल)

nextदुसरा ऑब्जेक्ट (पत्ता F24) पहिल्या ऑब्जेक्टसाठी पुढील ( ) आणि prevतिसऱ्या ऑब्जेक्टसाठी मागील ( ) आहे. तिसऱ्या ऑब्जेक्टच्या पिवळ्या फील्डमध्ये F24 पत्ता आहे आणि पहिल्या ऑब्जेक्टच्या निळ्या फील्डमध्ये F24 पत्ता आहे.

पहिल्या आणि तिसर्‍या ऑब्जेक्टमधील बाण त्याच दुसऱ्या ऑब्जेक्टकडे निर्देश करतात. त्यामुळे अशा प्रकारे बाण काढणे अधिक योग्य ठरेल.

4. लिंक केलेल्या सूचीमध्ये एक घटक घाला

अशा लाईनमध्ये एखाद्याला जोडण्यासाठी, तुम्हाला फक्त एकमेकांच्या शेजारी उभ्या असलेल्या दोन लोकांची परवानगी घेणे आवश्यक आहे. पहिली व्यक्ती नवागताला "माझ्यामागची व्यक्ती" म्हणून लक्षात ठेवते आणि दुसरी व्यक्ती "माझ्यासमोरची व्यक्ती" म्हणून लक्षात ठेवते.

आपल्याला फक्त दोन शेजारच्या वस्तूंचे संदर्भ बदलण्याची आवश्यकता आहे:

दुसऱ्या आणि तिसऱ्या वस्तूंचे संदर्भ बदलून आम्ही आमच्या सूचीमध्ये एक नवीन आयटम जोडला. नवीन ऑब्जेक्ट जुन्या दुसऱ्या ऑब्जेक्टसाठी पुढील आणि जुन्या तिसऱ्या ऑब्जेक्टसाठी मागील आहे. आणि, अर्थातच, नवीन ऑब्जेक्टला स्वतःच योग्य संदर्भ संग्रहित करणे आवश्यक आहे: त्याचा मागील ऑब्जेक्ट जुना दुसरा ऑब्जेक्ट आहे आणि त्याचा पुढील ऑब्जेक्ट जुना तिसरा ऑब्जेक्ट आहे.

एखादे घटक काढून टाकणे आणखी सोपे आहे: जर आपल्याला सूचीमधून 100 वा ऑब्जेक्ट काढायचा असेल, तर आपल्याला फक्त 99व्या ऑब्जेक्टसाठी फील्ड बदलणे आवश्यक आहे जेणेकरून ते 101व्या ऑब्जेक्टकडे निर्देश करेल nextआणि prev101व्या ऑब्जेक्टसाठी फील्ड बदला. ऑब्जेक्ट करा जेणेकरून ते 99 व्या कडे निर्देशित करेल. बस एवढेच.

पण 100 वा ऑब्जेक्ट मिळवणे इतके सोपे नाही.

5. सूचीमधून घटक काढा

लिंक केलेल्या सूचीचा 100 वा घटक मिळविण्यासाठी, तुम्हाला हे करणे आवश्यक आहे:

पहिला ऑब्जेक्ट मिळवा: तुम्ही हे firstऑब्जेक्टमधील व्हेरिएबल वापरून करा LinkedList. 1ल्या ऑब्जेक्टचे फील्ड next2र्‍या ऑब्जेक्टचा संदर्भ संग्रहित करते. अशा प्रकारे आपल्याला दुसरी वस्तू मिळते. दुस-या ऑब्जेक्टला तिसर्‍याचा संदर्भ आहे, वगैरे.

जर आपल्याला 100व्या ऑब्जेक्टचा संदर्भ घ्यायचा असेल, तर आपल्याला 1 ली ते 100 व्या ऑब्जेक्टमधून क्रमशः पुढे जावे लागेल. आणि जर आपल्याला सूचीतील दशलक्षव्या घटकाची आवश्यकता असेल, तर आपल्याला एकामागून एक दशलक्ष ऑब्जेक्ट्सची पुनरावृत्ती करावी लागेल!

आणि जर या वस्तू वेगवेगळ्या वेळी सूचीमध्ये जोडल्या गेल्या असतील तर ते मेमरीच्या वेगवेगळ्या भागांमध्ये स्थित असतील आणि त्याच वेळी प्रोसेसरच्या कॅशेमध्ये संपण्याची शक्यता नाही. याचा अर्थ असा आहे की लिंक केलेल्या सूचीच्या घटकांवर पुनरावृत्ती करणे केवळ मंद नाही तर खूप हळू आहे.

तेच आम्ही हाताळत आहोत.

मग आम्ही तुम्हाला हे धीमे कसे LinkedListकार्य करते हे का शिकवत आहोत?

बरं, नोकरीच्या मुलाखती दरम्यान तुम्हाला विचारले जाईल की ते कसे LinkedListवेगळे आहेArrayList . नक्कीच.