>> [Musik spiller]
>> DOUG Lloyd: OK, så på dette punkt i løbet,
Vi har dækket en masse af det grundlæggende i C. Vi ved en masse om variabler, arrays,
pegepinde, alt, gode ting.
De er alle slags bygget i at se som de grundlæggende,
men vi kan gøre mere, ikke?
Vi kan kombinere tingene sammen på interessante måder.
>> Og så lad os gøre det, lad os starte at forgrene ud af det C giver os,
og begynde at skabe vores egne data strukturer ved hjælp disse bygning
blokke sammen for at gøre noget virkelig værdifulde, nyttige.
En måde vi kan gøre dette er at tale om samlinger.
Så indtil videre har vi haft en slags data struktur til at repræsentere samlinger
af lide værdier, lignende værdier.
Det ville være et array.
Vi har samlinger af heltal eller samlinger af tegn og så videre.
>> Strukturer er også sortere i en data struktur til indsamling af oplysninger,
men det er ikke til opsamling som værdier.
Det er normalt blander forskellige datatyper sammen inde i en enkelt kasse.
Men det er ikke i sig selv anvendes til at kæde sammen
eller tilslut sammen lignende elementer, ligesom et array.
Arrays er stor for element se op, men tilbagekaldelse
at det er meget vanskeligt at indsætte i et array,
medmindre vi indsætter på allersidst i denne array.
>> Og det bedste eksempel jeg har for det er insertion slags.
Hvis du husker vores video ved indsættelse sortere,
der var en masse udgift involveret i at have
at afhente elementer, og skift dem af vejen til at passe noget
ind i midten af ​​dit array.
Arrays også lider af en anden problem, hvilket er manglende fleksibilitet.
Når vi erklære et array, vi får et skud på det.
Vi får at sige, jeg vil dette mange elementer.
Kan være 100, det måske være 1,000, kan det
være x hvor x er et tal, som brugeren gav os på en prompt eller på kommando
linje.
>> Men vi får kun ét skud på det, vi ikke komme til at så sige åh, faktisk jeg
havde brug for 101, eller jeg havde brug for x plus 20.
For sent, har vi allerede erklæret array, og hvis vi ønsker at få 101 eller x
plus 20, er vi nødt til at erklære en helt anden matrix,
kopiere alle elementer i array overstået, og så vi har nok.
Og hvad hvis vi tager fejl igen, hvad hvis vi rent faktisk har brug 102 eller x plus 40,
vi er nødt til at gøre det igen.
Så de er meget ufleksibel til resizing vores data,
men hvis vi kombinerer sammen nogle af det grundlæggende, at vi har allerede
lært om pegepinde og strukturer, især ved hjælp af dynamisk hukommelse
fordeling med malloc, vi kan sætte disse stykker sammen
at oprette en ny data structure-- en enkeltvis sammenkædet liste vi måske say--
der giver os mulighed for at vokse og skrumpe en samling værdier
og vi vil ikke have nogen spildplads.
>> Så igen, kalder vi denne idé, dette begreb, en sammenkædet liste.
Især vi i denne video er taler om enkeltvis linket liste,
og derefter en anden video, vi vil tale omkring dobbelt hægtede lister, som
er blot en variation på et tema her.
Men en enkelt bundet liste består af knudepunkter,
noder blot at være en abstrakt term-- det er bare noget, jeg ringer
det er en slags struktur, dybest set, jeg er?
Bare at kalde det en node-- og dette knude har to medlemmer, eller to felter.
Det har data, som regel en heltal, et tegn float,
eller kan være en anden datatype at du har defineret med en type def.
Og den indeholder en pointer til en anden node af samme type.
>> Så vi har to ting indersiden af dette knudepunkt, data og en pointer
til et andet knudepunkt.
Og hvis du begynder at visualisere dette, kan du tænke over det
som en kæde af knudepunkter, er forbundet med hinanden.
Vi har det første knudepunkt, det indeholder data, og en pegepind
til det andet knudepunkt, som indeholder data, og en pegepind til den tredje knudepunkt.
Og så det er derfor, vi kalder det en linkede liste, de er bundet sammen.
>> Hvad betyder dette særlige node struktur se ud?
Tja, hvis du husker fra vores video på definere brugerdefinerede typer, med type def,
Vi kan definere en structure-- og skriv definere en struktur som denne.
tyepdef struct sllist, og så er jeg bruge ordet værdi her vilkårligt
at angive, hvilke datatype rigtig.
Du kunne videregive et heltal eller flyde, du kunne have hvad du vil.
Det er ikke begrænset til blot heltal, eller noget lignende.
Så værdi er blot en vilkårlig datatype, og derefter en pointer
til en anden node af samme type.
>> Nu, der er en lille fangst her med at definere en struktur
når det er en selv referentiel struktur.
Jeg er nødt til at have en midlertidig navn til min struktur.
I slutningen af ​​den dag, jeg klart vil kalde det
SLL node, det er i sidste ende den nye nævne en del af min type definition
men jeg kan ikke bruge SLL node i midten af ​​dette.
Årsagen er, har jeg ikke skabte en type kaldet SLL node
indtil jeg ramt dette sidste punkt her.
Indtil dette punkt, jeg er nødt til at have en anden måde at henvise til denne datatype.
>> Og det er en selvstændig referentiel datatype.
Det; s en datatype af et struktur, der indeholder en database,
og en pointer til en anden struktur af samme type.
Så jeg har brug for at være i stand til at henvise til denne datatype i det mindste midlertidigt,
så giver det en midlertidig navn struct sllist
tillader mig at så siger jeg vil have en pointer til en anden struct sllist,
en struct sllist stjerne, og derefter efter at jeg har gennemført definitionen,
Jeg kan nu kalde denne type en SLL node.
>> Så det er derfor du se, at der er en midlertidig navn her,
men en permanent navn her.
Nogle gange vil du måske se definitioner af strukturen,
for eksempel, som ikke er selv referentiel, at
ikke har en specifier navn her.
Det ville bare sige typedef struct, åbne krøllede klammeparentes og derefter definere det.
Men hvis du er struct er self referentiel, som dette er,
skal du angive en midlertidig typen navn.
Men i sidste ende, nu at vi har gjort dette,
Vi kan bare henvise til disse knudepunkter, disse enheder,
som SLL noder til formål, af resten af ​​denne video.
>> Okay, så vi ved, hvordan man oprette en sammenkædet liste node.
Vi ved, hvordan man definerer en sammenkædet liste node.
Nu, hvis vi kommer til at starte bruge dem til at indsamle oplysninger,
der er et par af operationer, vi nødt til at forstå og arbejde med.
Vi har brug for at vide, hvordan man skaber en sammenkædet liste ud af den blå luft.
Hvis der ikke er nogen liste allerede, Vi ønsker at starte en.
Så vi skal være i stand at oprette en sammenkædet liste,
vi nødt til sandsynligvis søge via linket listen
for at finde et element, vi leder efter.
Vi skal være i stand til at indsætte nye ting ind i listen,
vi ønsker vores liste til at kunne vokse.
Og på samme måde, vi ønsker at kunne at slette ting fra vores liste,
Vi ønsker, at vores liste at være i stand til at skrumpe.
Og ved slutningen af ​​vores programmer, især
hvis du husker, at vi er dynamisk allokering hukommelse
at opbygge disse lister typisk vi ønsker at befri alle, at hukommelsen
når vi er færdige arbejder med det.
Og så skal vi være i stand til at slette et Hele linket liste på én mislykkes razzia.
Så lad os gå igennem nogle af disse operationer
og hvordan vi kan visualisere dem, taler i pseudokode kode specifikt.
Så vi ønsker at skabe en linkede liste, så måske vi
ønsker at definere en funktion med denne prototype.
SLL node stjerne, oprette, og jeg passerer i et argument, nogle vilkårlige data
skriv igen, af en eller anden vilkårlig datatype.
Men jeg returning-- denne funktion skal tilbage til mig en pointer til en enkeltvis
sammenkædet liste node.
Igen, vi forsøger at skabe en sammenkædet liste ud af den blå luft,
så jeg har brug for en pointer til denne liste, når jeg er færdig.
>> Så hvad er de skridt, der er involveret her?
Nå, første ting jeg kommer til at gøre, er dynamisk
allokere plads til en ny node.
Igen, vi skaber det ud af den blå luft, så vi er nødt til at malloc plads til det.
Og naturligvis straks efter vi malloc,
vi altid tjekke for at sikre, at vores pointer-- vi ikke fik tilbage null.
For hvis vi forsøger og ærbødighed en null-pointer,
vi kommer til at lide en segmenteringsfejl og vi vil ikke have det.
>> Så vi ønsker at udfylde feltet, vi ønsker at initialisere værdien feltet
og initialisere næste felt.
Og så ønsker vi at-- sidst som funktion prototype indicates-- vi ønsker
at returnere en pegepind til en SLL node.
Så hvad gør denne ligne visuelt?
Nå, først vi vil dynamisk allokere plads til en ny SLL node,
så vi malloc-- der er en visuel repræsentation
knudens vi lige har oprettet.
Og vi skal du kontrollere det er ikke null-- i denne sag,
billedet vil ikke vist op, hvis det var null,
vi ville have løbe tør for hukommelse, så vi er godt at gå der.
Så nu er vi til trin C, initialisere knudepunkter værdien felt.
Nå, der er baseret på denne funktion kalder Jeg bruger her,
ser ud som jeg ønsker at passere i 6, Så jeg vil 6 i værdifeltet.
Nu initialisere det næste felt.
Nå, hvad skal jeg gøre der, der er intet næste, højre,
dette er det eneste i listen.
Så hvad er den næste ting på listen?
>> Det bør ikke pege på noget, højre.
Der er ikke noget andet der, så hvad er begrebet vi kender, der er nothing--
pegepinde til ingenting?
Det bør være måske vi ønsker at sætte en null-pointer der,
og jeg vil repræsentere null pointer som bare en rød boks,
Vi kan ikke gå længere.
Som vi vil se lidt senere, vi vil have i sidste ende kæder
af pile forbinder disse knudepunkter sammen,
men når du rammer røde felt, det er null,
Vi kan ikke gå videre, det er slutningen af ​​listen.
>> Og endelig, vi ønsker blot at returnere en pegepind til denne knude.
Så vi vil kalde det nye, og vil vende tilbage ny
så den kan anvendes i uanset hvilken funktion skabte det.
Så der går vi, vi har oprettet en enkeltvis sammenkædet liste node ud af den blå luft,
og nu har vi en liste, vi kan arbejde med.
>> Lad os nu sige, at vi allerede har en stor kæde,
og vi ønsker at finde noget i det.
Og vi vil have en funktion, der kommer at returnere sand eller falsk, afhængigt
om, hvorvidt en værdi findes i denne liste.
En funktion prototype eller erklæring for denne funktion,
kan se ud som denne-- bool finde, og så vi ønsker at passere i to argumenter.
>> Det første, er en pointer til første element i den linkede liste.
Det er faktisk noget, du vil altid ønsker at holde styr på,
og faktisk kunne være noget, du endda sat i en global variabel.
Når du opretter en liste, du altid, altid
ønsker at holde styr på de meget første element på listen.
På den måde kan du henvise til alle de andre elementer af lige efter kæden,
uden at skulle holde pointers intakt til hver enkelt element.
Du behøver kun at holde styr på den første en, hvis de er alle lænket sammen.
>> Og så den anden ting vi passerer igen
er vilkårligt some-- uanset hvilken datatype er vi
søger der er inde i forhåbentlig et af knudepunkterne på listen.
Så hvad er de skridt?
Nå, den første ting, vi gør, er skaber vi en tværgående pointer
peger på listerne hoved.
Tja, hvorfor gør vi det, vi allerede har en pointer på lister hovedet,
hvorfor vi ikke bare flytte, at man rundt?
Tja, som jeg lige har sagt, det er virkelig vigtigt for os
for altid at holde styr på allerførste element i listen.
Og så er det faktisk bedre at oprette en kopi af denne,
og bruge den til at bevæge sig rundt, så vi aldrig uheld bevæge sig væk, eller vi altid
har en pointer på et tidspunkt, der er lige på det første element på listen.
Så det er bedre at skabe en anden en, som vi bruger til at flytte.
>> Så vi bare sammenligne, om feltet på denne node værdi
er det, vi leder efter, og hvis det er ikke, vi bare gå videre til næste node.
Og vi holde gør, at i og over og over,
indtil vi enten finder elementet, eller vi ramt
null-- vi har nået slutningen af listen, og det er ikke der.
Dette skulle forhåbentlig ringer en klokke til dig som bare lineær søgning,
vi bare replikere det i en enkelt bundet listestruktur
stedet for at bruge et array til at gøre det.
>> Så her er et eksempel på en enkelt bundet listen.
Denne ene består af fem knuder, og vi har
en pointer til lederen af liste, som kaldes listen.
Den første ting, vi ønsker at gøre, er igen, skabe den traversal pointer.
Så vi har nu to pejlemærker der peger på det samme.
>> Nu bemærke her også, jeg ikke nødt til at allokere nogen plads til trav.
Jeg sagde ikke trav lig malloc noget, der allerede findes, at node,
at rummet i hukommelsen findes allerede.
Så alt jeg faktisk gør, er skabe en anden pointer til det.
Jeg er ikke mallocing en ekstra plads, bare har nu to pejlemærker
peger på det samme.
>> Så er 2, hvad jeg leder efter?
Nå, nej, så i stedet er jeg kommer til at flytte til den næste.
Så dybest set vil jeg sige, trav lig trav næste.
Er 3 hvad jeg leder efter, nej.
Så jeg fortsætter med at gå igennem, indtil til sidst
komme til 6, som er hvad jeg søger for baseret på funktionen opkald
Jeg har i toppen der, og så jeg er færdig.
>> Nu, hvad hvis elementet er jeg leder efter, er ikke på listen,
er det stadig kommer til at arbejde?
Nå, bemærke, at listen her er subtilt anderledes,
og det er en anden ting, der er vigtigt med hægtede lister,
du behøver ikke at bevare dem i nogen bestemt rækkefølge.
Du kan hvis du vil, men du måske allerede har bemærket
at vi ikke holde styr på hvad nummer element, vi er på.
>> Og det er slags en handel, som vi har med linket liste vers arrays,
er det vi ikke har random access længere.
Vi kan ikke bare sige, jeg ønsker at gå til 0. element,
eller 6. element i mit array, som jeg kan gøre i et array.
Jeg kan ikke sige jeg ønsker at gå til 0. element, eller 6. element,
eller 25 element min sammenkædet liste, der er ingen indeks forbundet med dem.
Og så det er ligegyldigt virkelig hvis vi bevarer vores liste i orden.
Hvis du ønsker at du sikkert kan, men der er
ingen grund til de skal bevares i vilkårlig rækkefølge.
Så igen, lad os prøve og finde 6 på denne liste.
Nå, vi starter på begynder, vi ikke finde 6,
og derefter fortsætte vi ikke at finde 6, indtil vi til sidst kommer til her.
Så lige nu Trav peger på noden indeholdende 8, og seks er ikke derinde.
>> Så næste skridt ville være at gå til det næste pointer,
så siger trav lig trav næste.
Nå, trav næste, angives med det røde felt der, er null.
Så der er ingen andre steder at gå, og så på dette punkt
Vi kan konkludere, at vi har nået slutningen af ​​linkede liste,
og 6 er ikke derinde.
Og det ville blive returneret falsk i dette tilfælde.
>> OK, hvordan kan vi indsætte en ny knude i den linkede liste?
Så vi har været i stand til at skabe en sammenkædet liste ud af ingenting,
men vi sikkert gerne opbygge en kæde og ikke
skabe en masse forskellige lister.
Vi ønsker at have en liste, har en masse knuder i det,
ikke en flok lister med en enkelt node.
Så vi kan ikke bare fortsætte med at bruge Opret funktion vi defineret tidligere, nu er vi
ønsker at indsætte i en liste, der allerede eksisterer.
>> Så dette tilfælde vil vi at passere i to argumenter,
markøren til lederen af ​​det linkede liste, som vi ønsker at føje til.
Igen, det er derfor det er så vigtigt, at vi altid
holde styr på det, fordi det er den eneste måde, vi virkelig
nødt til at henvise til hele listen er blot ved en pointer til det første element.
Så vi ønsker at passere i en Markøren til denne første element,
og uanset værdi, vi ønsker at tilføje til listen.
Og til sidst denne funktion kommer til at vende tilbage en pegepind
til den nye leder af en linket liste.
>> Hvad er de skridt, der er involveret her?
Nå, ligesom med skabe, vi er nødt til dynamisk allokere
plads til en ny node, og tjek at gøre sikker på at vi ikke løber tør for hukommelse, igen,
fordi vi bruger malloc.
Så vi ønsker at befolke og indsæt node,
så sætter antallet, uanset val er, ind i knuden.
Vi ønsker at indsætte noden på begyndelsen af ​​linkede liste.
>> Der er en grund til, at jeg ønsker at gøre dette, og det
kunne være værd at tage et andet at holde pause i videoen her,
og tænke over, hvorfor jeg ønsker at indsætte ved begyndelsen af ​​en sammenkædet
listen.
Igen, jeg nævnte tidligere at det egentlig ikke
noget, hvis vi bevarer det på nogen orden, så måske det er et fingerpeg.
Og du så, hvad der ville ske, hvis vi ønskede at-- eller fra blot et sekund
siden, da vi skulle gennem søgning, du
kunne se, hvad der kunne ske, hvis vi forsøgte
at indsætte i slutningen af ​​listen.
Fordi vi ikke har en pointer til slutningen af ​​listen.
>> Så grunden til, at jeg ønsker at indsætte i begyndelsen,
er fordi jeg kan gøre det samme.
Jeg har en pointer i starten, og vi vil se det i en visuel i en anden.
Men hvis jeg ønsker at indsætte i slutningen, Jeg er nødt til at starte ved begyndelsen,
krydse hele vejen til ende, og derefter tack det på.
Så det ville betyde, at indsættelse i slutningen af ​​listen
ville blive en o n operation, som går tilbage
til vores diskussion af beregningsmæssige kompleksitet.
Det ville blive en o n operation, hvor som listen blev større, og større,
og større, vil det blive mere og vanskeligere at hæfte noget
ankomsttidspunktet ved afslutningen.
Men det er altid virkelig nemt at tack noget på i starten,
du er altid i begyndelsen.
>> Og vi vil se en visuel af denne igen.
Og så når vi er færdig, når Vi har indsat den nye node,
vi ønsker at returnere vores pointer til den nye leder af en linket liste, som
da vi indsætter på begynder, vil faktisk være
en pointer til det knudepunkt, vi lige har oprettet.
Lad os forestille sig dette, fordi jeg tror, ​​det vil hjælpe.
>> Så her er vores liste, den består af fire elementer, et knudepunkt indeholdende 15,
hvilket tyder på en node indeholdende 9, som
peger på en node, der indeholder 13, hvilket tyder på en node, der indeholder
10, som har nul pointer som sin næste pointer
så det er i slutningen af ​​listen.
Så vi ønsker at indsætte en ny knude med værdien 12
i begyndelsen af ​​denne liste, hvad gør vi?
Nå, først vi malloc plads til knude, og så sætter vi 12 derinde.
>> Så nu har vi nået en beslutning punkt, højre?
Vi har et par pejlemærker, som vi kunne
flytte, som man bør vi flytter først?
Skal vi lave 12 point til den nye leder af list--
eller undskyld, bør vi gøre 12 pege på den gamle leder af listen?
Eller skal vi sige, at den Listen begynder nu på 12.
Der er en forskel der, og vi vil se
hvad der sker med både i en anden.
>> Men dette fører til en store emne for sidebar,
som er, at en af ​​de vanskeligste ting med hægtede lister
er at arrangere pointers i den rigtige rækkefølge.
Hvis du flytter tingene i orden, du kan ende op ved et uheld
forældreløse resten af ​​listen.
Og her er et eksempel på det.
Så lad os gå med tanken of-- godt, vi har lige har oprettet 12.
Vi ved 12 vil være den nye leder af listen,
og så hvorfor ikke vi bare flytte listen pointer til at pege der.
>> OK, så det er godt.
Så nu hvor gør 12 næste punkt?
Jeg mener, visuelt kan vi se at det vil pege på 15,
som mennesker er det virkelig klart for os.
Hvordan computeren kender?
Vi har ikke noget peger på 15 længere, vel?
>> Vi har mistet enhver evne til at henvise til 15.
Vi kan ikke sige ny pil ved siden ligemænd noget, der er ikke noget der.
Faktisk har vi forældreløse resten af ​​listen
ved at gøre det, vi har uheld brudt kæden.
Og vi bestemt ikke ønsker at gøre det.
>> Så lad os gå tilbage og prøve dette igen.
Måske det rigtige at gøre er at sætte 12 næste pointer
til den gamle leder af listen først, så kan vi flytte listen igen.
Og i virkeligheden, dvs. rigtige rækkefølge at vi
nødt til at følge, når vi er arbejder med enkelt bundet listen.
Vi ønsker altid at tilslutte nyt element i listen,
før vi tager den slags vigtigt skridt for at ændre
hvor lederen af ​​den linkede liste er.
Igen, det er sådan en grundlæggende ting, Vi ønsker ikke at miste overblikket over det.
>> Så vi ønsker at sikre, at alt er lænket sammen,
før vi går, at markøren.
Og så det ville være den rigtige rækkefølge, som er at forbinde 12 til listen,
så sige, at listen starter en 12.
Hvis vi sagde listen starter ved 12 og derefter forsøgte at forbinde 12 til listen,
Vi har allerede set, hvad der sker.
Vi mister listen ved en fejltagelse.
>> OK, så en ting mere at tale om.
Hvad nu, hvis vi ønsker at slippe af med en hel linkede liste på én gang?
Igen, vi mallocing alt dette rum, og så vi
brug for at frigøre det, når vi er færdig.
Så nu er vi ønsker at slette hele linkede liste.
Nå, hvad ønsker vi at gøre?
>> Hvis vi har nået null-pointer, vi ønsker at stoppe, ellers bare slette
resten af ​​listen og derefter slippe mig.
Slet resten af ​​listen, og derefter slippe den aktuelle node.
Hvad lyder det som, hvad teknik har vi talte
om tidligere lyder det ud?
Slet alle andre, så komme tilbage og slette mig.
>> Det er rekursion, har vi gjort Problem lidt mindre,
vi siger slet alle andet, så kan du slette mig.
Og længere nede ad vejen, at node vil sige, slette alle andre.
Men til sidst vil vi komme til punkt, hvor listen er nul,
og det er vores base sagen.
>> Så lad os tage et kig på denne, og hvordan dette kunne arbejde.
Så her er vores liste, det er det samme liste blev vi bare taler om,
og der er de skridt.
Der er en masse tekst her, men forhåbentlig visualisering vil hjælpe.
>> Så vi have-- og jeg også trukket vores stakrammer illustration
fra vores video på opkald stakke, og forhåbentlig alt dette
sammen vil vise dig, hvad der foregår.
Så her er vores pseudokode kode.
Hvis vi når en null pointer, stop, ellers
slet resten af ​​listen, derefter slippe den aktuelle node.
Så lige nu, list-- markøren, at vi er
passerer at ødelægge point til 12.
12 er ikke en null-pointer, så vi er ved at slette resten af ​​listen.
>> Hvad er at slette resten af ​​os involveret?
Tja, det betyder at gøre en ringe til at ødelægge, siger
at 15 er begyndelsen af resten af ​​listen, vi ønsker at ødelægge.
Og så opfordringen til at ødelægge 12 er lidt i venteposition.
Det er indefrosset der, venter på ringe til at ødelægge 15, for at afslutte sit arbejde.
>> Tja, 15 er ikke en null-pointer, og så det kommer til at sige, okay,
godt, slet resten af ​​listen.
Resten af ​​listen starter på 9, og så vi vil bare
vente, indtil du sletter alt, ting, så kom tilbage og slette mig.
Nå 9 kommer til at sige, ja, Jeg er ikke en null-pointer,
så slette resten listen herfra.
Og så prøv og ødelægge 13.
13 siger, jeg er ikke null-pointer, samme ting, den passerer sorteper.
10 er ikke null-pointer, 10 indeholder en null-pointer,
men 10 er ikke i sig selv en null pointer lige nu,
og så den passerer sorteper også.
>> Og nu liste punkter der, det ville virkelig pege på some--
hvis jeg havde mere plads i billedet, det ville pege på nogle tilfældige plads
at vi ikke ved, hvad det er.
Det er null pointer selv, listen bogstaveligt talt nu sat det værdier null.
Det peger lige inde at røde felt.
Vi nåede en null-pointer, så Vi kan stoppe, og vi er færdig.
>> Og så lilla ramme er nu-- på toppen af ​​stack-- der er den aktive ramme,
men det er gjort.
Hvis vi har nået en null-pointer, stop.
Vi gør ikke noget, vi kan ikke slippe en null-pointer,
vi ikke malloc nogen plads, og så vi er færdig.
Således at funktionen ramme er ødelagt, og vi
resume-- vi fortsætte, hvor vi forlod ud med den næsthøjeste en, hvilket
er denne mørke blå ramme her.
Så vi samle op lige der, hvor vi slap.
Vi udgår resten af listen allerede, så nu er vi
kommer til at frigøre de nuværende knudepunkter.
Så nu kan vi befri denne node, og nu vi har nået slutningen af ​​funktionen.
Og så funktionen ramme er ødelagt, og vi samle op på den lyseblå én.
>> Så det says-- Jeg har allerede done-- slette resten af ​​listen, så
frigøre den aktuelle node.
Og nu den gule ramme er tilbage på toppen af ​​stakken.
Og så som du ser, er vi nu ødelægge listen fra højre til venstre.
>> Hvad ville der være sket, selv om, hvis vi havde gjort tingene på den forkerte vej?
Ligesom da vi forsøgte at tilføje et element.
Hvis vi rodet op kæden, hvis vi ikke tilslutte pointers
i den rigtige rækkefølge, hvis vi netop befriet det første element,
hvis vi bare befriet leder af listen, nu er vi
har ingen måde at henvise til resten af ​​listen.
Og så ville vi have forældreløse alt,
ville vi have haft, hvad der er kaldes en hukommelsesfejl.
Hvis du husker fra vores video på dynamisk hukommelse tildeling,
det er ikke meget god ting.
>> Så som jeg sagde, er der er flere operationer
at vi skal bruge for at arbejde med sammenkædet liste effektivt.
Og du måske har bemærket jeg udeladt en, sletning af et enkelt element fra en forbundet
listen.
Grunden til at jeg gjorde det er det er faktisk slags
vanskelig at tænke over, hvordan du sletter et enkelt element fra en enkeltvis
sammenkædet liste.
Vi skal være i stand til at springe over noget på listen, som
betyder, at vi kommer til en point-- vi vil slette denne node--
men for at gøre det så vi ikke mister nogen oplysninger,
vi nødt til at tilslutte denne node herovre, her.
>> Så sandsynligvis gjorde jeg, at forkert fra et visuelt perspektiv.
Så vi er i begyndelsen af ​​vores liste, vi fortsætter igennem,
vi ønsker at slette denne node.
Hvis vi bare slette det, vi har brudt kæden.
Denne knude lige her refererer til alt andet,
det indeholder kæden fra nu af.
>> Så hvad vi skal gøre rent faktisk efter at vi kommer til dette punkt,
er vi nødt til at træde et skridt tilbage én, og forbinde denne node over til dette knudepunkt,
så vi kan derefter slette den ene i midten.
Men enkeltvis hægtede lister ikke giver os en måde at gå baglæns.
Så vi er nødt til enten at holde to pegepinde, og flytte dem
slags off trin, den ene bag den anden som vi går, eller komme til et punkt
og sende derefter en anden pointer igennem.
Og som du kan se, er det kan få lidt rodet.
Heldigvis har vi En anden måde at løse dette,
når vi taler om dobbelt hægtede lister.
>> Jeg er Doug Lloyd, det er CS50.