[Powered by Google Translate] I programmering, vi ofte nødt til at repræsentere lister over værdier, såsom navne på studerende i et afsnit eller deres scoringer på det seneste quiz. 

I C-sprog, erklæres arrays kan anvendes at lagre lister. Det er nemt at opregne de elementer i en liste gemt i et array, og hvis du har brug for at få adgang eller ændre den i'te listeelement for en vilkårlig indeks I, der kan gøres i konstant tid, men arrays har ulemper, også. 

Når vi erklære dem, er vi forpligtet til at sige op foran hvor store de er, det vil sige, hvor mange elementer, de kan gemme og hvor store disse elementer, som bestemmes af deres type. For eksempel, int arr (10) kan gemme 10 varer der er på størrelse med en int. 

Vi kan ikke ændre et array størrelse efter erklæring. Vi er nødt til at lave et nyt array, hvis vi ønsker at gemme flere elementer. Grunden denne begrænsning eksisterer, er, at vores programmet lagrer hele arrayet som en sammenhængende luns af hukommelsen. Sige dette er den buffer, hvor vi gemt i vores array. Der kan være andre variabler beliggende lige ud til arrayet i hukommelsen, så vi kan ikke bare gøre array større. 

Nogle gange er vi gerne vil handle arrayet hurtige dataadgang hastighed for lidt mere fleksibilitet. Indtast den linkede liste, en anden grundlæggende datastruktur du måske ikke være så fortrolige med. På et højt niveau, en sammenkædet liste lagrer data i en sekvens af knudepunkter som er forbundet til hinanden med links, deraf navnet 'linkede liste.' Som vi vil se, denne forskel i design fører til forskellige fordele og ulemper end et array. 

Her er nogle C-kode for en meget simpel hægtet liste af heltal. Du kan se, at vi har repræsenteret hver node på listen som en struct, der indeholder 2 ting, et heltal til at gemme kaldes 'val' og et link til den næste node i listen som vi repræsenterer som en pegepind kaldes 'næste'. På denne måde kan vi spore hele listen med blot et enkelt pointer til 1. node, og så kan vi følge de næste pointers til 2. node, til 3. node, til 4. node, og så videre, indtil vi kommer til slutningen af ​​listen. 

Du vil måske være i stand til at se 1 fordel dette har over den statiske array-struktur - med en linket liste, vi har ikke brug for en stor luns af hukommelse helt. Den 1. node af listen kunne leve på dette sted i hukommelsen, og 2. knude kunne være helt herovre. Vi kan komme til alle de noder, uanset hvor i hukommelsen de er, fordi starter ved 1. knudepunkt, hver node næste pointer fortæller os præcis, hvor de skal gå næste. 

Derudover har vi ikke til at sige op foran hvor stor en sammenkædet liste vil være den måde, vi gør med statiske arrays, da vi kan holde tilføje noder til en liste så længe der er plads et eller andet sted i hukommelsen for nye noder. Derfor hægtede lister er nemme at ændre størrelsen dynamisk. Sig, senere i det program, vi har brug for at tilføje flere noder ind i vores liste. Hvis du vil indsætte en ny node i vores liste på flue, alt, hvad vi skal gøre, er tildele hukommelse til denne knude, plumpet i dataværdi, og derefter placere den hvor vi ønsker ved at justere de passende pointers. 

For eksempel, hvis vi ønskede at anbringe en knude i mellem 2. og 3. knudepunkter i listen,  ville vi ikke nødt til at flytte den 2. eller 3. noder på alle. Sig vi indsætte denne røde node. Alt, hvad vi ville have at gøre, er at sætte den nye node næste pointer at pege til 3. node og derefter ReWire 2. knudepunkts næste pointerjustering til at pege på vores nye node. Så kan vi ændre størrelsen på vores liste på farten da vores computer ikke er afhængig af indeksering, men snarere på at knytte med pegepinde til at gemme dem. 

En ulempe ved knyttet lister er, at i modsætning til et statisk array, computeren kan ikke bare hoppe til midten af ​​listen. Da computeren har til at besøge hver node i den linkede liste for at komme til det næste, det vil tage længere tid at finde en bestemt node end den ville i et array. Til at krydse hele listen tager tid proportional til længden af ​​listen, eller O (n) i asymptotisk notation. I gennemsnit nåede enhver node også tager tid proportional med n.. 

