[Powered by Google Translate] I programmering behöver vi ofta för att representera listor över värden, såsom namnen på eleverna i ett avsnitt eller deras poäng på den senaste frågesporten. 

I C-språket, deklarerade arrayer kan användas att lagra listor. Det är lätt att räkna upp elementen i en lista lagras i en array, och om du behöver komma åt eller ändra den i: te listelement för någon godtycklig index I, som kan göras i konstant tid, men arrayer har nackdelar också. 

När vi förklarar dem, vi måste säga på framsidan hur stora de är, det vill säga hur många element som de kan lagra och hur stor dessa element är, som bestäms av deras typ. Till exempel, int arr (10) kan lagra 10 poster som är storleken på en int. 

Vi kan inte ändra en rad storlek efter anmälan. Vi måste göra en ny array om vi vill lagra fler element. Anledningen till att denna begränsning finns är att vår Programmet lagrar hela uppsättningen som en sammanhängande bit av minne. Säga att detta är den buffert där vi lagras i vår grupp. Det kan finnas andra variabler ligger intill matrisen i minnet, så att vi inte kan bara göra arrayen större. 

Ibland vill vi handla arrayen snabba dataåtkomst hastighet för lite mer flexibilitet. Ange den länkade listan, en annan grundläggande datastruktur du kanske inte så bekant med. På en hög nivå, en länkad lista lagrar data i en sekvens av noder som är anslutna till varandra med länkar, därav namnet "länkad lista". Som vi ser, denna skillnad i design leder till olika fördelar och nackdelar än en matris. 

Här är några C-kod för en länkad mycket enkel lista med heltal. Du kan se att vi har representerade varje nod i listan som en struct som innehåller 2 saker, ett heltal för att lagra kallas "Val ' och en länk till nästa nod på listan som vi representerar som en pekare som kallas "Nästa". På detta sätt, kan vi spåra hela listan med bara en enda pekare till den 1: a noden, och då kan vi följa nästa pekare till den 2: a noden, till den 3: e noden, till 4: e noden, och så vidare, tills vi kommer till slutet av listan. 

Du kanske kan se en fördel har detta över den statiska matrisstruktur - med en länkad lista, Vi behöver inte en stor bit av minnet helt och hållet. Den 1: a noden i listan kunde leva på denna plats i minnet, och 2nd noden kan vara ända hit. Vi kan få till alla noder oavsett var i minnet de är, eftersom start vid 1: a noden varje nod nästa pekare berättar exakt vart man ska gå härnäst. 

Dessutom behöver vi inte säga upp front hur stor en länkad lista kommer att vara hur vi gör med statiska arrayer, eftersom vi kan fortsätta att lägga noder i en lista så länge det finns utrymme någonstans i minnet för nya noder. Därför länkade listor är lätta att ändra storlek dynamiskt. Säg, senare i programmet måste vi lägga till fler noder i vår lista. Om du vill infoga en ny nod i vår lista i farten, allt vi behöver göra är att allokera minne för denna nod, plopp i datavärdet, och sedan placera den där vi vill genom att justera lämpliga pekare. 

Till exempel, om vi ville placera en nod i mellan den 2: a och 3: e noder i listan,  Vi skulle inte behöva flytta 2 eller 3 noder alls. Säg att vi sätter denna röda nod. Allt vi skulle behöva göra är att ställa den nya noden nästa pekare att peka på noden 3:e och sedan ReWire 2: a noden nästa pekare att peka på vår nya noden. Så kan vi ändra storleken våra listor på fluga eftersom vår dator inte är beroende av indexering, utan snarare på att koppla med pekare för att lagra dem. 

Emellertid, en nackdel med länkade listor är att, till skillnad från en statisk matris, datorn kan inte bara hoppa till mitten av listan. Eftersom datorn har att besöka varje nod i den länkade listan för att komma till nästa, det kommer att ta längre tid att hitta en viss nod än den skulle i en array. Att korsa hela listan tar tid proportionell till längden av listan, eller O (n) i asymptotisk notation. I genomsnitt, når varje nod också tar tid proportionell mot n.. 

