[Powered by Google Translate] I programmering, vi ofte behov for å representere lister over verdier, slik som navn på elevene i en del eller deres score på den siste quiz. 

I C-språk, erklærte arrayer kan brukes for å lagre lister. Det er lett å oppsummere elementene i en liste lagret i en matrise, og hvis du trenger tilgang til eller endre ed listeelement for noen vilkårlig indeks I, som kan gjøres i konstant tid, men arrays har ulemper også. 

Når vi erklære dem, er vi forpliktet til å si opp foran hvor store de er, det vil si hvor mange elementer de kan lagre og hvor store disse elementene er, som bestemmes av type. For eksempel, int arr (10) kan lagre 10 varer som er på størrelse med en int. 

Vi kan ikke endre en rekke størrelse etter erklæringen. Vi må lage en ny rekke hvis vi ønsker å lagre flere elementer. Grunnen denne begrensningen eksisterer er at vår Programmet lagrer hel rekke som en sammenhengende del av minnet. Si dette er den buffer der vi lagret i array vår. Det kan være andre variabler ligger rett ved siden av tabellen i minnet, slik at vi ikke kan bare gjøre array større. 

Noen ganger vi ønsker å handle array rask datatilgang hastighet for litt mer fleksibilitet. Skriv inn lenket liste, en annen grunnleggende datastruktur du kanskje ikke være så kjent med. På et høyt nivå, en lenket liste lagrer data i en sekvens av noder som er koblet til hverandre med koblinger, derav navnet "lenket liste. Som vi vil se, denne forskjellen i design fører til forskjellige fordeler og ulemper enn en matrise. 

Her er noen C-kode for en veldig enkel lenket liste av heltall. Du kan se at vi har representert hver node i listen som en struct som inneholder to ting, et heltall for å lagre kalt 'val' og en link til neste node i listen som vi representerer som en peker som heter "neste". På denne måten kan vi spore hele listen med bare en enkelt peker til første node, og så kan vi følge de neste pekere til 2. node, til 3. node, til 4. node, og så videre, helt til vi kommer til slutten av listen. 

Du kan være i stand til å se en fordel dette har over statisk array struktur - med en lenket liste, Vi trenger ikke en stor del av minnet helt. Den første noden i listen kunne leve på dette stedet i minnet, og andre node kan være hele veien hit. Vi kan få til alle nodene uansett hvor i minnet er de, fordi starter på første node, hver node neste pekeren forteller oss nøyaktig hvor du skal gå neste. 

I tillegg har vi ikke å si opp foran hvor stor en lenket liste vil være måten vi gjør med statiske arrays, siden vi kan fortsette å legge noder i en liste så lenge det er plass et sted i minnet for nye noder. Derfor lenkede lister er lett å endre størrelsen dynamisk. Si, senere i programmet må vi legge til flere noder til listen vår. Å sette inn en ny node i vår liste på sparket, alt vi trenger å gjøre er å allokere minne for den noden, plop i dataverdi, og deretter plassere den der vi ønsker ved å justere de nødvendige pekere. 

For eksempel, hvis vi ønsket å plassere en node i mellom 2. og 3. noder i listen,  vi ville ikke ha å flytte andre eller tredje noder i det hele tatt. Si at vi setter denne røde noden. Alt vi måtte gjøre er å sette den nye nodens neste pekeren å peke på den tredje node og deretter ReWire andre nodens neste pekeren å peke på vår nye node. Så kan vi endre størrelsen våre lister på fly siden vår datamaskin ikke stole på indeksering, men heller på å knytte bruke pekere til å lagre dem. 

Imidlertid, en ulempe med koblede lister er at, i motsetning til en statisk array, maskinen kan ikke bare hoppe til midten av listen. Siden maskinen har å besøke hver node i lenket liste å komme til neste, det kommer til å ta lengre tid å finne en bestemt node enn det ville i en matrise. Å traversere hele listen tar tid proporsjonal til lengden av listen, eller O (n) i asymptotisk notasjon. I gjennomsnitt, nå noen node også tar tid proporsjonal med n. 

