[Powered by Google Translate] Bij het programmeren, we moeten vaak lijsten van waarden vertegenwoordigen, zoals de namen van de studenten in een sectie of hun scores op de laatste quiz. 

In de taal C, verklaarde arrays kunnen worden gebruikt lijsten te slaan. Het is gemakkelijk om op te noemen de elementen van een lijst opgeslagen in een array, en als je nodig hebt om toegang te krijgen of wijzigen de i-de element in de lijst enkele willekeurige index I, gedaan kan worden in constante tijd, maar arrays nadelen ook. 

Toen we ze verklaren, zijn we verplicht om te zeggen van te voren hoe groot ze zijn, dat wil zeggen, hoeveel elementen ze slaan kunnen en hoe groot deze elementen, die wordt bepaald door hun type. Zo int arr (10) kan 10 items die de grootte van een int. 

We kunnen een array grootte niet veranderen na aangifte. We moeten een nieuwe array maken als we willen meer elementen op te slaan. De reden bestaat deze beperking is dat onze programma slaat de hele reeks als een aaneengesloten stuk geheugen. Zeggen dat dit de buffer waar we opgeslagen in ons aanbod. Er kunnen andere variabelen direct naast de array gelegen in het geheugen, dus we kunnen niet gewoon de array groter. 

Soms willen we de array snelle toegang tot de gegevens snelheid handel voor een beetje meer flexibiliteit. Voer de gelinkte lijst, een andere fundamentele data structuur u misschien niet zo vertrouwd zijn met. Op een hoog niveau, een gekoppelde lijst opgeslagen gegevens in een reeks knooppunten die met elkaar verbonden met links, vandaar de naam 'gelinkte lijst.' Zoals we zullen zien, dit verschil in ontwerp leidt tot verschillende voordelen en nadelen dan een array. 

Hier zijn een paar C-code voor een zeer eenvoudige gelinkte lijst van gehele getallen. U kunt zien dat we elk knooppunt vertegenwoordigd in de lijst als een struct die 2 dingen bevat, een geheel getal op te slaan genaamd 'val' en een link naar het volgende knooppunt in de lijst die wij vertegenwoordigen als een pointer genaamd 'volgende'. Op deze manier kunnen we volgen de hele lijst met slechts een enkele verwijzing naar de 1e knooppunt, en dan kunnen we volgen de volgende verwijzingen de 2e knooppunt, de 3e knooppunt, de 4e knooppunt, en zo verder, totdat we aan het einde van de lijst. 

Je zou in staat zijn om een ​​voordeel heeft dit te zien over de statische array structuur - met een gekoppelde lijst, we niet helemaal behoefte aan een groot deel van het geheugen. De 1e knooppunt van de lijst zou kunnen leven op deze plaats in het geheugen, en de 2e knooppunt kan helemaal over hier te zijn. We kunnen krijgen om alle knooppunten ongeacht waar in het geheugen ze zijn, want vanaf de 1e node, elke node's volgende pointer vertelt ons precies waar naar de volgende te gaan. 

Bovendien hoeven we niet te zeggen van te voren hoe groot een gekoppelde lijst zal de manier waarop we dat doen met statische arrays zijn, want we kunnen blijven toevoegen knooppunten om een ​​lijst zolang er ergens geheugenruimte voor nieuwe knooppunten. Daarom gelinkte lijsten zijn makkelijk te dynamisch wijzigen. Zeg, later in het programma moeten we meer knooppunten toe te voegen aan onze lijst. Om een ​​nieuw knooppunt te voegen aan onze lijst op de vlieg, alles wat we hoeven te doen is geheugen toewijzen voor dat knooppunt, plop in de gegevens waarde, en plaats het waar we willen door het aanpassen van de betreffende aanwijzingen. 

Bijvoorbeeld, als we een plaats tussen knooppunt de 2e en 3e knooppunten van de lijst,  zouden we niet naar de 2e of 3e nodes bewegen. Zeggen dat we deze rode knooppunt invoegen. Alles wat we zouden moeten doen is de nieuwe node volgende pointer om te wijzen op de 3e knooppunt en dan opnieuw bedraden de 2e knooppunt volgende pointer wijzen op nieuwe node. Dus kunnen we de grootte van onze lijsten op de vlieg omdat onze computer is niet afhankelijk van indexering, maar eerder over het koppelen met behulp van pointers op te slaan. 

Een nadeel van gekoppelde lijsten is dat anders dan een statische array, de computer kan niet alleen naar het midden van de lijst. Omdat de computer moet elk knooppunt bezoeken in de gekoppelde lijst om naar het volgende, het gaat om langer duren om een ​​bepaald knooppunt vinden dan zou in een array. Om doorkruisen de hele lijst kost tijd evenredig de lengte van de lijst, of O (n) in asymptotische notatie. Gemiddeld bereikt een knooppunt ook tijd kost evenredig met n. 

