[MUSIC SPILLE] 

DOUG LLOYD: OK, så på dette punktet i kurset, vi har dekket mye av det grunnleggende C. Vi vet mye om variabler, matriser, pekere, alt det gode ting. De er alle slags inne i å se som det grunnleggende, men vi kan gjøre mer, ikke sant? Vi kan kombinere ting sammen på interessante måter. 

Og så la oss gjøre det, la oss starte å armen ut av hva C gir oss, og begynne å lage vår egen data strukturer ved hjelp av disse bygning blokker sammen for å gjøre noe virkelig verdifull og nyttig. En måte vi kan gjøre dette på er å snakke om samlinger. Så så langt har vi hatt en type data struktur for samlinger av like verdier, tilsvarende verdier. Det ville være en matrise. Vi har samlinger av heltall, eller samlinger av figurer og så videre. 

Strukturer er også sortere av en data struktur for innsamling av opplysninger men det er ikke for å samle like verdier. Det blander vanligvis forskjellige datatyper sammen inne i en enkelt boks. Men det er ikke i seg selv brukes til å kjede sammen eller koble sammen lignende elementer, som en matrise. Arrays er stor for element se opp, men tilbakekalling at det er svært vanskelig å sette inn i en matrise, med mindre vi setter på helt på slutten av denne matrisen. 

Og det beste eksemplet jeg har for det er innsetting sort. Hvis du husker vår video på innsetting sortere, Det var en masse utgifter som er involvert i å ha å plukke opp elementer, og flytte dem ut av veien for å passe noe inn i midten av klyngen. Arrays også lider av en annen Problemet, som er manglende fleksibilitet. Når vi erklære en matrise, vi får ett skudd på den. Vi får å si, jeg vil ha dette mange elementer. Kan være 100, det kan være 1000, det kan være x der x er et tall som brukeren ga oss en melding eller på kommando linjen. 

Men vi får bare ett skudd på det, vi får ikke til så si oh, faktisk jeg trengte 101, eller jeg trengte x pluss 20. For sent, har vi allerede erklært array, og hvis vi ønsker å få 101 eller x pluss 20, må vi erklære en helt annen matrise, kopiere alle elementene i matrisen over, og da har vi nok. Og hva om vi tar feil igjen, hva hvis vi faktisk trenger 102, eller x pluss 40, vi må gjøre dette igjen. Slik at de er svært lite fleksible for å endre størrelse våre data, men hvis vi kombinerer sammen noen av de grunnleggende at vi allerede har lært om pekere og strukturer, Spesielt ved bruk av dynamisk minne tildeling med malloc, vi kan sette disse bitene sammen å skape en ny data structure-- en enkeltvis lenket liste vi kan say-- som tillater oss å vokse og krympe en samling verdier og vi vil ikke ha noen bortkastet plass. 

Så igjen, kaller vi denne ideen, denne forestillingen, en lenket liste. Spesielt i denne videoen er vi snakker om enkeltvis lenket liste, og deretter en annen video vi skal snakke om dobbelt lenkede lister, som er bare en variant av et tema her. Men en enkeltvis lenket liste består av noder, noder bare å være en abstrakt term-- det er bare noe jeg ringer det er en slags struktur, i utgangspunktet er jeg? Bare kommer til å kalle det en node-- og dette node har to medlemmer, eller to felt. Det har data, vanligvis en heltall, et tegn flyte, eller kan være noen annen datatype at du har definert med en type def. Og den inneholder en peker til en annen node av samme type. 

Så vi har to ting inni denne noden, data og en peker til en annen node. Og hvis du begynner å visualisere dette, kan du tenke på det som en kjede av noder som er koblet sammen. Vi har den første node, det inneholder data, og en peker til den andre noden som inneholder data, og en peker til den tredje noden. Og så det er derfor vi kaller det en lenket liste, de er koblet sammen. 

Hva gjør denne spesiell nodestruktur ser ut? Vel, hvis du husker fra vår video på definere tilpassede typer, med type def, vi kan definere en structure-- og skriver definere en struktur som dette. tyepdef struct sllist, og da er jeg bruke ordet verdi her vilkårlig for å indikere hvilken som helst datatype egentlig. Du kan passere på et heltall eller flyte, du kan få hva du vil. Det er ikke begrenset til bare heltall, eller noe sånt. Så verdien er bare en vilkårlig datatype, og deretter en peker til en annen node av samme type. 