Lad os nu faktisk skrive noget kode der arbejder med hægtede lister. Lad os sige, at vi ønsker en tilknyttet liste med heltal. Vi kan repræsentere et knudepunkt i vores liste igen som struct med 2 felter, en heltalsværdi kaldet 'val' og en næste markør til den næste node i listen. Nå, synes simpelt nok. 

Lad os sige at vi vil skrive en funktion der gennemgår listen og udskriver den lagret i det sidste emne på listen. Tja, det betyder, at vi bliver nødt til at krydse alle knuder i listen at finde den sidste, men da vi ikke har tilføjet eller slette noget, vi ikke ønsker at ændre den interne struktur i de næste markører på listen. 

Så vil vi have en pointer specielt til traversal som vi kalder "crawler". Det vil kravle gennem alle elementer i listen ved at følge kæden af ​​næste pointers. Alt, hvad vi har gemt, er en pointer til 1. node, eller 'hoved' på listen. Head peger på 1. node. Det er af typen pointer-to-node. 

For at få den faktiske 1:e node i listen, vi er nødt til at dereference denne pointer, men før vi kan dereference det, er vi nødt til at kontrollere hvis markøren er nul først. Hvis det er nul, er tom, og vi bør udskrive en besked, der, fordi listen er tom, der er ingen sidste knudepunkt. Men, lad os sige listen ikke er tom. Hvis det ikke er, så bør vi kravler gennem hele listen indtil vi kommer til det sidste emne på listen, og hvordan kan vi fortælle, hvis vi ser på det sidste emne på listen? 

Tja, hvis en node næste pointer er nul, Vi ved, vi er i slutningen siden sidste næste pointerjustering ville have nogen næste node i listen at pege på. Det er god praksis altid at holde den sidste node næste pointer initialiseret til null at have en standardiseret egenskab, som advarer os, når vi har nået slutningen af ​​listen. 

Så hvis crawler → næste er null, huske på, at pilen syntaksen er en genvej til dereferere en pointer til en struct, så adgang den næste felt svarende til den akavede: (* Crawler). Næste. Når vi har fundet den sidste node, vi ønsker at udskrive crawler → val, værdien i den aktuelle node som vi ved er den sidste. Ellers, hvis vi ikke er endnu på det sidste node i listen, vi er nødt til at gå videre til den næste node i listen og kontrollere, om det er den sidste. For at gøre dette, har vi bare indstille vores webcrawler pointer at pege på den aktuelle node næste værdi, det vil sige den næste node i listen. Dette gøres ved at sætte crawler = crawler → næste. Så kan vi gentage denne proces, med en løkke for eksempel indtil vi finder den sidste node. Så, for eksempel hvis crawler pegede på hovedet vi satte crawler til at pege på crawler → næste, hvilket er det samme som det næste felt i den 1. node. Så nu er vores crawler peger til 2. node, og igen vi gentage dette med en løkke, indtil vi har fundet den sidste node, dvs hvor knuden næste pointer peger til null. Og der har vi det, vi har fundet den sidste node i listen, og at udskrive dens værdi, vi bare bruge crawler → val. 

Gennemkører er ikke så slemt, men hvad med at indsætte? Lad os sige, at vi ønsker at indsætte et heltal i den 4. plads i et heltal liste. Det er mellem de nuværende 3. og 4. noder. Igen, vi er nødt til at krydse den liste bare til komme til 3. element, den ene vi indsætte efter. Så skaber vi en crawler pointer igen at krydse listen, kontrollere, om vores hoved pointer er nul, og hvis det ikke er, peger vores webcrawler pointer i spidsen node. Så vi er på 1. element. Vi er nødt til at gå fremad 2 flere elementer, før vi kan indsætte, så vi kan bruge en for-løkke int i = 1; i <3, jeg + + og i hver iteration af løkken, fremme vores webcrawler pointer frem med 1 node ved at kontrollere, om den aktuelle node næste felt er nul, og hvis det ikke er, skal du flytte vores webcrawler markøren til den næste node ved at sætte det lig med den aktuelle node næste pointer. Så da vores for løkke siger at gøre det to gange, vi har nået den 3. knude, og når vores webcrawler pointer har nået node efter som vi ønsker at indsætte vores nye heltal, hvordan kan vi rent faktisk gør det indsættelse? 

