[Powered by Google Translate] ప్రోగ్రామింగ్, మనం, విలువల యొక్క జాబితాలలో ప్రాతినిధ్యం అవసరం ఒక విభాగంలో విద్యార్ధులు పేర్లు తాజా క్విజ్ లేదా వారి స్కోర్లు. 

సి భాషలో, శ్రేణుల ఉపయోగించవచ్చు డిక్లేర్డ్ జాబితాలు నిల్వ. ఇది ఒక జాబితా అంశాలు మార్చడానికి సులభం వ్యూహం నిల్వ మరియు మీరు ఆక్సెస్ అవసరం ఉంటే లేదా ith జాబితా మూలకం సవరించండి స్వేచ్ఛా ఇండెక్స్ కోసం నేను, ఆ, స్థిరమైన సమయంలో చేయవచ్చు కానీ శ్రేణుల కూడా లోపాలు ఉన్నాయి. 

మేము వాటిని డిక్లేర్ చేసినప్పుడు, మేము చెప్పడం అవసరం చేస్తున్నారు వారు ఎంత పెద్ద ముందు అప్, వారు నిల్వ ఎలా అనేక అంశాలను ఉంది మరియు ఎంత పెద్ద ఈ అంశాలు వారి రకం ద్వారా నిర్ణయించబడుతుంది. ఉదాహరణకు, Int చేరే సమయం (10) 10 అంశాలను నిల్వ చేయవచ్చు ఒక Int యొక్క పరిమాణం ఉంటాయి. 

మేము ప్రకటన తర్వాత వ్యూహం యొక్క పరిమాణం మార్చలేరు. మేము మరిన్ని అంశములు నిల్వ అనుకుంటే మేము ఒక కొత్త శ్రేణి చేసుకోవాలి. ఈ పరిమితి ఉంది కారణం మా కార్యక్రమం మొత్తం యెరే నిల్వ మెమరీ అవిచ్ఛిన్నంగా భాగం వంటి. ఈ మేము మా పరిధిలో నిల్వ పేరు బఫర్ సే. ఇతర అంశాలపై కావచ్చు శ్రేణి కుడి పక్కన ఉన్న మెమరీ, కాబట్టి మేము కాదు కేవలం శ్రేణి పెద్ద చేస్తాయి. 

కొన్నిసార్లు మేము శ్రేణి యొక్క ఫాస్ట్ డేటా వినియోగ వేగం వ్యాపారం చేయాలనుకుంటున్న ఒక చిన్న మరింత మృదుత్వాన్ని. లింక్ జాబితా, మరొక ప్రాథమిక డేటా నిర్మాణం ఎంటర్ మీరు వంటి తెలిసిన కాదు. అధిక స్థాయిలో, ఒక లింక్ జాబితా నోడ్స్ యొక్క క్రమంలో డేటా నిల్వ ఆ, లింకులు ప్రతి ఇతర కనెక్ట్ అందుకే పేరు 'లింక్ జాబితా.' డిజైన్ లో మేము చూస్తారు, ఈ వ్యత్యాసం వివిధ ప్రయోజనాలు మరియు అప్రయోజనాలు దారితీస్తుంది వ్యూహం కంటే. 

ఇక్కడ పూర్ణాంకాల యొక్క అతి సాధారణ లింక్ జాబితా కోసం కొన్ని సి కోడ్ ఉంది. మీరు మేము ప్రతి నోడ్ ప్రాతినిధ్యం చేసిన చూడగలరు 2 విషయాలు కలిగి ఉన్న ఒక struct వంటి జాబితాలో, 'వాల్' అని నిల్వ పూర్ణాంకం జాబితా తదుపరి నోడ్ మరియు లింక్ మేము అనే పాయింటర్ వంటి ఇది 'తర్వాత.' ఈ విధంగా, మేము మొత్తం జాబితా ట్రాక్ చెయ్యవచ్చు 1st నోడ్ కేవలం ఒకే పాయింటర్ తో, తరువాత రాబోయే గమనికలు అనుసరించండి 2 వ నోడ్కు, 3 వ నోడ్కు, 4 వ నోడ్కు, అందువలన, మేము జాబితా చివర వచ్చేవరకు. 