Laten we nu eigenlijk wat code schrijven die werkt met gelinkte lijsten. Laten we zeggen dat we willen een gelinkte lijst van gehele getallen. We kunnen een knooppunt weer te vertegenwoordigen in onze lijst als struct met twee velden, een geheel getal genaamd 'val' en een volgende pointer naar het volgende knooppunt van de lijst. Nou, lijkt simpel genoeg. 

Laten we zeggen dat we willen een functie te schrijven die doorkruist de lijst en drukt de waarde in het laatste knooppunt van de lijst. Nou, dat betekent dat we moeten alle knooppunten in de lijst doorlopen om de laatste een te vinden, maar omdat we niet toe te voegen of iets te verwijderen, willen we niet veranderen de interne structuur van de volgende verwijzingen in de lijst. 

Dus zullen we specifiek behoefte aan een pointer voor traversal die we zullen noemen 'crawler'. Het zal kruipen door alle elementen van de lijst door de keten van volgende verwijzingen. Alles wat we hebben opgeslagen is een pointer naar de 1e knooppunt, of 'hoofd' van de lijst. Hoofd wijst op de 1e node. Het is van het type pointer-naar-knooppunt. 

Om de werkelijke 1e knooppunt in de lijst te krijgen, we dereference deze verwijzing, maar voordat we kunnen dereference, we moeten controleren als de wijzer is null eerste. Als het nul, is de lijst leeg is, en we moeten printen een bericht dat, omdat de lijst leeg is, er is geen laatste knooppunt. Maar, laten we zeggen dat de lijst niet leeg is. Als het niet, dan moeten we kruipen door de hele lijst tot we bij de laatste knoop van de lijst, en hoe kunnen we zien of we kijken naar het laatste knooppunt in de lijst? 

Nou, als een knooppunt volgende pointer null, we weten dat we aan het eind sinds de laatste volgende pointer zou er geen volgende knooppunt in de lijst aan te wijzen. Het is een goede gewoonte om altijd het laatste knooppunt volgende pointer geïnitialiseerd op nul een gestandaardiseerde woning die ons waarschuwt als we aan het eind van de lijst te hebben. 

Dus, als crawler → volgende is null, vergeet niet dat de pijl syntax is een snelkoppeling voor dereferentie een pointer naar een struct, dan de toegang tot haar volgende veld gelijk aan het lastige: (* Crawler). Volgende. Zodra we hebben gevonden de laatste knoop, we willen crawler → val af te drukken, de waarde in het huidige knooppunt waarvan we weten dat de laatste. Anders, als we nog niet op het laatste knooppunt in de lijst, we hebben om verder te gaan naar het volgende knooppunt in de lijst en controleer of dat is de laatste. Om dit te doen, we zetten onze crawler wijzer wijzen op het huidige knooppunt volgende waarde, dat wil zeggen het volgende knooppunt in de lijst. Dit gebeurt door crawler = crawler → volgende. Dan herhalen we dit proces, met een lus bijvoorbeeld, totdat we de laatste knoop. Dus bijvoorbeeld als crawler wees het hoofd, we crawler te wijzen op crawler → volgende, die gelijk is aan het volgende veld van het eerste knooppunt. Zo, nu onze crawler wijst naar de 2e knooppunt, en, opnieuw, herhalen we dit met een lus, totdat we de laatste knoop gevonden, dat wil zeggen, waar de node volgende pointer wijst op null. En daar hebben we het, we hebben gevonden de laatste knooppunt in de lijst, en om de waarde af te drukken, gebruiken we gewoon crawler → val. 

Traverseren is niet zo erg, maar hoe zit het met het invoegen van? Laten we zeggen dat we willen een geheel getal in te voegen in de 4e positie in een geheel getal lijst. Dat tussen de huidige 3e en 4e nodes. Nogmaals, we de lijst doorlopen gewoon naar de 3e element, degene die we het invoegen na. Dus hebben we opnieuw een crawler pointer naar de lijst doorkruisen, controleren of ons hoofd aanwijzer null, en als het niet zo is, wijzen onze crawler pointer aan het hoofd node. Dus, we zijn in het 1e element. We moeten gaan voor 2 meer elementen voordat we kunnen invoegen, dus we kunnen gebruik maken van een for-lus int i = 1; i <3; i + + en elke iteratie van de lus, vooruit vooruit onze crawler pointer met 1 knoop controleren of het huidige knooppunt volgende veld nul is, en als het dat niet is, bewegen onze crawler aanwijzer naar het volgende knooppunt door het gelijk aan naast de huidige knooppunt aanwijzer. Dus, omdat onze lus zegt om dat te doen tweemaal we hebben bereikt de 3e knooppunt, en zodra onze crawler pointer heeft bereikt het knooppunt na die we willen onze nieuwe integer te voegen, hoe kunnen we eigenlijk de plaatsen? 