Nå, la oss faktisk skrive noen kode som fungerer med koblede lister. La oss si at vi en lenket liste av heltall. Vi kan representere en node i vår liste igjen som en struct med 2 felt, et heltall kalles 'val' og en neste pekeren til neste node i listen. Vel, synes enkel nok. 

La oss si vi ønsker å skrive en funksjon som gjennomgår listen og skriver ut som er lagret i den siste noden i listen. Vel, det betyr at vi må traversere alle nodene i listen å finne den siste, men siden vi ikke legger eller slette noe, ønsker vi ikke å endre den interne strukturen av de neste pekere i listen. 

Så trenger vi en peker spesielt for traversering som vi kaller 'crawler. Den kryper gjennom alle elementene i listen ved å følge kjeden av neste pekere. Alt vi har lagret er en peker til første node, eller "hodet" på listen. Hodet peker til første node. Det er av typen pointer-til-node. 

For å få den faktiske første node i listen, vi må dereferanse denne pekeren, men før vi kan dereferanse det, må vi sjekke hvis pekeren er null først. Hvis det er null, er listen tom, og vi bør skrive ut en melding om at, fordi listen er tom, det er ingen siste noden. Men, la oss si at listen er ikke tom. Hvis det ikke er det, så vi bør gjennomgå hele listen før vi kommer til den siste noden i listen, og hvordan kan vi vite at vi ser på den siste noden i listen? 

Vel, hvis en node neste pekeren er null, Vi vet at vi på slutten siden siste neste pekeren ville ha noe neste node i listen for å vise til. Det er god praksis å alltid holde den siste noden neste pekeren initialisert til null å ha en standardisert egenskap som varsler oss når vi har nådd slutten av listen. 

Så hvis crawler → neste er null, husk at pilen syntaksen er en snarvei for dereferencing en peker til en struct, deretter tilgang dens neste felt tilsvarer klosset: (* Crawler). Neste. Når vi har funnet den siste noden, Vi vil skrive ut crawler → val, verdien i gjeldende node som vi vet er den siste. Ellers, hvis vi er ennå ikke i siste node i listen, vi må gå videre til neste node i listen og sjekk om det er den siste. For å gjøre dette, vi bare sette vår crawler pekeren å peke på gjeldende node neste verdi, det vil si den neste node i listen. Dette gjøres ved å sette crawler = crawler → neste. Så vi gjentar denne prosessen, med en løkke for eksempel, til vi finner den siste noden. Så, for eksempel, hvis crawler pekte på hodet, vi satt crawler til å peke på crawler → neste, som er det samme som det neste feltet i første noden. Så nå søkeroboten peker til andre node, og, igjen, gjentar vi dette med en løkke, før vi har funnet den siste noden, er at hvor noden neste pekeren peker til null. Og der har vi det, vi har funnet den siste noden i listen, og til å skrive ut sin verdi, vi bare bruke crawler → val. 

Traversering er ikke så ille, men hva med å sette inn? La oss si at vi ønsker å sette et heltall i fjerde posisjon i et heltall liste. Som er mellom dagens tredje og fjerde noder. Igjen har vi å traversere listen bare for å komme til tredje element, den vi setter etter. Så lager vi en crawler peker igjen for å traversere listen, sjekk om vårt hode pekeren er null, og hvis det ikke er det, peke søkeroboten pekeren på hodet node. Så er vi på første element. Vi må gå frem to flere elementer før vi kan sette inn, slik at vi kan bruke en for loop int i = 1; i <3; i + + og i hver iterasjon av loopen, fremme søkeroboten pekeren framover ved en node ved å sjekke om den nåværende node neste feltet er null, og hvis det ikke er det, flytter søkeroboten pekeren til neste node ved å sette den lik gjeldende node neste pekeren. Så, siden vår for loop sier å gjøre det to ganger, Vi har nådd tredje node, og når søkeroboten indikatoren har nådd node etter som vi ønsker å sette vår nye heltall, hvordan gjør vi faktisk gjør innsetting? 