Nå er det en liten fangst her med å definere en struktur når det er en selvrefererende struktur. Jeg må ha en midlertidig nevne for min struktur. På slutten av dagen I klart vil kalle det SLL node, det er til syvende og sist den nye nevne en del av min type definisjon, men jeg kan ikke bruke sll node i midten av dette. Årsaken er, jeg har ikke skapt en type som heter sll node før jeg traff denne siste punktet her. Frem til det punktet, må jeg ha en annen måte å referere til denne datatypen. 

Og dette er en selv referensiell datatype. Den, er en datatype for en struktur som inneholder en data, og en peker til en annen struktur av samme type. Så jeg må være i stand til å referere til dette datatype i det minste midlertidig, så gir det en midlertidig Navnet på struct sllist tillater meg å så si at jeg vil ha en Peker til en annen struct sllist, en struct sllist stjerne, og deretter etter at jeg har fullført definisjon, Jeg kan nå kalle denne typen en sll node. 

Så det er derfor du ser det er et midlertidig navn her, men et permanent navn her. Noen ganger kan du se definisjoner av struktur, for eksempel, som ikke er selvrefererende, at har ikke en Specifier navn her. Det ville bare si typedef struct, åpne klammeparentes og deretter definere det. Men hvis du er struct er selv henvisnings, som denne er, må du angi en midlertidig typenavn. Men til slutt, nå at vi har gjort dette, Vi kan bare henvise til disse nodene, disse enheter, som SLL noder for formål av resten av denne videoen. 

Greit, så vi vet hvordan de skal skape en lenket liste node. Vi vet hvordan du definerer en lenket liste node. Nå, hvis vi kommer til å starte bruke dem til å samle inn informasjon, det er et par av operasjoner vi trenger å forstå og jobbe med. Vi trenger å vite hvordan du oppretter en lenket liste ut av løse luften. Hvis det er ingen liste allerede, Vi ønsker å starte en. Så vi må være i stand for å lage en lenket liste, vi må trolig søke via lenken liste å finne et element vi leter etter. Vi må være i stand til å sette inn nye ting inn i listen, Vi ønsker vår liste for å kunne vokse. Og på samme måte, vil vi være i stand å slette ting fra vår liste, Vi ønsker vår liste for å være i stand til å krympe. Og på slutten av vår programmer, særlig hvis du husker at vi er dynamisk tildele minne å bygge disse listene typisk, vi ønsker å frigjøre alle som minne når vi er ferdig å jobbe med det. Og så må vi være i stand til å slette en Hele lenket liste i ett mislykkes nedslag. Så la oss gå gjennom noen av disse operasjonene og hvordan vi kan visualisere dem, snakker i pseudokode spesifikt. Så vi ønsker å skape en lenket liste, så kanskje vi ønsker å definere en funksjon med denne prototypen. SLL node stjerne, skape, og jeg passert i ett argument, en oppkonstruert data skriver igjen, av noen vilkårlig datatype. Men jeg returning-- denne funksjonen tilbake til meg en peker til en enkeltvis lenket liste node. Igjen, vi prøver å skape en lenket liste ut av løse luften, så jeg trenger en peker til den listen når jeg er ferdig. 

Så hva er fremgangsmåten involvert her? Vel, jeg er første kommer til å gjøre er dynamisk tildele plass for en ny node. Igjen, vi skaper den ut av tynn luft, så vi trenger å malloc plass for det. Og selvfølgelig, umiddelbart etter at vi malloc, vi alltid sjekke for å være sikker på at vår pointer-- vi ikke få tilbake null. Fordi hvis vi prøver og ærbødighet en nullpeker, vi kommer til å lide en segfault og vi ønsker ikke det. 

Da vil vi gjerne fylle på feltet, vi ønsker å initialverdifeltet og initial neste felt. Og så ønsker vi to-- slutt som funksjon prototype indicates-- vi ønsker å returnere en peker til en sll node. Så hva gjør dette ser ut visuelt? Vel, først skal vi dynamisk tildele plass for en ny SLL node, så vi malloc-- det er en visuell representasjon av noden vi nettopp opprettet. Og vi må du kontrollere det er ikke null-- i dette tilfellet, bildet ville ikke ha vist seg hvis det var null, vi ville ha gått tom for minne, så vi er godt å gå dit. Så nå er vi videre til trinn C, initialisere noder verdifeltet. Vel, basert på denne funksjonen kaller jeg bruker her, ser ut som jeg ønsker å passere på 6, Så jeg skal seks i verdifeltet. Nå initial neste felt. Vel, hva skal jeg gjøre der, det er ingenting ved siden, høyre, dette er den eneste på listen. Så hva er det neste på listen? 