మీరు ఈ ఉంది 1 లాభం లేదు చేయగలరు స్టాటిక్ అర్రే నిర్మాణాన్ని పైగా - ఒక లింక్ జాబితాను, మేము పూర్తిగా మెమరీ పెద్ద భాగం లేదు. జాబితా యొక్క 1 వ నోడ్, మెమరీ లో ఈ ప్రదేశంలో చేరుకోలేకపోయారు మరియు 2 వ నోడ్ ఇక్కడ అన్ని మార్గం ఉంటుంది. మెమరీలో వారు ఎక్కడ మేము నోడ్స్ సంబంధం లేదు పొందవచ్చు ఎందుకంటే ప్రతి నోడ్ యొక్క తదుపరి పాయింటర్, 1st నోడ్ వద్ద మొదలు ఖచ్చితంగా తదుపరి వెళ్ళడానికి మాకు చెబుతుంది. 

అదనంగా, మేము ముందు అప్ చెప్పడానికి లేదు ఎంత పెద్ద అనుబంధ జాబితా, మేము స్టాటిక్ శ్రేణితో చేయండి మార్గం మేము ఒక జాబితాకు నోడ్స్ జోడించవచ్చు నుండి కాలం స్పేస్ కొత్త నోడ్స్ కోసం మెమరీ ఎక్కడో అక్కడ వంటి. అందువలన, అనుసంధాన జాబితాలు డైనమిక్ పరిమాణాన్ని సులభం. తరువాత కార్యక్రమంలో మేము మరింత నోడ్స్ జోడించడానికి, సే మా జాబితాలో. ఎగిరి మా జాబితా ఒక కొత్త నోడ్ ప్రవేశపెట్టుటకు, మేము అన్ని, ఆ నోడ్సుకోసం మెమరీని కేటాయించాల్సిన ఉంది డేటా విలువ plop, మేము తగిన గమనికలు సర్దుబాటు ద్వారా ఎక్కడ మరియు అప్పుడు అది ఉంచండి. 

ఉదాహరణకు, మధ్య లో ఒక నోడ్ ఉంచండి కోరుకుంటే జాబితా యొక్క 2 మరియు 3 నోడ్స్,  మేము అన్ని వద్ద 2 వ లేదా 3 వ నోడ్స్ తరలించడానికి కాదు. మేము ఈ Red నోడ్ ఇన్సర్ట్ చేస్తున్నారు అనుకోండి. మేము లేదు కావలసిన అన్ని కొత్త నోడ్ యొక్క తదుపరి పాయింటర్ సెట్ 3 వ నోడ్ సూచించడానికి తర్వాత 2 వ నోడ్ యొక్క తదుపరి పాయింటర్ rewire మా కొత్త నోడ్ మార్చాలి. కాబట్టి, మేము ఎగిరి మా జాబితాలు పరిమాణాన్ని మార్చవచ్చు మా కంప్యూటర్ ఇండెక్సింగ్ ఆధారపడతారు కాబట్టి, కానీ వాటిని నిల్వ గమనికలు ఉపయోగించి లింక్ మీద. 

అయితే, ఒక ప్రతికూలత లింక్ జాబితాలు అని, ఒక స్థిర శ్రేణి కాకుండా, కంప్యూటర్ కేవలం జాబితా మధ్య జంప్ కాదు. కంప్యూటర్ లింక్ జాబితాలో ప్రతి నోడ్ సందర్శించడానికి కలిగి ఉన్నందుకు తదుపరి చెయ్యడానికి, ఒక నిర్దిష్ట నోడ్ కనుగొనేందుకు సమయం పడుతుంది వెళుతున్న ఇది వ్యూహంలో దానికన్నా. మొత్తం జాబితా అనుపాత సమయం పడుతుంది ప్రయాణించేందుకు జాబితా యొక్క పొడవు, లేదా O (n) asymptotic విధానంలో. సగటున, ఏ నోడ్ చేరుకుంది కూడా సమయం n నిష్పత్తిలో పడుతుంది. 

