இணைக்கப்பட்ட பட்டியல் தொகுப்பை அறிமுகப்படுத்துகிறோம்

1. வரலாறுLinkedList

ஜாவாவில் C++ மொழியிலிருந்து பெறப்பட்ட மற்றொரு சேகரிப்பு வகுப்பு ஜாவா உள்ளது. இது LinkedList"இணைக்கப்பட்ட பட்டியலை" செயல்படுத்தும் வகுப்பு.

வெளிப்புறமாக, a என்பது LinkedListஒரு போலவே தோன்றுகிறது ArrayList. வகுப்பில் LinkedListஉள்ள அனைத்து முறைகளும் வகுப்பில் உள்ளன ArrayList. கொள்கையளவில், நீங்கள் எப்போதும் LinkedListஒரு பதிலாக ஒரு பயன்படுத்த முடியும் 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 வது பொருளுக்கான புலத்தை மாற்ற வேண்டும், nextஅது 101 வது பொருளை சுட்டிக்காட்டுகிறது, மேலும் prev101 வது புலத்தை மாற்றவும். ஆப்ஜெக்ட் அதனால் அது 99 ஐ சுட்டிக்காட்டுகிறது. அவ்வளவுதான்.

ஆனால் 100-வது பொருளைப் பெறுவது அவ்வளவு எளிதானது அல்ல.

5. பட்டியலிலிருந்து ஒரு உறுப்பை அகற்றவும்

இணைக்கப்பட்ட பட்டியலின் 100வது உறுப்பைப் பெற, நீங்கள் செய்ய வேண்டியது:

first1வது பொருளைப் பெறுங்கள்: பொருளில் உள்ள மாறியைப் பயன்படுத்தி இதைச் செய்கிறீர்கள் LinkedList. 1 வது பொருளின் புலம் next2 வது பொருளின் குறிப்பை சேமிக்கிறது. அப்படித்தான் இரண்டாவது பொருளைப் பெறுகிறோம். 2 வது பொருளில் மூன்றாவது குறிப்பு உள்ளது, மற்றும் பல.

100 வது பொருளைப் பற்றிய குறிப்பைப் பெற வேண்டுமானால், 1 முதல் 100 வது வரை அனைத்து பொருட்களையும் தொடர்ச்சியாக நகர்த்த வேண்டும். ஒரு பட்டியலில் மில்லியன் உறுப்புகள் நமக்குத் தேவைப்பட்டால், ஒரு மில்லியனுக்கும் அதிகமான பொருட்களை ஒன்றன் பின் ஒன்றாக மாற்ற வேண்டும்!

இந்த பொருள்கள் வெவ்வேறு நேரங்களில் பட்டியலில் சேர்க்கப்பட்டால், அவை நினைவகத்தின் வெவ்வேறு பகுதிகளில் அமைந்துள்ளன, மேலும் அவை ஒரே நேரத்தில் செயலியின் தற்காலிக சேமிப்பில் முடிவடையும் வாய்ப்பில்லை. இதன் பொருள், இணைக்கப்பட்ட பட்டியலின் கூறுகளை மீண்டும் மீண்டும் செய்வது மெதுவாக அல்ல, ஆனால் மிக மெதுவாக இருக்கும்.

அதைத்தான் நாங்கள் கையாள்கிறோம்.

இந்த மெதுவாக எவ்வாறு செயல்படுகிறது என்பதை நாங்கள் ஏன் உங்களுக்குக் கற்பிக்கிறோம் LinkedList?

சரி, வேலை நேர்காணலின் போது நீங்கள் எப்படி LinkedListவேறுபடுகிறது என்றுArrayList கேட்கப்படும் . கண்டிப்பாக.