Vel, har vår nye heltall som skal settes inn i listen som en del av sin egen node struct, siden dette er virkelig en sekvens av noder. Så, la oss lage en ny pekepinn på node kalt "new_node, ' og sett den til å peke til minne om at vi nå bevilger på haugen for noden selv, og hvor mye minne trenger vi å fordele? Vel, på størrelse med en node, og vi ønsker å sette sitt val feltet til heltall som vi vil sette inn. La oss si, 6. Nå inneholder noden vårt heltallsverdi. Det er også lurt å starte den nye nodens neste felt å peke på null, men hva nå? 

Vi må endre interne strukturen listen og de neste pekere finnes i listen eksisterende 3. og 4. noder. Siden de neste pekere bestemme rekkefølgen av listen, og siden vi sette vår nye node rett inn i midten av listen, det kan være litt vanskelig. Dette er fordi, husk, vår datamaskin vet bare plasseringen av noder i listen grunn av de neste pekere lagret i tidligere noder. Så, hvis vi noen gang mistet oversikten over noen av disse stedene, si ved å endre en av de neste pekere i vår liste, for eksempel, sier vi endret 3. nodens neste felt å peke på noen node over her. Vi vil være ute av lykken, fordi vi ikke ville har noen anelse om hvor du finner resten av listen, og det er åpenbart veldig dårlig. Så må vi være veldig forsiktig med rekkefølgen der vi manipulere våre neste pekere under innsetting. 

Så, for å forenkle dette, la oss si at våre 4 første noder kalles A, B, C og D, med pilene representerer kjeden av pekere som kobler nodene. Så må vi sette inn vår nye node i mellom noder C og D. Det er viktig å gjøre det i riktig rekkefølge, og jeg vil vise deg hvorfor. 

La oss se på feil måte å gjøre det først. Hei, vi vet den nye noden må komme rett etter C, så la oss sette C neste pekeren å peke på new_node. Greit, virker greit, vi må bare gjøre ferdig nå ved gjør den nye nodens neste pekeren peker til D, men vent, hvordan kan vi gjøre det? Det eneste som kunne fortelle oss hvor D var, var neste pekeren tidligere lagret i C, men vi omskrev at pekeren å peke på den nye noden, så vi ikke lenger har noen anelse hvor D er i minnet, og vi har mistet resten av listen. Ikke bra i det hele tatt. 

Så, hvordan vi gjør dette riktig? Først peker den nye nodens neste peker på D. Nå, både den nye nodens og C er neste pekere peker til samme node, D, men det er fint. Nå kan vi peke C neste pekeren på den nye noden. Så har vi gjort dette uten å miste data. I kode, er C gjeldende node at traversering pekeren crawler peker til, og D er representert ved noden pekes til av gjeldende nodens neste felt, eller crawler → neste. Så vi først sette den nye nodens neste pekeren å peke på crawler → neste, på samme måte som vi sa new_node neste pekeren skal peke på D i illustrasjonen. Deretter kan vi sette gjeldende node neste pekeren til vår nye node, akkurat som vi måtte vente til punkt C til new_node i tegningen. Nå er alt er i orden, og vi tapte ikke spore av data, og vi var i stand til å bare stokk vår nye node i midten av listen uten å gjenoppbygge det hele eller skiftende noen elementer måten vi ville ha hatt til med en fast lengde array. 

Så, koblede lister er en grunnleggende, men viktig, dynamisk datastruktur som har både fordeler og ulemper sammenlignet matriser og andre datastrukturer, og som ofte er tilfellet i informatikk, det er viktig å vite når du skal bruke hvert verktøy, slik at du kan velge riktig verktøy til rett jobb. 

For mer praksis, kan du prøve å skrive funksjoner slette noder fra en lenket liste - Husk å være forsiktig om i hvilken rekkefølge du omorganisere de neste pekere for å sikre at du ikke mister en del av listen - eller en funksjon for å telle nodene i en lenket liste, eller en morsom en, for å snu rekkefølgen på alle nodene i en lenket liste. 

Mitt navn er Jackson Steinkamp, ​​er dette CS50.