ఇప్పుడు, యొక్క నిజానికి కొన్ని కోడ్ వ్రాయుటకు అనుమతి ఆ లింక్ జాబితాలు పనిచేస్తుంది. లెట్ యొక్క మేము పూర్ణాంకాల యొక్క లింక్ జాబితా అనుకుందాం. మేము మళ్ళీ మా జాబితాలో ఒక నోడ్ సూచిస్తుంది 2 ఖాళీలను ఒక struct వంటి, 'వాల్' అని ఒక పూర్ణ సంఖ్య విలువ మరియు జాబితా యొక్క తదుపరి నోడ్ ఒక తదుపరి పాయింటర్. Well, తగినంత సాధారణ తెలుస్తోంది. 

లెట్ యొక్క మేము ఒక ఫంక్షన్ రాయడానికి అనుకుందాం ఇది ప్రవహిస్తుంది అవుట్ జాబితా మరియు ప్రింట్లు విలువ జాబితా యొక్క చివరి నోడ్ నిల్వ. అయితే, అది మేము జాబితాలో నోడ్లు దాటటానికి అవసరం అర్థం చివరి కనుగొనేందుకు, కాని మేము జోడించడం లేదు నుండి లేదా ఏదైనా తొలగించడం, మనము అనుకుంటున్న జాబితా తదుపరి గమనికలు యొక్క అంతర్గత నిర్మాణం. 

కాబట్టి, మేము ట్రావెర్సల్ కోసం ప్రత్యేకంగా ఒక పాయింటర్ చేయాలి ఇది మేము 'క్రాలర్.' పిలుస్తాను ఇది జాబితా యొక్క అన్ని మూలకాలను ద్వారా క్రాల్ చేస్తుంది తదుపరి గమనికలు యొక్క గొలుసు అనుసరించడం ద్వారా. మేము నిల్వ అన్ని, 1st నోడ్ ఒక పాయింటర్ గా జాబితా లేదా 'తల'. 1st నోడ్ వెళ్ళండి పాయింట్లు. టైపు పాయింటర్ నుండి నోడ్ యొక్క ఉంటుంది. 

జాబితాలో నిజమైన 1 నోడ్ పొందడానికి, మేము, dereference ఈ పాయింటర్ కలిగి మేము అది dereference ముందు కానీ, మేము తనిఖీ చేయాలి పాయింటర్ మొదటి శూన్య ఉంటే. అది శూన్య అయితే, జాబితా, ఖాళీగా ఉంది మరియు మేము, జాబితా ఖాళీగా ఉంది ఎందుకంటే ఆ, ఒక సందేశాన్ని ముద్రించండి ఉండాలి గత నోడ్ ఉండదు. కానీ, లెట్స్ జాబితా ఖాళీగా కాదు సే. అలా కాకపోతే, అప్పుడు మేము మొత్తం జాబితా ద్వారా క్రాల్ చెయ్యాలో మేము జాబితాలో చివరి నోడ్ ను వరకు, మరియు మేము జాబితాలో చివరి నోడ్ వద్ద చూస్తున్న ఎలా మేము చెబుతారా? 

Well, ఒక కణుపు యొక్క తదుపరి పాయింటర్ శూన్య ఉంటే, మేము చివరికి మాకు తెలుసు గత తదుపరి పాయింటర్ సూచించడానికి జాబితాలో తదుపరి నోడ్ కలిగి కనుక. ఇది ఎల్లప్పుడూ శూన్యం కు initialized గత నోడ్ యొక్క తదుపరి పాయింటర్ ఉంచడానికి మంచి పద్ధతి యొక్క మేము జాబితా ముగింపు చేరుకున్నారు ఉన్నప్పుడు మాకు హెచ్చరిస్తుంది ఇది ఒక ప్రామాణిక ఆస్తి కలిగి. 