Det bør ikke peke på noe, ikke sant. Det er ingenting annet der, så hva er konseptet vi vet om som er nothing-- pekere til ingenting? Det bør være kanskje vi ønsker å sette en nullpeker der, og jeg skal representere null pekeren som bare en rød boks, vi kan ikke gå videre. Som vi skal se litt senere, vi vil ha slutt kjeder piler koble disse nodene sammen, men når du treffer røde boksen, det er null, vi kan ikke gå videre, det er slutten av listen. 

Og til slutt, vi ønsker bare å returnere en peker til denne noden. Så vi vil kalle det nye, og vil returnere nytt slik at den kan brukes i uansett funksjon opprettet den. Så det vi går, Vi har laget en enkeltvis lenket liste node ut av løse luften, og nå har vi en liste vi kan jobbe med. 

Nå, la oss si at vi allerede har en stor kjede, og vi ønsker å finne noe i det. Og vi vil ha en funksjon som kommer å returnere sant eller usant, avhengig om hvorvidt en verdi eksisterer i den listen. En funksjon prototype, eller erklæringen for denne funksjonen, kan se ut som dette-- bool finne, og så vi ønsker å passere på to argumenter. 

Den første er en peker til første elementet i lenket liste. Dette er faktisk noe du vil alltid ønsker å holde styr på, og faktisk kan være noe som du selv satt i en global variabel. Når du oppretter en liste, du alltid, alltid ønsker å holde styr på de aller første elementet på listen. På den måten kan du referere til alle de andre elementer ved bare å følge kjeden, uten å måtte holde pekere intakt til hvert enkelt element. Du trenger bare å holde styr på den første en hvis de er alle lenket sammen. 

Og deretter den andre tingen vi kjører i gang er vilkårlig some-- uansett datatype vi er leter etter det er innsiden av forhåpentligvis en av nodene i listen. Så hva er fremgangsmåten? Vel, er det første vi gjør vi skape en tverrgående peker og peker på listene hodet. Vel, hvorfor skal vi gjøre det vi allerede har en peker på listene hodet, hvorfor ikke vi bare flytte den rundt? Vel, som jeg sa, det er veldig viktig for oss å alltid holde styr på aller første element i listen. Og så det er faktisk bedre for å lage en kopi av det, og bruke den til å bevege seg rundt så vi aldri uhell bevege seg bort, eller vi alltid har en peker på et punkt som ligger rett på det første elementet på listen. Så det er bedre å lage en andre en som vi bruker til å bevege seg. 

Så vi bare sammenligne hvorvidt verdifeltet på den noden er det vi leter etter, og hvis det er ikke, vi bare flytte til neste node. Og vi fortsette med det over, og over og over, før vi enten finne elementet, eller vi treffer null-- vi har nådd slutten av listen, og det er ikke der. Dette bør forhåpentligvis ringe en bjelle til deg som bare lineær søk, vi bare replikere den i en enkeltvis lenket liste struktur stedet for å bruke en matrise for å gjøre det. 

Så her er et eksempel på en enkeltvis lenket liste. Denne består av fem noder, og vi har en peker til leder av liste, som kalles listen. Det første vi vil gjøre er å igjen, lage, at traversering pekeren. Så vi har nå to pekere som peker til det samme. 

Legg nå merke til her også, jeg gjorde ikke må malloc noen plass for trav. Jeg sa ikke trav lik malloc noe, allerede eksisterer som node, at plass i minnet finnes allerede. Så alt jeg egentlig gjør er å skape et annet peker til den. Jeg er ikke mallocing en ekstra plass, må bare nå to pekere peker på det samme. 

Så er to hva jeg leter etter? Vel, nei, så i stedet jeg er kommer til å flytte til den neste. Så i utgangspunktet vil jeg si, trav tilsvarer trav neste. Er tre det jeg leter etter, nei. Så jeg fortsetter å gå gjennom, inntil eventuelt komme til 6 som er hva jeg ser basert på beregnet funksjon samtale Jeg har på toppen der, og så er jeg ferdig. 

Nå, hva om elementet jeg er leter etter er ikke i listen, er det fortsatt kommer til å fungere? Vel, legge merke til at listen her er litt forskjellig, og dette er en annen ting som er viktig med koblede lister, du trenger ikke å bevare dem i en bestemt rekkefølge. Du kan hvis du vil, men du har kanskje allerede lagt merke til at vi ikke holde styr på hva antall element vi er på. 