Nou, onze nieuwe integer moet worden ingevoegd in de lijst als onderdeel van haar eigen knooppunt struct, aangezien dit echt een reeks knooppunten. Dus, laten we een nieuwe pointer te leveren aan knooppunt genaamd 'new_node,' en zet deze om te wijzen op het geheugen dat we nu kennen op de hoop voor de knoop zelf, en hoeveel geheugen hebben we nodig om toe te wijzen? En de grootte van een knooppunt, en we willen haar val veld is ingesteld op het gehele getal dat we willen invoegen. Laten we zeggen, 6. Nu, het knooppunt omvat ons geheel getal. Het is ook een goede gewoonte om te initialiseren van de nieuwe node volgende veld te wijzen op null, maar wat nu? 

We moeten de interne structuur van de lijst te wijzigen en de volgende verwijzingen in de bestaande van de lijst 3e en 4e nodes. Omdat de volgende verwijzingen bepalen de volgorde van de lijst, en aangezien we het plaatsen van onze nieuwe knooppunt recht in het midden van de lijst, het kan een beetje lastig. Dit is te onthouden, omdat,, onze computer alleen weet waar knooppunten in de lijst door de volgende verwijzingen opgeslagen in de vorige nodes. Dus, als we ooit verloren spoor van een van deze locaties, zeggen door het veranderen van een van de volgende verwijzingen in onze lijst, bijvoorbeeld zeggen dat we veranderd de 3e knooppunt volgende veld om te wijzen op een aantal knooppunten hier. We zouden pech, want we zouden niet enig idee waar de rest van de lijst te vinden, en dat is natuurlijk heel slecht. Dus, we moeten echt voorzichtig zijn over de volgorde waarin we manipuleren onze volgende aanwijzingen tijdens het inbrengen. 

Dus, om dit te vereenvoudigen, laten we zeggen dat onze eerste 4 knopen genoemd A, B, C en D, met de pijlen die de keten van pointers de knooppunten verbinden. Dus, moeten we onze nieuwe knooppunt plaatst tussen knooppunten C en D. Het is essentieel om het te doen in de juiste volgorde, en ik zal je laten zien waarom. 

Laten we eens kijken naar de verkeerde weg naar de eerste te doen. Hey, we weten dat de nieuwe node heeft het recht te komen na C, dus laten we stellen volgende pointer C's te wijzen op new_node. Oke, oke lijkt, we moeten nu af te maken door het maken van de nieuwe node volgende pointer wijzen naar D, maar wacht, hoe kunnen we dat doen? Het enige dat ons kan vertellen waar D was, werd de volgende pointer eerder opgeslagen in C, maar we herschreven dat wijzer verwijzen naar de nieuwe knooppunt dus we hebben niet langer enig idee waar D is in het geheugen, en we hebben verloren de rest van de lijst. Helemaal niet goed. 

Dus, hoe doen we dit recht? Ten eerste, richt de nieuwe node volgende pointer bij D. Nu zowel het nieuwe knooppunt C en de volgende verwijzingen verwijzen naar dezelfde knooppunt D, maar dat is prima. Nu kunnen we wijzen volgende pointer C's op de nieuwe node. Dus hebben we dit gedaan zonder gegevens te verliezen. In code, C is het huidige knooppunt dat de traversal wijzer crawler wordt verwezen, en D wordt vertegenwoordigd door het knooppunt naar wijst naast het huidige knooppunt veld, of rupsbanden → volgende. Dus, we eerst de nieuwe node volgende pointer om te wijzen op crawler → volgende, op dezelfde manier waarop we zeiden volgende pointer new_node's moeten wijzen op D in de afbeelding. Dan kunnen we het huidige knooppunt van de volgende pointer op onze nieuwe knooppunt, net zoals we moesten wachten om C wijzen op new_node in de tekening. Nu alles is in orde, en we hebben niet verliezen bijhouden van alle gegevens, en we waren in staat om gewoon blijven nieuwe knoop in het midden van de lijst zonder de wederopbouw van de hele zaak, of zelfs verschuiven alle elementen de manier waarop we zouden hebben gehad om met een vaste lengte array. 

Dus, gelinkte lijsten zijn een eenvoudige, maar belangrijke, dynamische datastructuur die zowel voor-en nadelen vergelijking met arrays en andere datastructuren, en zoals vaak het geval is in de informatica, is het belangrijk om te weten wanneer elk instrument te gebruiken, zodat u kunt kiezen het juiste gereedschap voor de juiste baan. 

Voor meer oefening, proberen het schrijven van functies knooppunten verwijderen uit een gekoppelde lijst - vergeet niet om voorzichtig te zijn over de volgorde waarin u herschikken uw volgende aanwijzingen om ervoor te zorgen dat je niet een stuk van uw lijst te verliezen - of een functie aan de knooppunten tellen in een verbonden lijst, of een leuke een, de volgorde van alle knooppunten in een gekoppelde lijst keren. 

Mijn naam is Jackson Steinkamp, ​​dit is CS50.