Nu ska vi faktiskt skriva lite kod som arbetar med länkade listor. Låt oss säga att vi vill ha en länkad lista av heltal. Vi kan representera en nod i vår lista igen som en struktur med 2 fält, ett heltal kallas "Val ' och en nästa pekare till nästa nod på listan. Tja, det verkar enkelt nog. 

Låt oss säga att vi vill skriva en funktion som går igenom listan och skriver ut värde som lagras i den sista noden i listan. Tja, innebär att vi kommer att behöva korsa alla noder i listan att hitta den sista, men eftersom vi inte lägger eller ta bort något, vi vill inte ändra den interna strukturen för nästa pekare i listan. 

Så behöver vi en pekare speciellt för traversering som vi kallar "sökrobot". Det kommer att krypa igenom alla element i listan genom att följa kedjan av nästa pekare. Allt vi har lagrat en pekare till den 1: a noden, eller "chef" i listan. Head pekar på 1. Noden. Det är av typen pekare-till-nod. 

För att få den verkliga 1:e nod i listan, vi dereference denna pekare, men innan vi kan dereference det måste vi kontrollera Om pekaren är null först. Om det är noll, är listan tom, och vi bör skriva ut ett budskap att eftersom listan är tom, det finns ingen sista nod. Men låt oss säga att listan inte är tom. Om det inte, bör vi krypa igenom hela listan tills vi kommer till den sista noden i listan, och hur kan vi berätta om vi tittar på den sista noden i listan? 

Tja, om en nod nästa pekare är null Vi vet att vi är i slutet sedan den senaste nästa pekare skulle ha någon nästa nod i listan för att peka på. Det är en god vana att alltid hålla den sista noden nästa pekare initieras till null att ha ett standardiserat egenskap som varnar oss när vi har nått slutet av listan. 

Så om sökrobot → Nästa är null, kom ihåg att pilen syntaxen är en genväg för att dereferencing en pekare till en struktur, och sedan komma nästa fält motsvarar besvärliga: (* Larvfötter). Nästa. När vi har hittat den sista noden, Vi vill skriva ut sökrobot → val, värdet i den aktuella noden som vi vet är den sista. Annars, om vi inte ännu på den sista noden i listan, Vi måste gå vidare till nästa nod i listan och kontrollera om det är den sista. För att göra detta, satte vi bara vår sökrobot pekare att peka på den aktuella noden nästa värde, dvs, den nästa nod i listan. Detta görs genom att ställa sökrobot = sökrobot → Nästa. Då vi upprepa denna process med en ögla till exempel, tills vi hittar den sista noden. Så, till exempel, om sökrobot pekade på huvudet, Vi satt sökrobot peka på sökrobot → nästa, som är densamma som nästa fält av den 1st noden. Så, nu är vår sökrobot pekar på 2. Noden, och, återigen, upprepar vi detta med en slinga, tills vi har hittat den sista noden, är att där noden nästa pekare pekar på null. Och där har vi det, Vi har hittat den sista noden i listan och skriva ut dess värde, Vi använder bara larvfötter → val. 

Tvärgående är inte så illa, men hur du sätter? Låt oss säga att vi vill infoga ett heltal i den 4: e positionen i ett heltal lista. Det är mellan de nuvarande 3 och 4 noder. Återigen måste vi korsa listan bara för att få till den 3: e elementet, ett vi sätter efter. Så skapar vi en sökrobot pekare igen korsa listan, kontrollera om vår framvisaren är null och om det inte pekar vår sökrobot pekare på huvudnoden. Så vi är på 1: a elementet. Vi måste gå framåt 2 fler element innan vi kan sätta in, så att vi kan använda en for-slinga int i = 1; i <3, jag + + och i varje iteration av slingan, öka vår sökrobot pekare fram 1 nod genom att kontrollera om den aktuella noden nästa fält är noll, och om det inte flyttar vår sökrobot pekare till nästa nod genom att ställa det lika med den aktuella noden nästa pekare. Så, eftersom vår för slinga säger att göra det två gånger, Vi har nått den 3: e noden, och när vår sökrobot pekare har nått noden efter som vi vill infoga vår nya heltal, hur vi faktiskt göra sätta? 