కాబట్టి, క్రాలర్ → తరువాతి శూన్య ఉంటే, బాణం సింటాక్స్ dereferencing ఒక షార్ట్కట్ అని గుర్తుంచుకోండి ఒక struct ఒక పాయింటర్, అప్పుడు యాక్సెస్ ఇబ్బందికరమైన సమానం తన తరువాత ఫీల్డ్: (* క్రాలర్). తదుపరి. ఒకసారి మేము గత నోడ్ అనిపిస్తే మేము, క్రాలర్ → Val ప్రింట్ మీరు ప్రస్తుత నోడ్ విలువ ఇది మనము గత ఒకటి. లేకపోతే, మేము జాబితాలో చివరి నోడ్ వద్ద ఇంకా తెలియకపోతే, మేము జాబితాలో తదుపరి నోడ్ వెళ్ళటానికి కలిగి ఆ చివరి అయితే మరియు తనిఖీ. ఇది చేయుటకు, మేము మా క్రాలర్ పాయింటర్ సెట్ ప్రస్తుత నోడ్ యొక్క తదుపరి విలువ సూచించడానికి, ఆ, జాబితా తదుపరి నోడ్ ఉంది. ఈ సెట్టింగ్ చేస్తారు క్రాలర్ = క్రాలర్ → తరువాతి. అప్పుడు మేము, ఉదాహరణకు ఒక లూప్ ఈ విధానాన్ని పునరుక్తి మేము గత నోడ్ క్లిక్ చెయ్యండి. కావున, ఉదాహరణకు, క్రాలర్ తల సూచించే ఒకవేళ, మేము, క్రాలర్ → తరువాతి సూచించడానికి క్రాలర్ సెట్ ఇది 1 వ నోడ్ యొక్క తదుపరి రంగంలో కూడా లేదు. కాబట్టి, ఇప్పుడు మా క్రాలర్, 2 వ నోడ్ కు సూచిస్తుంది మరియు, మళ్ళీ, మేము, ఒక లూప్ ఈ పునరావృతం మేము గత నోడ్ అనిపిస్తే వరకు, అనగా, పేరు నోడ్ యొక్క తదుపరి పాయింటర్ శూన్యం కు సూచిస్తుంది. మరియు అక్కడ మేము, అది కలిగి మేము జాబితాలో చివరి నోడ్ అనిపిస్తే, మరియు దాని విలువ ముద్రించడానికి, మేము కేవలం క్రాలర్ → Val ఉపయోగించండి. 

నదీ ప్రవాహానికి అడ్డంగా ప్రయాణం అంత చెడ్డ కాదు, కానీ ఇన్సర్ట్ గురించి? అనుమతిస్తుంది మేము 4 వ స్థానం లో పూర్ణాంకం ఇన్సర్ట్ అనుకుందాం పూర్ణాంకం జాబితాలో. ప్రస్తుతం 3 వ మరియు 4 వ నోడ్సుమధ్య ఉంది. మళ్లీ, మేము జస్ట్ జాబితా ప్రయాణించేందుకు కలిగి 3 వ మూలకం, మేము తర్వాత ఇన్సర్ట్ చేసిన ఒక పొందండి. అందుకే, ఈ, జాబితా నుండి అడ్డంగా మళ్ళీ క్రాలర్ పాయింటర్ సృష్టించడానికి మా తల పాయింటర్ శూన్య ఉంటే, తనిఖీ అలా కాకపోతే మరియు, తల నోడ్ వద్ద మా క్రాలర్ పాయింటర్ అభిప్రాయపడుతున్నారు. కాబట్టి, మేము 1st మూలకం వద్ద ఉన్నారు. మేము, మేము ఇన్సర్ట్ ముందు 2 మరిన్ని అంశములు ముందుకు వెళ్ళాలి కాబట్టి మేము లూప్ ఒక ఉపయోగించవచ్చు Int i = 1; i <3; i + + మరియు లూప్ యొక్క ప్రతి పునరావృతం లో, 1 నోడ్ ముందుకు మా క్రాలర్ పాయింటర్ ముందుకు ప్రస్తుత నోడ్ యొక్క తదుపరి రంగంలో శూన్య ఉంటే తనిఖీ చెయ్యడం ద్వారా, అలా కాకపోతే మరియు, తరువాత నోడ్ మా క్రాలర్ పాయింటర్ తరలించు ప్రస్తుత నోడ్ యొక్క తదుపరి పాయింటర్ దానిని సమానంగా చేయడం ద్వారా. కాబట్టి, మా కోసం లూప్ అలా ఇలా చెబుతాడు నుండి రెండుసార్లు, మేము, 3 వ నోడ్ చేరుకున్నారు మరియు ఒకసారి మా క్రాలర్ పాయింటర్ తర్వాత నోడ్ చేరుకుంది ఇది మేము, మా కొత్త పూర్ణాంక ఇన్సర్ట్ చెయ్యడానికి మీరు ఎలా మేము నిజంగా ఇన్సర్ట్ చేయాలి? 

