లింక్డ్‌లిస్ట్ సేకరణను పరిచయం చేస్తున్నాము

1. చరిత్రLinkedList

జావాకు C++ భాష నుండి సంక్రమించబడిన మరొక సేకరణ తరగతి జావా ఉంది. ఇది LinkedList"లింక్డ్ లిస్ట్"ని అమలు చేసే తరగతి.

బాహ్యంగా, a LinkedListఒక మాదిరిగానే కనిపిస్తుంది ArrayList. తరగతికి LinkedListతరగతికి సంబంధించిన అన్ని పద్ధతులు ఉన్నాయి ArrayList. సూత్రప్రాయంగా, మీరు ఎల్లప్పుడూ ఒక 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వ ఆబ్జెక్ట్‌కి ఫీల్డ్‌ని మార్చాలి, తద్వారా nextఅది 101వ ఆబ్జెక్ట్‌ని చూపుతుంది మరియు prev101వ ఫీల్డ్‌ని మార్చాలి. వస్తువు 99కి చూపుతుంది. అంతే.

కానీ 100వ వస్తువు పొందడం అంత సులభం కాదు.

5. జాబితా నుండి ఒక మూలకాన్ని తీసివేయండి

లింక్ చేయబడిన జాబితా యొక్క 100వ మూలకాన్ని పొందడానికి, మీరు వీటిని చేయాలి:

1వ ఆబ్జెక్ట్‌ని పొందండి: మీరు ఆబ్జెక్ట్‌లోని firstవేరియబుల్‌ని ఉపయోగించి దీన్ని చేయండి LinkedList. 1వ వస్తువు యొక్క ఫీల్డ్ next2వ వస్తువుకు సూచనను నిల్వ చేస్తుంది. ఆ విధంగా మనం రెండవ వస్తువును పొందుతాము. 2వ ఆబ్జెక్ట్‌లో మూడవ దానికి రిఫరెన్స్ ఉంది.

మనం 100వ ఆబ్జెక్ట్‌కు సూచనను పొందాలంటే, 1వ నుండి 100వ వరకు అన్ని వస్తువులను మనం వరుసగా తరలించాలి. మరియు మనకు జాబితాలో మిలియన్‌వ మూలకం అవసరమైతే, మనం ఒకదాని తర్వాత ఒకటిగా ఒక మిలియన్ వస్తువులను పునరావృతం చేయాలి!

మరియు ఈ వస్తువులు వేర్వేరు సమయాల్లో జాబితాకు జోడించబడితే, అవి మెమరీలోని వివిధ భాగాలలో ఉంటాయి మరియు అదే సమయంలో ప్రాసెసర్ కాష్‌లో ముగిసే అవకాశం లేదు. దీనర్థం లింక్ చేయబడిన జాబితా యొక్క మూలకాలపై పునరావృతం చేయడం కేవలం నెమ్మదిగా కాదు, చాలా నెమ్మదిగా ఉంటుంది.

మేము దానితో వ్యవహరిస్తున్నాము.

ఈ స్లో ఎలా పని చేస్తుందో మేము మీకు ఎందుకు బోధిస్తున్నాము LinkedList?

సరే, ఉద్యోగ ఇంటర్వ్యూల సమయంలో మీరు నుండి ఎలాLinkedListArrayList భిన్నంగా ఉంటుంది అని అడగబడతారు . ఖచ్చితంగా.