Nå, vores nye heltal skal indsættes i listen som en del af sin egen node struct, idet dette er virkelig en sekvens af knudepunkter. Så lad os lave en ny pointer til knude kaldes 'new_node' og sæt den til at pege på hukommelse, som vi nu tildele på heapen for knuden selv, og hvor meget hukommelse har vi brug for at afsætte? Nå, størrelsen af ​​et knudepunkt, og vi ønsker at sætte sit val felt til heltal, vi ønsker at indsætte. Lad os sige, 6. Nu node indeholder vores heltalsværdi. Det er også god praksis at initialisere den nye node næste felt at pege på null, men hvad nu? 

Vi ændre den interne struktur af listen og de næste pointers i listen eksisterende 3. og 4. knudepunkter. Da de næste pointers bestemme rækkefølgen af ​​listen, og da vi sætter vores nye knudepunkt lige ind i midten af ​​listen, det kan være en smule tricky. Dette skyldes, husk, vores computer kun kender placeringen af ​​knudepunkter i listen på grund af de næste pointers lagret i de foregående knudepunkter. Så hvis vi nogensinde mistet overblikket over nogen af ​​disse steder, sige ved at ændre en af ​​de næste pejlemærker i vores liste, for eksempel, siger vi ændret 3. knudepunkts næste felt at pege på nogle node herovre. Vi ville være ude af lykke, fordi vi ikke ville har nogen idé om, hvor at finde resten af ​​listen, og det er naturligvis virkelig dårlig. Så vi er nødt til at være virkelig forsigtig med ordren hvor vi manipulere vores næste pointers under indføring. 

Så for at forenkle det, så lad os sige, at vores første 4 noder kaldes A, B, C og D, med pilene repræsenterer kæden af ​​pegepinde der forbinder knudepunkter. Så er vi nødt til at indsætte vores nye knudepunkt i mellem knudepunkterne C og D. Det er afgørende at gøre det i den rigtige rækkefølge, og jeg vil vise dig hvorfor. 

Lad os se på den forkerte måde at gøre det først. Hey, vi ved det nye knudepunkt skal komme lige efter C, så lad os indstille C næste pointer at pege på new_node. Okay, virker okay, vi bare nødt til at slutte op nu ved gør den nye knude næste pointer pege på D, men vent, hvordan kan vi gøre det? Det eneste, der kunne fortælle os, hvor D var, blev den næste pointer tidligere lagret i C, men vi bare omskrev denne pegepind den peger på den nye knudepunkt, så vi ikke længere har nogen anelse om, hvor D er i hukommelsen, og vi har mistet resten af ​​listen. Ikke god til alle. 

Så hvordan vi gør det rigtigt? Først peger det nye knudepunkt næste pointer på D. Nu, både den nye node-og C'er næste pointers peger på det samme knudepunkt, D, men det er fint. Nu kan vi pege C næste pointer på det nye knudepunkt. Så vi har gjort dette uden at miste data. I kode, er C den aktuelle node at gennemkrydsning pointer crawler peger på, og D er repræsenteret ved knudepunktet peges på af den aktuelle node næste felt, eller crawler → næste. Så vi startede det nye knudepunkt næste pointer at pege på crawler → næste, på samme måde, vi sagde new_node næste pointer bør pege på D på illustrationen. Derefter kan vi sætte den aktuelle node næste pointer til vores nye knudepunkt, ligesom vi måtte vente til punkt C til new_node på tegningen. Nu alt er i orden, og vi ikke mister styr på alle data, og vi var i stand til bare holde vores nye knudepunkt i midten af ​​listen uden at genopbygge det hele eller endda flytte eventuelle elementer den måde, vi ville have haft til med en fast længde array. 

Så hægtede lister er en grundlæggende, men vigtig, dynamisk datastruktur som har både fordele og ulemper sammenlignet med arrays og andre datastrukturer, og som det ofte er tilfældet i datalogi, Det er vigtigt at vide, hvornår du skal bruge hvert værktøj, så du kan vælge det rigtige værktøj til det rigtige job. 

For mere praksis, så prøv at skrive funktioner til slette noder fra en sammenkædet liste - husk at være forsigtig med den rækkefølge, som du omarrangere Deres næste pointere at sikre, at du ikke mister en bid af din liste - eller en funktion til at tælle knudepunkter i et sammenkædet liste, eller en sjov en, at bytte om på rækkefølgen af ​​alle knudepunkter i en sammenkædet liste. 

Mit navn er Jackson Steinkamp, ​​det er CS50.