Well, మా కొత్త పూర్ణాంక జాబితాలో చేర్చబడ్డ ఉంటుంది తన సొంత నోడ్ struct భాగంగా, ఇది నిజంగా నోడ్స్ యొక్క వరుస క్రమం నుండి. కాబట్టి, నోడ్ ఒక కొత్త పాయింటర్ తయారు చేద్దాము 'new_node,' అని మరియు ఇది సెట్ మేము ఇప్పుడు కేటాయించాలని ఆ స్మృతి సూచించడానికి నోడ్ మాత్రమే కుప్ప న, మరియు మేము కేటాయించే ఎంత మెమరీ చేయాలి? Well, ఒక కణుపు యొక్క పరిమాణం, మరియు మేము ఇన్సర్ట్ చెయ్యడానికి కావలసిన పూర్ణాంక తన Val రంగంలో సెట్ చేయాలనుకుంటున్నారా. లెట్ యొక్క 6 చెబుతారు. ఇప్పుడు, నోడ్ మా పూర్ణాంక విలువ కలిగి ఉంది. ఇది కొత్త నోడ్ యొక్క తదుపరి రంగంలో ప్రారంభించడం కూడా మంచి పద్ధతి యొక్క శూన్యం సూచించడానికి, కానీ ఇప్పుడు ఏంటి? 

మేము జాబితాలో అంతర్గత నిర్మాణం మార్చవలసి మరియు తర్వాత గమనికలు జాబితా యొక్క ప్రస్తుత ఉన్న 3 వ మరియు 4 వ నోడ్స్. తదుపరి గమనికలు జాబితా క్రమాన్ని గుర్తించేందుకు, నుండి మరియు మేము మా కొత్త నోడ్ ఇన్సర్ట్ ఉన్నందున కుడివైపు జాబితా యొక్క మధ్యలో, అది ఒక బిట్ గమ్మత్తైన ఉంటుంది. గుర్తు, ఎందుకంటే ఇది మా కంప్యూటర్ ఉంది మాత్రమే జాబితాలో ల నగర తెలుసు మునుపటి నోడ్స్ నిల్వ తదుపరి గమనికలు కారణంగా. కాబట్టి, మనం, ఈ ప్రాంతాల్లో ఏ ట్రాక్ కోల్పోతే మా జాబితా తదుపరి గమనికలు ఒకటి మార్చడం ద్వారా చెప్పడానికి, ఉదాహరణకు, మేము మార్చబడింది సే 3 వ నోడ్ యొక్క తదుపరి రంగంలో ఇక్కడ కొంత నోడ్ మార్చాలి. మేము ఎందుకంటే మేము, అవ్ట్ అదృష్టం అంటాను , పేరు జాబితా మిగిలిన కనుగొనేందుకు ఏ ఆలోచన ఉంది మరియు స్పష్టమైన నిజంగా దురదృష్టకరం. అందుకే, ఈ క్రమంలో గురించి నిజంగా జాగ్రత్తగా ఉండాలి మేము చొప్పించడం సమయంలో మా తదుపరి గమనికలు సర్దుబాటు దీనిలో. 

కాబట్టి, ఈ సరళీకృతం చేయడానికి, యొక్క అని పిలవబడు ఆ మా మొదటి 4 నోడ్స్ గమనికలు యొక్క గొలుసు ప్రాతినిధ్యం బాణాలు తో, A, B, C, D మరియు పిలుస్తారు నోడ్స్ కనెక్ట్. కాబట్టి, మేము మా కొత్త నోడ్ ఇన్సర్ట్ చేయాలి నోడ్స్ సి మరియు డి మధ్య ఇది కుడి క్రమంలో దీన్ని క్లిష్టమైన, మరియు నేను తెలియజేస్తాము. 

మొదటి దీన్ని తప్పుగా చూద్దాం. హేయ్, మేము కొత్త నోడ్ సి తరువాత వచ్చిన పొందింది, కాబట్టి యొక్క C యొక్క తదుపరి పాయింటర్ సెట్ తెలియజేయండి new_node మార్చాలి. All right, సరే ఉంది, మేము ఇప్పుడు ముగించడానికి కలిగి D కొత్త నోడ్ యొక్క తదుపరి పాయింటర్ విషయాన్ని, కానీ వేచి, ఎలా మేము చేయగలరు? D ఉన్న మాకు అని మాత్రమే కాదు, తదుపరి పాయింటర్ గతంలో, సి నిల్వ చేశారు కానీ మేము ఆ పాయింటర్ తిరిగి వ్రాసారు కొత్త నోడ్ సూచించడానికి, కాబట్టి మేము ఇకపై, D మెమరీలో ఉన్న ఏ క్లూ కలిగి మరియు మేము జాబితా మిగిలిన కోల్పోయి. అన్ని మంచి. 