Tja, har vår nya heltal som skall införas i den förteckning som en del av sin egen nod struct, eftersom detta är verkligen en sekvens av noder. Så, låt oss göra en ny pekare till noden kallas new_node " och ställa in den att peka på minnet att vi nu fördela i stacken för själva noden, och hur mycket minne behöver vi fördela? Jo, storleken av en nod, och vi vill sätta sin val fält till heltal som vi vill infoga. Låt oss säga, 6. Nu innehåller noden vår heltalsvärde. Det är också bra att initiera den nya noden nästa fält peka på null, men nu vad? 

Vi måste förändra den interna strukturen av listan och nästa pekare som finns i listan befintliga 3 och 4 noder. Eftersom nästa pekare bestämma i vilken ordning listan, och eftersom vi sätter vår nya noden rakt in i mitten av listan, det kan vara lite knepigt. Detta beror, kom ihåg, vår dator endast känner placeringen av noder i listan på grund av de nästa pekare lagrade i de tidigare noderna. Så, om vi någonsin förlorat reda på någon av dessa platser, säga genom att ändra en av de kommande pekare i vår lista, till exempel, säger vi ändrat den 3: e noden nästa fält att peka på någon nod hit. Vi skulle vara ute på tur, eftersom vi inte skulle har någon aning om var att hitta resten av listan, och det är naturligtvis riktigt illa. Så måste vi vara riktigt försiktig om beställning där vi manipulerar vår nästa pekare under införande. 

Så, för att förenkla detta, låt oss säga att vår första 4 noder kallas A, B, C och D, med pilarna representerar kedjan av pekare som ansluter noderna. Så måste vi sätta vår nya noden mellan noderna C och D. Det är viktigt att göra det i rätt ordning, och jag ska visa dig varför. 

Låt oss titta på fel sätt att göra det först. Hej, vi vet den nya noden måste komma direkt efter C, så låt oss ställa C: s nästa pekare att peka på new_node. Okej, verkar okej, vi bara avsluta nu genom gör den nya noden nästa pekare pekar på D, men vänta, hur kan vi göra det? Det enda som skulle kunna tala om för oss där D var, var nästa pekare lagrad tidigare i C, men vi skrev bara att pekaren att peka till den nya noden, så vi inte längre har någon aning där D är i minnet, och vi har förlorat resten av listan. Inte bra alls. 

Så, hur vi gör detta rätt? Först pekar den nya noden nästa pekare vid D. Nu, både den nya nodens och C: s nästa pekare pekar på samma nod, D, men det är bra. Nu kan vi punkt C nästa pekare på den nya noden. Så har vi gjort detta utan att förlora några data. I kod, C är aktuella noden att förflyttning pekaren sökrobot pekar på, och D representeras av noden pekas på av den aktuella noden nästa fält, eller larvfötter → Nästa. Så ställer vi först den nya noden nästa pekare att peka på sökrobot → nästa, på samma sätt som vi sa new_node nästa pekare bör peka till D i figuren. Då kan vi ställa den aktuella noden nästa pekare till vår nya noden, precis som vi var tvungna att vänta till punkt C för att new_node på ritningen. Nu allt är i ordning, och vi inte förlorar reda på alla uppgifter, och vi kunde bara hålla vår nya nod i mitten av listan utan att bygga om hela eller ens flytta några element det sätt vi skulle ha behövt en fast längd matris. 

Så, länkade listor är en grundläggande, men viktiga, dynamiska datastruktur som har både fördelar och nackdelar jämfört med matriser och andra datastrukturer, och som ofta är fallet i datavetenskap, Det är viktigt att veta när du ska använda varje verktyg, så att du kan välja rätt verktyg för rätt jobb. 

För mer övning, försök att skriva funktioner bort noder från en länkad lista - kom ihåg att vara försiktig om i vilken ordning du ordna ditt nästa pekare för att säkerställa att du inte förlorar en bit av din lista - eller en funktion för att räkna noderna i en länkad lista, eller en rolig en, för att kasta om ordningen av alla noder i en länkad lista. 

Mitt namn är Jackson Steinkamp, ​​det här CS50.