Og det er liksom en handel som vi har med lenket liste vers arrays, det har vi ikke random access lenger. Vi kan ikke bare si, jeg vil ha å gå til 0. element, eller den sjette element av min array, som jeg kan gjøre i en matrise. Jeg kan ikke si at jeg ønsker å gå til 0. element, eller det sjette element, eller den 25. element av min lenket liste, det er ingen indeks knyttet til dem. Og slik er det ikke virkelig betyr noe hvis vi bevare vår liste i orden. Hvis du vil kan du sikkert kan, men det er ingen grunn til at de trenger å bli bevart i den rekkefølgen. Så igjen, la oss prøve og finne 6 i denne listen. Vel, vi begynner på begynner, finner vi ikke seks, og da har vi ikke fortsette å finne 6, før vi til slutt får til her. Så akkurat nå trav peker til noden inneholder åtte, og seks er ikke der. 

Så neste skritt vil være for å gå til neste pekeren, så si trav tilsvarer trav neste. Vel, trav neste, angitt med den røde boksen der, er null. Så det er ikke noe annet å gå, og så på dette punktet Vi kan konkludere med at vi har nådd enden av lenket liste, og 6 er ikke i der. Og det ville bli returnert falsk i dette tilfellet. 

OK, hvordan setter vi en ny node inn i lenket liste? Så vi har vært i stand til å skape en lenket liste ut av ingenting, men vi sannsynligvis vil bygge opp en kjede og ikke skape en haug med forskjellige lister. Vi ønsker å ha en liste som har en haug med noder i det, ikke en haug med lister med én node. Så vi kan ikke bare fortsette å bruke Lag funksjon vi definert tidligere, nå er vi ønsker å sette inn en liste som allerede eksisterer. 

Så dette tilfellet, skal vi å passere i to argumenter, pekeren til leder av det lenket liste som vi ønsker å legge til. Igjen, det er derfor det er så viktig at vi alltid holde orden på det, fordi det er den eneste måten vi virkelig nødt til å referere til hele listen er bare ved en peker til det første elementet. Så vi ønsker å passere i en Peker til det første elementet, og hva verdien vi ønsker å legge til i listen. Og til slutt denne funksjonen kommer til å returnere en peker til den nye sjefen for en lenket liste. 

Hva er fremgangsmåten involvert her? Vel, akkurat som med opprette, vi trenger å dynamisk allokere plass til en ny node, og kontroller sikker på at vi ikke går tom for minne, på nytt, fordi vi bruker malloc. Så vi ønsker å fylle og sette inn node, så sette tall, uansett val er, inn i noden. Vi ønsker å sette noden på begynnelsen av lenket liste. 

Det er en grunn til at jeg ønsker å gjøre dette, og det kan være verdt å ta en andre til pause videoen her, og tenke på hvorfor jeg ønsker å Sett i begynnelsen av en koblet listen. Igjen, jeg nevnte tidligere at det gjør egentlig ikke rolle om vi bevare det på noen rekkefølge, så kanskje det er en anelse. Og du så hva som ville skje hvis vi ønsket to-- eller fra bare et sekund siden da vi skulle gjennom søk deg kunne se hva som kan skje hvis vi prøvde for å sette inn i enden av listen. Fordi vi ikke har et pekeren til enden av listen. 

Så grunnen til at jeg ønsker å sette i begynnelsen, er fordi jeg kan gjøre det umiddelbart. Jeg har en peker i begynnelsen, og vi vil se dette i et visuelt i et sekund. Men hvis jeg ønsker å sette inn på slutten, Jeg må begynne på begynnelsen, traversere hele veien til den enden, og deretter slår den på. Slik det ville bety at innsetting i enden av listen ville bli en o n drift, kommer tilbake til vår diskusjon av beregningsorientert kompleksitet. Det ville blitt en o n operasjon, der som listen ble større og større, og større, vil det bli mer og vanskeligere å tråkle noe på i enden. Men det er alltid veldig lett å tack noe på i begynnelsen, du er alltid i begynnelsen. 

Og vi vil se en visuell av dette igjen. Og så når vi er ferdig, en gang Vi har satt inn ny node, vi ønsker å gå tilbake til vår pekeren til den nye sjefen for en lenket liste, som siden vi setter på begynner, faktisk vil være en peker til noden vi nettopp opprettet. La oss visualisere dette, fordi jeg tror det vil hjelpe. 