కాబట్టి, మేము ఈ కుడి ఎలా చేయాలి? మొదటి, D. కొత్త నోడ్ యొక్క తదుపరి పాయింటర్ సూచించండి ఇప్పుడు, రెండు కొత్త నోడ్ యొక్క మరియు C యొక్క తదుపరి గమనికలు అదే నోడ్, D సూచించే ఉంటాయి, కానీ ఆ మంచిది. ఇప్పుడు మేము కొత్త నోడ్ వద్ద సి తరువాత పాయింటర్ సూచిస్తుంది. కాబట్టి, మేము ఏ డేటా కోల్పోకుండా ఇది చేసిన. కోడ్ లో, C ప్రస్తుత కణుపు ట్రావెర్సల్ పాయింటర్ క్రాలర్, కు సూచిస్తుంది ఆ మరియు D, ప్రస్తుత నోడ్ యొక్క తదుపరి రంగంలో ద్వారా చూపారు నోడ్ ప్రాతినిధ్యం వహిస్తుంది లేదా క్రాలర్ → తరువాతి. కాబట్టి, మేము మొదటి కొత్త నోడ్ యొక్క తదుపరి పాయింటర్ సెట్ క్రాలర్ → తరువాతి సూచించడానికి, మేము new_node తరువాత పాయింటర్ భావించారు అదే విధంగా ఉదాహరణ D సూచించారు. అప్పుడు, మేము ప్రస్తుత నోడ్ యొక్క తదుపరి పాయింటర్ సెట్ చేయవచ్చు మా కొత్త నోడ్ కు, మేము డ్రాయింగ్ లో new_node కు సి మార్చాలి వేచి చేసినట్టుగానే. ఇప్పుడు ప్రతిదీ క్రమంలో ఉంది, మరియు మేము ఓడిపోలేదు ఏదైనా డేటా ట్రాక్, మరియు మేము కేవలం సాధించారు జాబితా మధ్యలో మా కొత్త నోడ్ కర్ర ఈ మొత్తం విషయం పునర్నిర్మాణ లేదా ఏదైనా మూలకాల బదిలీ లేకుండా మార్గం మేము ఒక స్థిర పొడవు శ్రేణి తో పేర్కొంది. 

కాబట్టి, అనుసంధాన జాబితాలు ఒక ప్రాథమిక, కానీ ముఖ్యమైన, డైనమిక్ డేటా నిర్మాణం ఉన్నాయి ఇది ప్రయోజనాలు మరియు అప్రయోజనాలు ఉన్నాయి శ్రేణుల మరియు ఇతర డేటా నిర్మాణాలు పోలిస్తే, మరియు, తరచుగా కంప్యూటర్ సైన్స్ లో కేసు ఇది ప్రతి సాధనం ఉపయోగించడానికి తెలుసుకోవడానికి ముఖ్యం కాబట్టి మీరు సరైన ఉద్యోగం కోసం కుడి సాధనం ఎంచుకోవచ్చు. 

మరింత సాధన కోసం, విధులు రాయడం ప్రయత్నించండి ఒక లింక్ జాబితా నుండి తొలగించండి నోడ్స్ - మీరు క్రమాన్ని ఏ క్రమంలో గురించి జాగ్రత్తగా గుర్తుంచుకోండి మీ జాబితా యొక్క ఒక భాగం కోల్పోతే లేదు నిర్ధారించడానికి మీ తదుపరి గమనికలు - లేదా అనుబంధ జాబితా లో నోడ్ లెక్కించడానికి ఒక ఫంక్షన్ ఒక లింక్ జాబితాలో నోడ్స్ యొక్క అన్ని క్రమాన్ని రివర్స్ లేదా ఒక ఆహ్లాదకరమైన ఒక. 

నా పేరు జాక్సన్ STEINKAMP, ఈ CS50 ఉంది.