>> [MUSIK SPELA]
>> DOUG Lloyd: OK, så på denna punkt i kursen,
Vi har täckt en hel del av grunderna i C. Vi vet en hel del om variabler, arrayer,
pekare, så bra grejer.
De är alla slags inbyggt i att se som grunderna,
men vi kan göra mer, eller hur?
Vi kan kombinera saker tillsammans på ett intressant sätt.
>> Och så låt oss göra det, låt oss börja filial ut vad C ger oss,
och börja skapa våra egna uppgifter strukturer med hjälp av dessa byggnad
block tillsammans för att göra något riktigt värdefullt, användbar.
Ett sätt som vi kan göra det här är att prata om samlingarna.
Så hittills har vi haft en typ av data struktur för att representera samlingar
av gillar värden, liknande värden.
Det skulle vara en matris.
Vi har samlingar av heltal, eller samlingar av tecken och så vidare.
>> Strukturer också sortera av ett data struktur för insamling av information,
men det är inte för att samla liknande värden.
Det blandar oftast olika datatyper tillsammans inne i en enda låda.
Men det är inte i sig används för att kedja ihop
eller koppla samman liknande poster, som en array.
Arrayer är bra för elementet titta upp, men minns
att det är mycket svårt att infoga i en matris,
om vi införa åtmin alldeles i slutet av denna matris.
>> Och det bästa exemplet jag har för det är insättningssortering.
Om ni minns vår video på insättningssortering,
Det fanns en hel del kostnader inblandade i att ha
att plocka upp delar, och flytta dem ur vägen för att passa något
i mitten av matrisen.
Arrayer lider också av en annan problem, som är stelhet.
När vi förklarar en array, vi får ett skott på det.
Vi får säga, jag vill här många element.
Kan vara 100, kanske det vara 1000, kanske det
vara där x är ett nummer som användaren gav oss vid en prompt eller kommandot
linje.
>> Men vi får bara ett skott på det, vi inte får sedan säga åh, jag faktiskt
behövs 101, eller jag behövde x plus 20.
För sent, vi har redan förklarat array, och om vi vill få 101 eller X
plus 20, måste vi förklara en helt annan uppsättning,
kopiera alla element i arrayen över, och sedan har vi nog.
Och tänk om vi har fel igen, vad om vi verkligen behöver 102, eller x plus 40,
Vi måste göra detta igen.
Så de är mycket oflexibel för att ändra storlek våra data,
men om vi kombinerar ihop några av grunderna som vi redan har
lärt sig om pekare och strukturer, särskilt genom dynamiskt minne
tilldelning med malloc, vi kan sätta in dessa bitar tillsammans
att skapa en ny data structure-- en Listan kan vi säga-- ensamma kopplade
som tillåter oss att växa och krympa en samling värden
och vi kommer inte att ha någon slösat utrymme.
>> Så återigen, vi kallar denna idé, detta begrepp, en länkad lista.
I synnerhet i den här videon är vi talar om enskilt länkad lista,
och sedan en annan video vi ska prata om dubbelt länkade listor, som
är bara en variation på ett tema här.
Men en enskilt länkad lista består av noder,
noder bara vara ett abstrakt term-- Det är bara något jag ringer
det är en sorts struktur, i princip, jag är?
Bara kommer att kalla det en node-- och detta nod har två medlemmar, eller två fält.
Det har data, vanligtvis ett heltal, en karaktär flyta,
eller kan vara någon annan datatyp att du har definierat med en typ def.
Och den innehåller en pekare till annan nod av samma typ.
>> Så vi har två saker inuti denna nod, information och en pekare
till en annan nod.
Och om du börjar att visualisera detta kan du tänka på det
som en kedja av noder som är förbundna med varandra.
Vi har den första noden, det innehåller data, och en pekare
till den andra noden, som innehåller uppgifter, och en pekare till den tredje noden.
Och så det är därför vi kallar det en länkad lista, de är sammanlänkade.
>> Vad gör detta speciella nod struktur ser ut?
Tja, om du minns från vår video på definiera egna typer med typ def,
Vi kan definiera en structure-- och Skriv definiera en struktur som denna.
tyepdef struct sllist, och då är jag använda ordet värde här godtyckligt
att ange någon datatyp verkligen.
Du kan vidarebefordra ett heltal eller float, du kan ha vad du vill.
Det är inte begränsat till bara heltal, eller nåt sånt.
Så värdet är bara en godtycklig datatyp och sedan en pekare
till en annan nod av samma typ.
>> Nu finns det en liten hake här med att definiera en struktur
när det är en självrefererande struktur.
Jag måste ha en tillfällig namn för min struktur.
I slutet av dagen I klart vill kalla det
SLL nod, är det i slutändan nya nämna en del av min definition typ,
men jag kan inte använda SLL nod i mitten av denna.
Anledningen är, har jag inte skapat en typ som kallas SLL nod
tills jag hit denna sista punkt här.
Fram till den punkten, jag måste ha ett annat sätt att hänvisa till den här datatypen.
>> Och detta är en själv Referens datatyp.
Det; s en datatyp en struktur som innehåller ett data,
och en pekare till en annan struktur av samma typ.
Så jag behöver för att kunna hänvisa till den här datatypen åtminstone tillfälligt,
så ger det en temporär namn struct sllist
låter mig då säga att jag vill ha en pekare till en annan struct sllist,
en struct sllist stjärna, och sedan efter att jag har slutfört definition,
Jag kan nu kalla denna typ en SLL nod.
>> Så det är därför du ser att det finns ett tillfälligt namn här,
men en permanent namn här.
Ibland kan du se definitioner av strukturen,
till exempel, som inte är självrefererande, att
inte har en specificeraren namn här.
Det skulle bara säga typedef struct, öppna klammerparentes och sedan definiera den.
Men om du är struct är själv referens, som denna är,
måste du ange en temporärt namn typ.
Men i slutändan, nu att vi har gjort detta,
vi kan bara referera till dessa noder, dessa enheter,
som SLL noder för ändamål av resten av den här videon.
>> Okej, så vi vet hur man skapa en länkad lista nod.
Vi vet hur man definierar en länkad lista nod.
Nu, om vi ska börja använda dem för att samla in information,
det finns ett par operationer vi måste förstå och arbeta med.
Vi behöver veta hur man skapar en länkad lista ur luften.
Om det inte finns någon lista redan Vi vill starta en.
Så vi behöver för att kunna att skapa en länkad lista,
Vi måste förmodligen söka via länken listan
att hitta ett element som vi letar efter.
Vi måste kunna sätta in nya saker i listan,
Vi vill att vår lista för att kunna växa.
Och på samma sätt vill vi kunna att ta bort saker från vår lista,
Vi vill att vår lista för att kunna krympa.
Och i slutet av vår program, i synnerhet
om ni minns att vi är dynamiskt allokera minne
att bygga dessa listor typiskt vi vill befria allt detta minne
När vi är klara att arbeta med det.
Och så vi måste kunna ta bort en Hela länkad lista i en misslyckas svep.
Så låt oss gå igenom några av dessa operationer
och hur vi kan visualisera dem, talar i pseudokod kod specifikt.
Så vi vill skapa en lista kopplad, så kanske vi
vill definiera en funktion med denna prototyp.
SLL nod stjärna, skapa och jag passerar i ett argument, en del godtyckligt data
skriver igen, av någon godtycklig datatyp.
Men jag returning-- denna funktion bör tillbaka till mig en pekare till ett enskilt
länkad lista nod.
Återigen, vi försöker att skapa en länkad lista ur luften,
så jag behöver en pekare till den listan när jag är klar.
>> Så vad är stegen här?
Tja, första jag kommer att göra är dynamiskt
allokera utrymme för en ny nod.
Återigen, vi skapar det ur tomma luft, så vi måste malloc utrymme för det.
Och naturligtvis, omedelbart när vi malloc,
vi alltid kontrollera att se till att vår pointer-- vi inte få tillbaka noll.
För om vi försöker och aktning en null-pekare,
vi kommer att drabbas av en segfault och vi vill inte ha det.
>> Sedan vi vill fylla i fältet, Vi vill initiera värdefältet
och initiera nästa fält.
Och sedan vill vi att-- småningom som funktionsprototyp indicates-- vi vill
att returnera en pekare till en SLL nod.
Så vad gör detta ser ut visuellt?
Tja, först ska vi dynamiskt allokera utrymme för en ny SLL nod,
så vi malloc-- det är en visuell representation
av noden vi just skapat.
Och vi kontrollera att det är inte null-- i detta fall,
bilden skulle inte ha visas upp om det var noll,
vi skulle ha slut på minne, så vi är bra att åka dit.
Så nu är vi vidare till steg C, initialisera noderna värdefältet.
Tja, baserat på denna funktion kallar jag använder här,
ser ut som jag vill passera på 6, så jag ska 6 i värdefältet.
Nu, initiera nästa fält.
Tja, vad ska jag göra där, det finns inget nästa, höger,
Detta är det enda i listan.
Så vad är nästa sak på listan?
>> Det bör inte peka på någonting, höger.
Det finns inget annat där, så vad är Begreppet vi känner till som är nothing--
pekare till ingenting?
Det borde vara kanske vi vill att sätta en null-pekare där,
och jag ska representera null pekaren som bara en röd ruta,
vi kan inte gå längre.
Som vi ser lite senare, Vi kommer att ha så småningom kedjor
av pilar som förbinder dessa noder tillsammans,
men när du träffar röda rutan, det är noll,
vi kan inte gå längre, det är slutet av listan.
>> Och slutligen, vi vill bara returnera en pekare till denna nod.
Så vi kallar det nya, och kommer tillbaka nya
så att den kan användas i oavsett funktion skapade den.
Så det vi går, har vi skapat en för sig länkad lista nod ur luften,
och nu har vi en lista som vi kan arbeta med.
>> Nu, låt oss säga att vi redan ha en stor kedja,
och vi vill hitta något i det.
Och vi vill ha en funktion som kommer att återvända sant eller falskt, beroende
om huruvida ett värde finns i listan.
En funktion prototyp eller deklaration för denna funktion,
kan se ut this-- Bool hitta, och då vill vi att passera i två argument.
>> Den första är en pekare till första elementet i länklistan.
Detta är faktiskt något du alltid vill hålla reda på,
och faktiskt kan vara något som du även sätta i en global variabel.
När du har skapat en lista, du alltid, alltid
vill hålla reda på den mycket första elementet i listan.
På så sätt kan du hänvisa till alla andra element genom att bara följa kedjan,
utan att behöva hålla pekare intakt till varje enskilt element.
Du behöver bara hålla reda på den första ett om de är alla kedjas ihop.
>> Och sedan den andra saken vi passerar igen
är godtyckligt some-- oavsett datatyp vi
efter det är inne i förhoppningsvis en av noderna i listan.
Så vad är stegen?
Tja, är det första vi gör Vi skapar en övergripande pekare
pekar på listorna huvudet.
Tja, varför gör vi det, vi redan har en pekare på listorna huvudet,
varför inte vi bara flytta den en runt?
Tja, som jag just sagt, det är verkligen viktigt för oss
att alltid hålla reda på mycket första elementet i listan.
Och så är det faktiskt bättre att skapa en kopia av det,
och använda det för att flytta runt så vi aldrig oavsiktligt flytta bort, eller vi alltid
har en pekare vid någon tidpunkt som är rätt på det första elementet i listan.
Så det är bättre att skapa en andra som vi använder för att flytta.
>> Då vi jämför bara om värdet fältet vid denna nod
är vad vi letar efter, och om det är inte, vi bara gå vidare till nästa nod.
Och vi fortsätta att göra det över, och över, och över,
tills vi antingen hitta elementet, eller vi hit
null-- vi har nått slutet på listan och det är inte det.
Detta bör förhoppningsvis ringa en klocka till dig som bara linjär sökning,
vi bara replikera det i en enskilt länkad lista struktur
istället för att använda en matris för att göra det.
>> Så här är ett exempel på en enskilt länkad lista.
Detta består av fem noder, och vi har
en pekare till chefen för listan, som kallas listan.
Det första vi vill göra är igen, skapa den genomgångs pekare.
Så vi har nu två pekare som pekar på samma sak.
>> Nu märker här också, det gjorde jag inte måste malloc något utrymme för trav.
Jag sa inte trav lika malloc något, redan denna nod,
detta utrymme i minnet finns redan.
Så allt jag faktiskt gör är skapa en annan pekare till det.
Jag är inte mallocing ytterligare utrymme, bara har nu två pekare
pekar på samma sak.
>> Så är 2 vad jag letar efter?
Tja, nej, så i stället jag kommer att flytta till nästa.
Så i princip skulle jag säga, trav lika trav nästa.
Är 3 vad jag letar efter, nej.
Så jag fortsätter att gå igenom, tills slutligen
få till 6 vilket är vad jag ser för baserat på funktionsanrop
Jag har på toppen där, och så jag är klar.
>> Nu, vad händer om elementet jag söker inte finns i listan,
är det fortfarande kommer att fungera?
Tja, märker att listan här är subtilt olika,
och detta är en annan sak som är viktigt med länkade listor,
du behöver inte för att bevara dem i någon särskild ordning.
Du kan om du vill, men Du kanske redan har märkt
att vi inte hålla reda på vilket nummer elementet vi befinner oss i.
>> Och det blir liksom en handel som vi har med länkad lista verser arrayer,
är det att vi inte har direktåtkomst längre.
Vi kan inte bara säga, jag vill att gå till 0. elementet,
eller 6:e ​​elementet i min array, som jag kan göra i en rad.
Jag kan inte säga att jag vill gå till 0. Element, eller 6: e elementet,
eller den 25: e elementet i min länkad lista, det finns inget index i samband med dem.
Och så det spelar ingen egentligen ingen roll om vi bevara vår lista i ordning.
Om du vill kan du säkert kan, men det finns
ingen anledning till varför de behöver bevaras i vilken som helst ordning.
Så återigen, låt oss försöka och hitta 6 i den här listan.
Tja, börjar vi på början, vi inte hitta 6,
och då kan vi inte fortsätta att hitta 6, tills vi så småningom hit.
Så just nu trav pekar på noden innehållande 8, och sex är inte där.
>> Så nästa steg skulle vara för att gå till nästa pekaren,
så säger trav lika trav nästa.
Tja, trav nästa, indikeras av den röda lådan finns, är null.
Så det finns ingen annanstans att gå, och så på denna punkt
Vi kan konstatera att vi har nått I slutet av den länkade listan,
och 6 är inte där.
Och det skulle återlämnas false i detta fall.
>> OK, hur ska vi sätta in en ny nod i den länkade listan?
Så vi har kunnat skapa en länkad lista från ingenstans,
men vi vill förmodligen bygga en kedja och inte
skapa en massa olika listor.
Vi vill ha en lista som har ett gäng noder i det,
inte en grupp av listor med en enda nod.
Så vi kan inte bara fortsätta att använda Skapa funktion vi definierade tidigare, nu är vi
vill infoga i en lista som redan finns.
>> Så det här fallet, kommer vi att passera i två argument,
pekaren till chefen för att lista som vi vill lägga till länkade.
Återigen, det är därför det är så viktigt att vi alltid
hålla reda på det, eftersom Det är det enda sättet vi verkligen
måste hänföra sig till hela listan är bara genom en pekare till det första elementet.
Så vi vill passera på en pekare till det första elementet,
och oavsett värde som vi vill lägga till i listan.
Och så småningom denna funktion kommer att returnera en pekare
till ny chef för en länkad lista.
>> Vilka är de steg som ingår här?
Jo, precis som med att skapa, vi behöver för att dynamiskt allokera
utrymme för en ny nod och kontrollera att göra att vi inte får slut på minne, återigen,
eftersom vi använder malloc.
Då kan vi vill fylla och sätt i noden,
så uppskattar antalet, oavsett Val är, in i noden.
Vi vill infoga noden på början av den länkade listan.
>> Det finns en anledning till att jag vill göra detta, och det
kan vara värt att ta en andra att pausa videon här,
och fundera på varför jag skulle vilja infoga i början av en länkad
listan.
Återigen, jag nämnde tidigare att det egentligen inte
roll om vi bevara det på något ordning, så kanske det är en ledtråd.
Och du såg vad som skulle hända om vi ville att-- eller bara en sekund
sedan när vi var på väg genom ökning kan
kunde se vad som kan hända om vi försökte
att infoga i slutet av listan.
Eftersom vi inte har en pekaren till slutet av listan.
>> Så anledningen till att jag skulle vilja att infoga i början,
är att jag kan göra det omedelbart.
Jag har en pekare i början, och vi får se detta i ett visuellt i en sekund.
Men om jag vill infoga i slutet, Jag måste börja från början,
passera hela vägen till änden, och sedan lägga fram det på.
Så det skulle innebära att införing i slutet av listan
skulle bli en o n drift, kommer tillbaka
till vår diskussion om beräkningskomplexitet.
Det skulle bli en o n drift, där som listan blev större och större,
och större, kommer det att bli mer och svårare att kryssa något
på slutet.
Men det är alltid riktigt enkelt att please något på i början,
du är alltid i början.
>> Och vi får se en visuell detta igen.
Och sedan när vi är klara, en gång Vi har satt den nya noden,
vi vill återvända vår pekare till ny chef för en länkad lista, som
eftersom vi sätta in på början, faktiskt kommer att
en pekare till noden vi just skapat.
Låt oss visualisera detta, eftersom jag tror att det hjälper.
>> Så här är vår lista, består av fyra delar, en nod innehåller 15,
vilket pekar på en nod innehållande 9, som
pekar på en nod som innehåller 13, vilket pekar på en nod som innehåller
10, som har noll pekare som nästa pekare
så det är i slutet av listan.
Så vi vill infoga en nya noden med värdet 12
i början av detta listan, vad gör vi?
Tja, först vi malloc utrymme för nod, och sedan sätter vi 12 där.
>> Så nu har vi nått en beslutspunkt, eller hur?
Vi har ett par tips som vi kunde
flytta, vilket man bör vi gå först?
Ska vi göra 12 poäng för den nya chefen för list--
eller ursäkta mig, bör vi göra 12 peka på gamla chef på listan?
Eller ska vi säga att listan börjar nu på 12.
Det finns en skillnad där, och vi ska titta
på vad som händer med både i en sekund.
>> Men detta leder till en bra ämne för sidofältet,
vilket är att en av de svåraste saker med länkade listor
är att ordna pekarna i rätt ordning.
Om du flyttar saker i ordning, du kan hamna oavsiktligt
föräldralösa resten av listan.
Och här är ett exempel på detta.
Så låt oss gå med idén of-- Tja, vi har just skapat 12.
Vi vet 12 kommer att vara ny chef för listan,
och så varför inte vi går bara listan pekaren för att peka där.
>> OK, så det är bra.
Så nu där har 12 nästa punkt?
Jag menar, visuellt kan vi se att det kommer att peka på 15,
som människor det är verkligen uppenbart för oss.
Hur datorn vet?
Vi har inget pekar på 15 längre, eller hur?
>> Vi har förlorat någon förmåga att hänvisa till 15.
Vi kan inte säga nya pilen bredvid jämlikar något, det finns inget där.
I själva verket har vi föräldralösa resten av listan
genom att göra så, vi har oavsiktligt brutit kedjan.
Och vi absolut inte vill göra det.
>> Så låt oss gå tillbaka och prova det här igen.
Kanske rätt sak att göra är att ställa in 12 nästa pekare
till den gamla chefen för listan först, då kan vi flytta listan över.
Och faktiskt, är att den rätt ordning att vi
måste följa när vi är arbetar med enskilt länkad lista.
Vi vill alltid att ansluta nytt element i listan,
innan vi tar den typen av viktigt steget att ändra
där chefen för den länkade listan är.
Återigen, det är en sådan grundläggande sak, vi vill inte förlora reda på det.
>> Så vi vill se till att allt kedjas ihop,
innan vi går att pekaren.
Och så detta skulle vara rätt ordning, vilket är att ansluta 12 till listan,
sedan säga att listan börjar ett 12.
Om vi ​​sade listan börjar vid 12 och sedan försökte ansluta 12 till listan,
Vi har redan sett vad som händer.
Vi förlorar listan av misstag.
>> OK, så en sak att prata om.
Vad händer om vi vill bli av med lista en hel kopplad på en gång?
Återigen, vi mallocing allt detta utrymme, och så vi
behöver frigöra den när vi är klara.
Så nu vill vi ta bort hela den länkade listan.
Tja, vad vill vi göra?
>> Om vi ​​har nått nollpekare, vi vill sluta, annars bara ta bort
resten av listan och sedan befria mig.
Ta bort resten av listan, och sedan frigöra den aktuella noden.
Vad gör det låter som, vilken teknik har vi pratat
om tidigare låter det som?
Ta bort alla andra, då komma tillbaka och ta bort mig.
>> Det är rekursion, har vi gjort Problemet lite mindre,
vi säger bort alla annars, då kan du ta bort mig.
Och längre ner på gatan, nod som kommer att säga, ta bort alla andra.
Men så småningom kommer vi att komma till punkt där listan är null
och det är vår bas fallet.
>> Så låt oss ta en titt på detta, och hur detta kan fungera.
Så här är vår lista, det är samma listar vi bara talar om,
och det finns stegen.
Det finns en hel del text här, men förhoppningsvis visualisering kommer att hjälpa.
>> Så vi have-- och jag drog också upp vår stackramar illustrationen
från vår video på samtals stackar, och förhoppningsvis allt detta
tillsammans kommer att visa dig vad som händer.
Så här är vår pseudokoden.
Om vi ​​når ett noll Pekare, stopp, annars
radera resten av listan, sedan frigöra den aktuella noden.
Så just nu, list-- pekaren att vi är
passerar in för att förstöra punkter till 12.
12 är inte en nollpekare, så vi är kommer att ta bort resten av listan.
>> Vad som att ta bort resten av oss inblandade?
Tja, betyder det att en ringa för att förstöra, säger
att 15 är början av den resten av listan vi vill förstöra.
Och så uppmaningen att förstöra 12 är typ av på is.
Det är frusen där, väntar på ringa för att förstöra 15, för att avsluta sitt jobb.
>> Tja, 15 är inte en nollpekare, och så det kommer att säga, okej,
Tja, ta bort resten av listan.
Resten av listan börjar vid 9, och så vi ska bara
vänta tills du tar bort allt som grejer och sedan komma tillbaka och ta bort mig.
Tja 9 kommer att säga, ja, Jag är inte en nollpekare,
så radera resten listan härifrån.
Och så försöker förstöra 13.
13 säger: Jag är inte nollpekare, Samma sak, passerar den buck.
10 är inte nollpekare, 10 innehåller en null-pekare,
men 10 är inte i sig en null pekaren just nu,
och så den passerar buck också.
>> Och nu lista punkter där det verkligen vill påpeka att some--
om jag hade mer utrymme i bilden, det skulle peka på vissa slumpmässiga utrymme
att vi inte vet vad det är.
Det är noll pekaren men listan bokstavligen nu inställd det värden null.
Det pekar åt höger innanför den röda rutan.
Vi nådde en nollpekare, så vi kan stoppa, och vi är klara.
>> Och så att lila ramen är now-- vid ovanpå stack-- som är den aktiva ramen,
men det är gjort.
Om vi ​​har nått en null-pekare, sluta.
Vi gör ingenting, vi kan inte befria en null-pekare,
vi inte malloc någon utrymme, och så vi är klara.
Så denna funktion ram förstörs, och vi
resume-- vi plocka upp där vi lämnade bort med nästa högsta, som
är denna mörka blå ram här.
Så vi plockar upp precis där vi slutade.
Vi strök resten av listan redan, så nu är vi
kommer att frigöra de aktuella noderna.
Så nu kan vi frigöra denna nod, och nu Vi har kommit till slutet av funktionen.
Och så denna funktion ram förstörs, och vi plocka upp på ljusblå ett.
>> Så det says-- jag har redan done-- ta bort resten av listan, så
frigöra den aktuella noden.
Och nu den gula ramen är tillbaka på toppen av stacken.
Och så som du ser, är vi nu förstöra listan från höger till vänster.
>> Vad skulle ha hänt, men Om vi ​​hade gjort saker på fel sätt?
Precis som när vi försökte att lägga till ett element.
Om vi ​​trasslat till kedjan, om vi inte koppla pekarna
i rätt ordning, om vi just befriat det första elementet,
om vi bara befriade av listan, nu vi
har ingen möjlighet att hänvisa till resten av listan.
Och så skulle vi ha föräldralösa allt,
Vi skulle ha haft vad som är kallas en minnesläcka.
Om ni minns från vår video på dynamisk minnesallokering,
det är inte så bra.
>> Så som sagt, det finns flera operationer
att vi måste använda för att arbeta förteckning faktiskt samband.
Och ni kanske har märkt jag utelämnat en, radera en enda element från en länkad
listan.
Anledningen till att jag gjorde det är det faktiskt typ av
svårt att tänka på hur man tar bort en enda element från ett enskilt
länkad lista.
Vi måste kunna hoppa över något i listan, vilket
innebär att vi får en point-- vi vill radera detta node--
men för att göra det så vi inte förlorar någon information,
Vi måste ansluta denna nod hit, här.
>> Så jag gjorde förmodligen är fel på det visuella planet.
Så vi är i början av vår lista, vi fortsätter igenom,
Vi vill ta bort denna nod.
Om vi ​​bara ta bort det, Vi har brutit kedjan.
Denna nod här hänvisar till allt annat,
den innehåller kedjan från här på ut.
>> Så vad vi behöver göra faktiskt när vi kommer till denna punkt,
är att vi måste ta ett steg tillbaka ett och ansluta denna nod över till denna nod,
så att vi kan sedan ta bort den i mitten.
Men ensamma länkade listor inte ger oss ett sätt att gå bakåt.
Så vi måste antingen behålla två pekare, och flytta dem
sorts off steg, en bakom andra som vi går, eller komma till en punkt
och sedan skicka en annan pekare igenom.
Och som ni kan se, det kan bli lite rörigt.
Lyckligtvis har vi ett annat sätt att lösa detta,
när vi talar om dubbelt länkade listor.
>> Jag är Doug Lloyd, är detta CS50.