Så her er vår liste, den består av fire elementer, en node som inneholder 15, som peker til en node inneholdende 9, hvilken peker til en node som inneholder 13, som peker til en node som inneholder 10, som har null pekeren som sin neste pekeren så det er slutten av listen. Så vi ønsker å sette inn et ny node med verdien 12 i begynnelsen av denne liste, hva gjør vi? Vel, først vi malloc plass for node, og da vi satt 12 i det. 

Så nå har vi nådd en beslutningspunkt, ikke sant? Vi har et par tips som vi kunne bevege seg, som man bør vi flytte først? Skal vi lage 12 poeng å den nye sjefen for list-- eller unnskylde meg, bør vi gjøre 12 peke på den gamle hodet av listen? Eller skal vi si at Listen begynner nå på 12. Det er en forskjell der, og vi vil se på hva som skjer med begge i en andre. 

Men dette fører til en stort tema for sidebar, som er at en av de vanskeligste ting med lenkede lister er å ordne pekere i riktig rekkefølge. Hvis du flytter ting i rekkefølge, du kan ende opp ved et uhell orphaning resten av listen. Og her er et eksempel på det. Så la oss gå med ideen of-- vel, vi har nettopp opprettet 12. Vi vet 12 kommer til å bli ny leder av listen, og så hvorfor ikke vi bare flytte listen pekeren til å peke der. 

OK, så det er bra. Så nå hvor kommer 12 neste punkt? Jeg mener, visuelt vi kan se at den vil peke til 15, som mennesker det er veldig tydelig for oss. Hvordan datamaskinen vet? Vi har ikke noe pekte på 15 lenger, ikke sant? 

Vi har mistet noen mulighet til å referere til 15. Vi kan ikke si ny pilen ved equals noe, det er ingenting der. Faktisk har vi foreldreløs resten av listen ved å gjøre det, vi har brutt ved et uhell kjeden. Og vi absolutt ikke ønsker å gjøre det. 

Så la oss gå tilbake og prøve dette igjen. Kanskje den riktige tingen å gjøre er å sette 12 neste pekeren til den gamle hodet av listen først, da kan vi flytte listen over. Og i virkeligheten er at riktig rekkefølge som vi må følge når vi er jobbe med enkeltvis lenket liste. Vi ønsker alltid å koble nytt element i listen før vi tar den slags viktig skritt for å endre der leder av lenket liste er. Igjen, det er en så grunnleggende ting, vi ønsker ikke å miste oversikten over det. 

Så vi ønsker å være sikker på at alt er lenket sammen, før vi flytter at pekeren. Og så dette ville være riktig rekkefølge, som er til å koble 12 til listen, så si at listen starter en 12. Hvis vi sa listen starter på 12 og så forsøkt å koble 12 til listen, vi har allerede sett hva som skjer. Vi mister listen ved en feiltakelse. 

OK, så en ting å snakke om. Hva hvis vi ønsker å bli kvitt en hel lenket liste på en gang? Igjen, vi mallocing all denne plassen, og så vi trenger å frigjøre det når vi er ferdige. Så nå ønsker vi å slette hele lenket liste. Vel, hva vi ønsker å gjøre? 

Hvis vi har nådd nullpeker, vi ønsker å stoppe, ellers bare slette resten av listen og deretter frigjøre meg. Sletter resten av listen, og deretter frigjøre gjeldende node. Hva høres dette ut som, hva teknikken har vi snakket om tidligere høres det ut? Slett alle andre, så komme tilbake og slette meg. 

Det er rekursjon, har vi gjort problemet litt mindre, vi sier slette alle annet, så kan du slette meg. Og lenger ned i veien, som node vil si, slette alle andre. Men til slutt vil vi komme til punkt hvor listen er null, og det er vår base case. 

Så la oss ta en titt på denne, og hvordan dette kan fungere. Så her er vår liste, er det det samme lister vi var bare snakker om, og det er trinnene. Det er mye tekst her, men forhåpentligvis visualisering vil hjelpe. 

Så vi have-- og jeg har også trukket opp vår stack rammer illustrasjon fra vår video på anrops stabler, og forhåpentligvis all denne sammen vil vise deg hva som skjer. Så her er vår pseudokode. Hvis vi nå en null pekeren, stoppe, ellers sletter resten av listen, deretter frigjøre gjeldende node. Så akkurat nå, list-- pekeren at vi er bestått i å ødelegge poeng til 12. 12 er ikke en nullpeker, så vi er kommer til å slette resten av listen. 

Hva er å slette Resten av oss som er involvert? Vel, det betyr å gjøre en ringe for å ødelegge, sier 15 som er begynnelsen av Resten av listen vi ønsker å ødelegge. Og så kallet til å ødelegge 12 er litt på vent. Det er frosset der, venter på ringe for å ødelegge 15, for å fullføre jobben sin. 

Vel, er 15 ikke en nullpeker, og så det kommer til å si, all right, vel, slette resten av listen. Resten av listen starter på 9, og så får vi bare vent til du sletter alt som ting, så komme tilbake og slette meg. Vel ni kommer til å si, vel, Jeg er ikke en nullpeker, så sletter resten listen herfra. Og så prøve og ødelegge 13. 13 sier: Jeg er ikke nullpeker, samme, går det the buck. 10 er ikke nullpeker, 10 inneholder en nullpeker, men 10 er ikke i seg selv en nullpeker akkurat nå, og så den passerer the buck også. 

Og nå liste poeng der, det virkelig vil peke på some-- hvis jeg hadde mer plass i bildet, det ville peke på noen tilfeldig plass at vi ikke vet hva det er. Det er nullpeker skjønt, listen er bokstavelig talt nå satt det verdier null. Det peker rett på innsiden som rød boks. Vi nådde en nullpeker, så vi kan stoppe, og vi er ferdige. 

Og slik at lilla ramme er now-- på toppen av stack-- som er den aktive rammen, men det er gjort. Hvis vi har nådd en nullpeker, stopp. Vi gjør ikke noe, vi kan ikke frigjøre en nullpeker, vi ikke malloc noen plass, og så er vi ferdige. Slik at funksjonsramme er ødelagt, og vi resume-- vi fortsette der vi forlot med det nest høyeste ene, som er denne mørke blå ramme her. Så vi plukke opp akkurat der vi slapp. Vi fjernet resten av liste allerede, så nå er vi kommer til å frigjøre de nåværende noder. Så nå kan vi frigjøre denne noden, og nå Vi har nådd slutten av funksjonen. Og slik at funksjonsramme er ødelagt, og vi plukke opp på den lyseblå en. 

Så det says-- jeg allerede har done-- sletting resten av listen, så frigjøre nåværende node. Og nå den gule rammen er tilbake på toppen av bunken. Og slik som du ser, er vi nå ødelegge listen fra høyre til venstre. 

Hva ville ha skjedd, skjønt, hvis vi hadde gjort ting på feil måte? Akkurat som da vi prøvde å legge til et element. Hvis vi messed opp kjeden, hvis vi ikke koble pekere i riktig rekkefølge, hvis vi bare frigjort det første elementet, hvis vi bare frigjort leder av listen, nå er vi har ingen mulighet til å referere til resten av listen. Og så ville vi ha foreldreløs alt, vi ville ha hatt det som er kalt en minnelekkasje. Hvis du husker fra vår video på dynamisk minne allokering, det er ikke veldig bra. 

Så som jeg sa, det er flere operasjoner at vi trenger å bruke for å jobbe med lenket liste effektivt. Og du har kanskje merket jeg utelatt en, slette en enkelt element fra en tilkoblet listen. Grunnen til at jeg gjorde det er det er faktisk slags vanskelig å tenke på hvordan du sletter et enkelt element fra en enkeltvis lenket liste. Vi må være i stand til å hoppe over noe på listen, som betyr at vi får til en point-- vi vil slette denne node-- men for å gjøre det slik vi ikke mister noe informasjon, vi trenger å koble dette node over her, her. 

Så jeg sannsynligvis gjorde det galt fra et visuelt perspektiv. Så vi er i begynnelsen av vår liste, vi går gjennom, vi vil slette denne noden. Hvis vi bare slette den, vi har brutt kjeden. Denne noden her refererer til alt annet, den inneholder kjeden fra her på ut. 

Så det vi trenger å gjøre faktisk etter at vi kommer til dette punktet, er vi trenger å gå tilbake ett, og koble denne noden over til denne node, slik at vi kan deretter slette den i midten. Men enkeltvis lenkede lister ikke gi oss en vei å gå bakover. Så vi må enten holde to pekere, og flytte dem slags off trinn, en bak andre mens vi går, eller kommer til et punkt og deretter sende en annen pekeren gjennom. Og som du kan se, det kan bli litt rotete. Heldigvis har vi en annen måte å løse det, når vi snakker om dobbelt lenkede lister. 

Jeg er Doug Lloyd, dette er CS50.