[Musik spiller] David J. MALAN: Okay. Dette er CS50. Det er uge fem fortsat, og vi har nogle gode nyheder og nogle dårlige nyheder. Så god nyhed er, at CS50 lancerer denne fredag. Hvis du ønsker at slutte sig til os, hovedet til den sædvanlige webadresse her. Endnu bedre nyheder, ingen foredrag på mandag den 13.. Lidt mindre bedre nyheder, quiz nul er næste onsdag. Flere detaljer kan findes på denne webadresse her. Og i løbet af de næste par dage vi vil udfylde de tomme felter med hensyn til værelserne at vi vil have reserveret. Bedre nyhed er, at der vil være et kursus for hele anmeldelse session i det kommende Mandag i aften. Hold øje med kursets hjemmeside for placering og detaljer. Sektioner, selvom det er en ferie, også vil mødes så godt. Bedste nyheder, foredrag næste fredag. Så dette er en tradition, vi har, som pr pensum. Bare-- det vil være fantastisk. Du vil se ting som konstant tid datastrukturer og hash tabeller og træer og forsøger. Og vi vil tale om fødselsdag problemer. En hel masse ting afventer næste fredag. OK. Alligevel. Så minde om, at vi har været fokus på dette billede af, hvad der er inde i vores computerens hukommelse. Så hukommelse eller RAM er, hvor programmerne findes mens du kører dem. Hvis du dobbeltklikker på en ikonet for at køre nogle program eller dobbeltklik på en ikonet for at åbne nogle fil, den er indlæst fra din harddisk drev eller SSD-drev i RAM, Random Access Memory, hvor det lever, indtil strømmen går ud, den bærbare computer låget lukkes, eller du afslutter programmet. 

Nu, hukommelse, af som du sikkert har 1 gigabyte i disse dage, 2 gigabyte, eller endda meget mere, er generelt fastlagt for et givet i denne slags rektangulære konceptuel model hvorved vi har stakken på bunden og en masse andre ting på toppen. De ting øverst vi har set på dette billede før men aldrig talt om er den såkaldte tekstsegment. Tekst segment er bare en fancy måde sige de nuller og ettaller, der komponere din faktiske kompileret program. 

Så når du dobbeltklikker Microsoft Word på din Mac eller pc, eller når du kører prik skråstreg Mario på en Linux-computer på dit terminalvindue, de nuller og ettaller, der udgør Word eller Mario gemmes midlertidigt i computerens RAM i den såkaldte tekstsegment til et bestemt program. Nedenfor der går initialiseret og uden startværdi data. Det er ting som globale variabler, at vi ikke har brugt mange af, men lejlighedsvis vi har havde globale variabler eller statisk defineret strenge, er hårdt kodet ord som "Hej" der er ikke taget ind fra brugeren der er hard-kodet ind i dit program. 

Nu ned til bunden vi har den såkaldte stak. Og stakken, hidtil, vi har været hjælp til hvilke typer af formål? Hvad er stakken blevet brugt til? Ja? 

Publikum: Funktioner. 

David J. MALAN: For funktioner? I hvilken forstand for funktioner? 

Publikum: Når du ringer til en funktion, argumenter er kopieret over på stakken. 

David J. MALAN: Præcis. Når du ringer til en funktion, dens argumenter er kopieret over på stakken. Så enhver X'er eller Y'er eller A'er eller BS at du passerer ind i en funktion midlertidigt sat på den såkaldte stak, ligesom en af ​​Annenberg Dining Hall bakker og også ting ligesom lokale variable. Hvis din foo funktion eller din swap funktion har lokale variabler, ligesom temp, de to ender på stakken. Nu vil vi ikke snakke for meget om dem, men disse miljøvariabler nederst oplevede vi et stykke tid siden, da Jeg var futzing på tastaturet en dag og jeg begyndte at få adgang til tingene ligesom argv 100 eller argv 1.000, bare elements-- jeg glemmer den numbers-- men at skulle ikke tilgås af mig. Vi begyndte at se nogle funky symboler på skærmen. Det var såkaldte miljøvariabler ligesom de globale indstillinger for min program eller til min computer, ikke relateret til den nylige fejl, som vi diskuterede, Shellshock, der har været plager en hel computere. 

Nu endelig i dagens fokus vi vil i sidste ende være på bunke. Dette er en anden luns af hukommelse. Og fundamentalt alt dette hukommelse er den samme ting. Det er den samme hardware. Vi er bare slags behandle forskellige klynger byte til forskellige formål. Den bunke er også vil være der, hvor variabler og hukommelse, som du anmoder fra operativsystemet opbevares midlertidigt. 

Men der er lidt af et problem her, som billedet antyder. Vi slags har to skibe om at kollidere. Fordi som du bruger mere og mere af stakken, og som vi ser i dag og fremefter, som du bruger mere og mere af det dynge, helt sikkert dårlige ting kan ske. Og ja, vi kan fremkalde det bevidst eller ubevidst. Så cliffhanger sidste tidspunkt var dette program, som ikke tjener noget funktionelt andet end at demonstrere formål hvordan du som en slem fyr rent faktisk kan tage fordel af fejl i en andens program og overtage et program eller endda en hele computeren eller server. Så bare at kaste et blik, du bemærke, at hovedsagen i bunden tager på kommandolinjen argumenter, som pr argv. Og det har et kald til en funktion f, væsentlige en anonym funktion kaldet f, og den går i argv [1]. 

Så uanset ord brugeren typer i på prompten efter dette program navn, og så denne vilkårlige funktion op top, f, tager i en streng, AKA char *, som vi er begyndt at diskutere, og det bare kalder det "bar". Men vi kunne kalde det noget. Og så erklærer det, indenfor f, et array af tegn kaldet C-- 12 sådanne tegn. 

Nu ved den historie, jeg fortalte for et øjeblik siden, hvor i hukommelsen c, eller er de 12 chars ender? Bare for at være klar. Ja? 

Publikum: på stakken. 

David J. MALAN: på stakken. Så c er en lokal variabel. Vi beder om 12 tegn eller 12 byte. De kommer til at ende op på den såkaldte stak. Nu endelig er denne anden funktion Det er faktisk temmelig nyttigt, men vi har ikke rigtig brugt det selv, strncopy. Det betyder streng kopi, men kun n bogstaver, n tegn. Så n tegn vil være kopieret fra bar til ca. Og hvor mange? Længden af ​​baren. Så med andre ord, at én linje, strncopy, kommer til at kopiere effektivt bar i til c. 

Nu, bare at slags forudse moralen i denne historie, hvad der er potentielt problematiske her? Selvom vi tjekker længden bar og passerer det ind strncopy, hvad er din tarm fortæller dig er stadig brudt om dette program? Ja? 

Publikum: Indeholder ikke plads til nul-karakteren. David J. MALAN: Indeholder ikke plads til nul-karakteren. Potentielt, i modsætning til tidligere praksis, vi ikke engang har så meget som et plus 1 til rumme at null-tegn. Men det er endnu værre end det. Hvad skal vi ellers ikke at gøre? Ja? 

Publikum: [uhørligt] David J. MALAN: Perfect. Vi har hårdt kodet 12 temmelig vilkårligt. Det er ikke så meget problem, men det faktum, at vi ikke selv kontrollere, om længden af ​​linjen er mindre end 12, i hvilket tilfælde det vil være sikkert at sætte det ind i hukommelsen kaldet C, som vi har tildelt. Faktisk, hvis bar er ligesom 20 tegn lange, denne funktion synes at kopiere 20 tegn fra bar til C, og dermed at tage mindst 8 bytes at det ikke bør være. Det er underforstået her. 

Så kort, brudte program. Ikke sådan en big deal. Måske får du en segmentering fejl. Vi har alle haft fejl i programmer. Vi har alle kunne have bugs i programmer lige nu. Men hvad er konsekvenserne? Nå, her er en zoomet ind version af at billede af min computers hukommelse. Dette er bunden af ​​min stak. Og ja, allernederst er, hvad der er kaldet forælder rutine stak, fancy måde for at sige, det er vigtigste. Så hvem kaldte funktion f, som vi taler om. Så er bunden af ​​stakken. Returadresse er noget nyt. Det har altid været der, altid været i det billede. Vi har bare aldrig gjort opmærksom på det. Fordi det viser sig, den måde C værker er at når en funktion kalder en anden, ikke kun gøre de argumenter, der funktion blive skubbet på stakken, ikke kun gøre funktionens lokale variabler bliver skubbet på stakken, noget, der hedder en returadresse også bliver sat på stakken. Specifikt om de vigtigste opkald Foo, Mains egen adresse i hukommelsen, okse noget, effektivt bliver sat på stakken således at når f er færdig køre den ved hvor man kan hoppe tilbage til i teksten segmentet for at fortsætte udførelsen. 

Så hvis vi er her begrebsmæssigt, i hoved, så f bliver kaldt. Hvordan f vide, hvem til håndbetjening tilbage? Nå, denne lille brødkrumme i rødt her, kaldet returadresse, det bare checks, hvad er det returadresse? Åh, lad mig springe tilbage til hoved her. Og det er en lille smule af en oversimplificering, fordi de nuller og ettaller for vigtigste er teknisk heroppe i tech-segmentet. Men det er den idé. f bare har at vide, hvad hvor kontrol i sidste ende går tilbage. 

Men den måde computere har længe lagt ud ting ligesom lokale variable og argumenter er ligesom dette. Så i toppen af ​​dette billede i blå er stakken ramme til f, så alle af hukommelsen, at f specifikt er bruger. Så derfor bemærke, at bar er i dette billede. Bar var sit argument. Og vi påstod, at argumenterne til funktioner bliver skubbet på stakken. Og C, selvfølgelig, er også på dette billede. 

Og bare for notational formål, mærke i øverste venstre hjørne er, hvad der ville være c beslag 0 og derefter lidt ned til højre er c beslag 11. Så med andre ord, kan du forestille dig at der er et gitter af bytes der for det første som er øverst til venstre, bund er den sidste af de 12 byte. 

Men nu forsøge at spole frem. Hvad er ved at ske, hvis vi passerer i en streng bar, der er længere end C? Og vi er ikke at kontrollere, om Det er faktisk længere end 12. Hvilken del af dette billede vil bliver overskrevet af byte 0, 1, 2, 3, dot dot dot, 11, og derefter dårlig, 12, 13 til 19? Hvad kommer til at ske her, hvis du udlede af bestilling at c beslag 0 er på toppen og c beslag 11 er slags ned til højre? Ja? 

PUBLIKUM: Jamen, det vil at overskrive char * baren. 

David J. MALAN: Ja, det ligner du kommer til at overskrive char * bar. Og værre, hvis du sender i en virkelig lang streng, kan du endda overskrive hvad? Returadressen. Hvilket igen, er ligesom en brødkrumme at fortælle programmet, hvor at gå tilbage til når f gøres bliver kaldt. 

Så hvad skurkene typisk gør er, hvis de kommer på tværs af et program at de er nysgerrige om det er udnytte, buggy på en sådan måde at han eller hun kan tage fordel af denne fejl, generelt de ikke får dette rigtigt første gang. De bare begynde at sende, for eksempel, tilfældige strenge i dit program, enten på tastaturet, eller ærligt de sandsynligvis skrive et lille program til bare automatisk generere strygere, og begynde at slå på dit program ved at sende masser af forskellige indgange ved forskellige længder. 

Så snart dit program går ned, det er en fantastisk ting. Fordi det betyder, at han eller hun har opdaget hvad der formentlig er faktisk en fejl. Og så de kan få mere klog og begynde at fokusere mere snævert om, hvordan at udnytte denne fejl. Især hvad han eller hun kan gøre er at sende, i bedste fald, hej. Nogen big deal. Det er en streng, der er tilstrækkelig kort. Men hvad nu, hvis han eller hun sender, og vi vil generalisere det som, angreb code-- så nuller og dem, der gør tingene ligesom rm-rf, der fjerner alt fra harddisken eller sende spam eller anden måde at angribe maskinen? 

Så hvis hver af disse bogstaverne A bare repræsenterer, konceptuelt, angreb, angreb, angreb, angreb, nogle dårlige kode at en anden skrev, men hvis denne person er smart nok til ikke kun at omfatte alle disse rm-RFS, men også har hans eller hendes sidste par bytes være et nummer, der svarer til adressen på hans eller hendes eget angreb kode at han eller hun gik i bare ved at give den ved prompten, du effektivt kan narre computeren i at lægge mærke til, når f er færdig udførelse, Åh, det er tid for mig til at hoppe tilbage til den røde returadresse. Men fordi han eller hun har en eller anden måde overlappede denne returadresse med deres eget nummer, og de er smart nok har konfigureret at nummer til at henvise, som du se i super top venstre hjørne er der, den faktiske adresse i computerens hukommelse nogle af deres angreb kode, en slem fyr kan narre computeren i udførelsen af ​​hans eller hendes egen kode. 

Og denne kode, igen, kan være alt. Det er generelt kaldes shell kode, som er lige en måde at sige, at det ikke er generelt noget så simpelt som RM-RF. Det er faktisk noget som Bash, eller et program, der giver ham eller hendes programmatisk kontrol at udføre noget andet, som de vil. Så kort sagt, alt dette stammer fra den simple kendsgerning, at denne fejl er involveret ikke kontrol grænserne for dit array. Og fordi den måde computere arbejde er, at de bruge stakken fra effektivt, begrebsmæssigt, bund på op, men derefter elementer du skubber ind på stakken vokse oppefra og ned, dette er utroligt problematisk. Nu er der måder at arbejde omkring dette. Og helt ærligt, er der sprog med til at løse dette. Java er immun for eksempel til dette særlige spørgsmål. Fordi de ikke give dig fingerpeg. De give ikke dig Direct Memory adresser. Så med denne magt, at vi har at røre noget i hukommelsen vi ønsker kommer ganske vist stor risiko. 

Så hold øje. Hvis helt ærligt, i de kommende måneder eller år at komme, når som helst du læse om nogle udnyttelse af et program eller en server, hvis du nogensinde ser en antydning af noget som en buffer overflow angreb, eller stakoverløb er en anden type for angreb, der ligner i ånden, meget, som inspirerer webstedets navnet, hvis du kender det, det er alle taler om lige overfyldte størrelsen af ​​nogle tegn matrix eller nogle matrix mere generelt. Eventuelle spørgsmål, så om dette? Prøv ikke dette derhjemme. 

Okay. Så malloc hidtil har været vores nye ven i, at vi kan allokere hukommelse at vi ikke nødvendigvis kender i forhånd ved, at vi ønsker, så vi ikke har til hårdt kode ind i vores programnumre som 12. Når brugeren fortæller os, hvor meget data, som han eller hun ønsker at indtaste, vi kan allokere så meget hukommelse. 

Så malloc det viser sig, at den omfang, vi har brugt det, eksplicit sidste gang, og derefter gutter har brugt det til getString ubevidst for flere uger, alle allokere hukommelse kommer fra den såkaldte bunke. Og det er derfor getString for eksempel kan allokere hukommelse dynamisk uden at vide hvad du er kommer til at skrive i forvejen, hånd du tilbage en pegepind til denne hukommelse, og at hukommelsen er stadig jeres at beholde, selv efter getString afkast. Fordi tilbagekaldelse efter alt at stak konstant går op og ned, op og ned. Og så snart det går ned, betyder enhver hukommelse denne funktion anvendes, bør ikke bruges af andre. Det er skrald værdier nu. 

Men den bunke er heroppe. Og hvad er rart om malloc er, at når malloc allokerer hukommelse op her, det er ikke påvirket, for størstedelens vedkommende af stakken. Og så enhver funktion kan få adgang til hukommelse, der er blevet malloc'd, selv af en funktion som getString, selv efter at det er returneret. 

Nu det modsatte af malloc er gratis. Og ja, den regel, du nødt til at begynde at vedtage er noget, enhver, når som helst du bruger malloc du skal selv bruge gratis, til sidst, på samme pointer. Alt dette tidspunkt, vi har skrevet buggy, buggy kode, af mange årsager. Men en af ​​der har været anvendelse af CS50 bibliotek, som selv er bevidst buggy, det lækker hukommelse. Hver gang du har kaldt getString i løbet af de sidste par uger vi beder operativsystemet systemet, Linux, for hukommelsen. Og du har aldrig en gang givet det tilbage. Og det er ikke i praksis, en god ting. 

Og Valgrind, en af ​​de redskaber, der er indført i Pset 4, handler om at hjælpe dig nu finde fejl som. Men heldigvis for Pset 4 behøver du ikke at bruge CS50 biblioteket eller getString. Så eventuelle fejl i forbindelse med hukommelse er i sidste ende kommer til at være din egen. 

Så malloc er mere end blot bekvemt til dette formål. Vi kan faktisk nu løse fundamentalt forskellige problemer, og fundamentalt løse problemer mere effektivt som ugen nul løfte. Indtil videre er dette den mest sexede datastruktur, vi har haft. Og ved datastruktur jeg bare betyde en måde at begrebsliggøre hukommelse på en måde, der går videre end bare at sige, dette er en int, er dette et tegn. Vi kan begynde at klynge ting sammen. 

Så et array lignede dette. Og hvad var nøglen i omkring en array er at det giver dig back-to-back bidder af hukommelse, som hver vil være af samme type, int, int, int, int, eller char, char, fjeldørred, char. Men der er nogle ulemper. Dette er for eksempel et array af størrelse seks. Antag, at du udfylde dette array med seks tal og derefter, uanset grunden, din bruger ønsker at give du et syvende nummer. Hvor skal du sætte det? 

Hvad er løsningen, hvis du har skabt et array på stakken, for eksempel blot med uge to notation som vi introducerede, af kantede parenteser med en række indeni? Nå, du har fået seks numre i disse bokse. Hvad ville dine instinkter være? Hvor ville du ønsker at sætte det? 

Publikum: [uhørligt] 

David J. MALAN: Undskyld? 

Publikum: Sæt det på enden. 

David J. MALAN: Sæt det på enden. Så bare over til højre, uden for denne boks. Hvilket ville være rart, men det viser sig at du ikke kan gøre det. Fordi hvis du ikke har bedt om for dette stykke af hukommelse, det kunne være tilfældigt, at dette bliver brugt af en anden variabel helt. Tænk tilbage en uge eller så når vi lagde ud Zamyla og Davin og Gabe navne i hukommelsen. De var bogstaveligt tilbage til tilbage til tilbage. Så vi kan ikke nødvendigvis lid til, at hvad der nu er herovre er tilgængelig for mig at bruge. 

Så hvad ellers kan du gøre? Tja, når realisere dig har brug for en bred vifte af størrelse syv, du bare kunne skabe en vifte af størrelse syv derefter bruge en for-løkke eller en while-løkke, kopiere det ind i det nye array, og så en eller anden måde bare slippe af med dette array eller bare stoppe med at bruge det. Men det er ikke særlig effektiv. Kort sagt, arrays ikke lade du dynamisk ændre størrelsen på. 

Så på den ene side får du random access, som er forbløffende. Fordi det lader os gøre ting ligesom kløft og erobring, binær søgning, som alle vi har talte om på skærmen her. Men du male dig selv op i et hjørne. Så snart du rammer slutningen af ​​din array, du nødt til at gøre en meget dyr operation eller skrive en hel masse kode nu beskæftige sig med dette problem. 

Så hvad nu hvis vi i stedet havde noget, der hedder en liste, eller en linket liste i særdeleshed? Hvad hvis man i stedet for at have rektangler ryg mod ryg mod ryg, vi har rektangler, der efterlader lidt lidt vrikke værelse i mellem dem? Og selv om jeg har tegnet dette billede eller tilpasset dette billede fra en af ​​teksterne her for at være tilbage til tilbage til tilbage meget velordnet, i virkeligheden, en af ​​disse rektangler kunne være heroppe i hukommelsen. En af dem kunne være her op. En af dem kunne være heroppe, her, og så videre. 

Men hvad nu hvis vi trak, i denne sag, pile at en eller anden måde forbinde disse rektangler sammen? Faktisk har vi set en teknisk inkarnation af en pil. Hvad har vi brugt i de seneste dage, at under hætten, er repræsentativ for en pil? En markør, højre? 

Så hvad nu hvis, i stedet for blot lagring af numre ligesom 9, 17, 22, 26, 34, hvad nu hvis vi ikke gemt kun et nummer, men en pegepind siden af ​​hvert sådant nummer? Så meget som du ville tråd en nål gennem en hel bunke af stof, en eller anden måde kombinationsklausuler ting sammen, ligeledes kan vi med pegepinde, som inkarneret med pile her, slags flette sammen disse individuelle rektangler ved effektivt ved hjælp af en pegepind ved siden af ​​hvert nummer, peger på nogle næste nummer, der peger på, til gengæld nogle næste nummer? Så med andre ord, hvad hvis vi faktisk ønskede at gennemføre noget som dette? Nå desværre disse rektangler, mindst én med 9, 17, 22, og så videre, er disse ikke længere pæne firkanter med enkelte numre. Den nederste, rektangel under 9, for eksempel, repræsenterer, hvad skal være en pegepind, 32 bits. Nu er jeg endnu ikke bekendt med nogen datatype i C, der ikke blot giver dig en int men en pegepind helt. 

Så hvad er løsningen, hvis vi vil at opfinde vores egne svar på dette? Ja? 

Publikum: [uhørligt] 

David J. MALAN: Hvad er det? 

Publikum: Ny struktur. 

David J. MALAN: Ja, så hvorfor vi ikke skabe en ny struktur, eller i C, en struct? Vi har set structs før, hvis kortvarigt, hvor vi behandlet med en studerende struktur som dette, der havde et navn og et hus. I Pset 3 breakout du har brugt en hel flok structs-- GRect og GOvals at Stanford skabt til at klynge oplysninger sammen. Så hvad nu hvis vi tager den samme idé om søgeordene "typedef" og "struct", og derefter nogle elev-specifikke ting, og udvikle dette i følgende: typedef struct node-- og knudepunkt er bare en meget generisk datalogi betegnelse for noget i en datastruktur, en beholder i en datastruktur. En node Jeg hævder vil have en int n helt ligetil, og så lidt mere kryptisk, denne anden linje, struct node * næste. Men færre tekniske termer, hvad er det anden linje kode inde i krøllede parenteser? Ja? 

Publikum: [uhørligt] David J. MALAN: A pointer til en anden node. Så ganske vist syntaks lidt kryptisk. Men hvis du læser det bogstaveligt, næste er navnet på en variabel. Hvad er dens datatype? Det er en lidt vidtløftig denne gang, men det er af typen struct node *. Enhver tid vi har set noget stjerne, at betyder, at det er en pointer til denne datatype. Så næste er tilsyneladende en pointer til en struct node. 

Nu, hvad er en struct node? Nå, mærke, at du ser dem samme ord øverst til højre. Og ja, se dig også ordet "Knude" hernede nederst til venstre. Og det er faktisk bare en bekvemmelighed. Bemærk, at i vores studerende definition der er ordet "studerende" kun én gang. Og det er fordi en elev Formålet var ikke selvrefererende. Der er ikke noget inde i en elev der skal pege på en anden elev, persay. Det ville være slags underlige i den virkelige verden. 

Men med en knude i en forbundet liste, vi ønsker en knude være referentiel en lignende genstand. Og så mærke til ændringen her er ikke bare hvad der er indeni de krøllede parenteser. Men vi tilføje ordet "knude" foroven samt tilføje det til bunden i stedet for "studerende". Og dette er kun en teknisk detalje så, igen, din datastruktur kan være selvrefererende, således at en knude kan pege på en anden sådan node. 

Så hvad er dette i sidste ende kommer til at betyde for os? Tja, en, denne ting inde er indholdet af vores knudepunkt. Denne ting op her, øverst til højre, er bare så det igen, kan vi henvise til os. Og så den yderste ting, selvom noden, er et nyt begreb, måske, det er stadig den samme som studerende, og hvad var under emhætten i SPL. 

Så hvis vi nu ønskede at starte gennemførelsen af ​​denne linkede liste, hvordan kan vi omsætte noget som dette til at kode? Nå, lad os bare se en eksempel på et program, der rent faktisk bruger en linket liste. Blandt dagens uddeling kode er et program kaldet List Zero. Og hvis jeg køre dette skabte jeg en super simpel GUI, Grafisk brugergrænseflade, men det er egentlig bare printf. Og nu har jeg givet mig selv et par menu options-- Slet, Indsæt, Søg, og Traverse. Og Afslut. Disse er blot almindelige operationer på en datastruktur kendt som et link liste. 

Nu Slet vil slette et nummer fra listen. Indsæt kommer til at tilføje et nummer til listen. Søg kommer til at se efter nummer på listen. Og travers er bare en fancy måde sige, gå gennem listen, printe den ud, men det er det. Du må ikke ændre det på nogen måde. 

Så lad os prøve dette. Lad os gå videre og type 2. Og så jeg har tænkt mig at indsætte antal, siger 9. Enter. Og nu er mit program er bare programmeret til at sige, listen er nu 9. Nu, hvis jeg gå videre og gør Indsæt igen, lad mig gå videre og zoome ud og skriv 17. Min liste er nu 9, derefter 17. Hvis jeg gør indsætte igen, lad os springe en. I stedet for 22, som pr det billede, vi har været at se på her, lad mig springe frem og indsæt 26 næste. Så jeg har tænkt mig at skrive 26. Listen er som jeg forventer. Men nu, bare for at se, om denne kode kommer til at være fleksibel, så lad mig nu typen 22, som i det mindste begrebsmæssigt, hvis vi er Holde dette sorteret, som faktisk kommer til at være endnu et mål lige nu, skal gå i mellem 17 og 26. Så jeg trykker på Enter. Ja, det virker. Og så lad mig indsætte sidste pr billedet 34. 

Okay. Så for nu lad mig fastsætte, at Slet og Traverse og Search gør, faktisk fungerer. I virkeligheden, hvis jeg løber Søg, lad os søg efter nummer 22, Enter. Det fandt 22. Så det er, hvad denne Program List Zero gør. 

Men hvad der rent faktisk sker om der implementerer dette? Nå, først jeg måtte have, og faktisk Jeg har en fil kaldet list0.h. Og et eller andet sted i der er denne linje, typedef, struct node så har jeg mine krøllede parenteser, int n, og så struct-- hvad var definitionen? Struct node næste. Så vi har brug for stjernen. Nu teknisk vi kommer ind for vane at trække det her. Du vil måske se lærebøger og online referencer gør det der. Det er funktionelt ækvivalente. I virkeligheden er det lidt mere typisk. Men jeg vil være i overensstemmelse med, hvad vi gjorde sidste gang og gøre dette. Og så til sidst, jeg har tænkt mig at gøre dette. 

Så i en header fil et eller andet sted i list0.h dag er denne struct definition og måske nogle andre ting. I mellemtiden i list0c der kommer til at være et par ting. Men vi vil bare start og ikke afslutte dette. List0.h er en fil jeg vil at medtage i min C-fil. Og så på et tidspunkt er jeg kommer til at have int, main, ugyldig. Og så jeg har tænkt mig at har nogle gøremål er her. Jeg vil også have en prototype, ligesom tomrum, søg, int, n, hvis formål i livet er at søge efter et element. Og så hernede Jeg hævder i dagens kode, ugyldig, søg, int, n, ingen semikolon men åbne krøllede parenteser. Og nu vil jeg en eller anden måde søge til et element på denne liste. Men vi har ikke nok på skærmen endnu. Jeg har faktisk ikke repræsenteret selve listen. Så en måde, vi kunne gennemføre en sammenkædet liste i et program er jeg slags ønsker at gøre noget ligesom erklærer linket liste op her. For overskuelighedens skyld vil jeg gøre denne globale, selvom vi generelt bør ikke gøre det for meget. Men det vil forenkle dette eksempel. Så jeg vil gerne erklære en linket liste op her. Nu, hvordan kan jeg gøre det? 

Her er billedet af en linket liste. Og det gør jeg ikke rigtig ved i det øjeblik, hvor Jeg har tænkt mig at gå om repræsentere så mange ting med blot én variabel i hukommelsen. Men tænk tilbage et øjeblik. Alt dette tidspunkt, vi har haft strenge, som vi derefter viser sig at være arrays af tegn, som vi derefter åbenbaret til bare at være en pegepind til det første tegn i et array af tegn der er nul afsluttes. Så ved denne logik, og med denne billede slags såning dine tanker, hvad behøver vi faktisk skrive i vores kode til at repræsentere en linket liste? Hvor meget af denne information har vi brug at fange i C-kode, ville du sige? Ja? 

PUBLIKUM: Vi har brug for en pointer til en node. David J. MALAN: En markør til et knudepunkt. Især som knudepunkt ville din instinkter være at holde en pointer til? 

PUBLIKUM: Den første node. 

David J. MALAN: Ja, sandsynligvis bare den første. Og bemærk, det første knudepunkt er en anden form. Det er kun halvdelen af ​​struct, fordi det er faktisk kun en pegepind. Så hvad du rent faktisk kan gøre, er erklære en sammenkædet liste at være af typen node *. Og lad os bare kalde det først og initialisere den til null. Så nul igen, er på vej ind i billedet her. Ikke alene er nul bruges som som en særlig returværdi for ting som getString og malloc, null er også nul pointer, manglen på en pointer, hvis du vil. Det betyder bare, intet er endnu her. Nu først, jeg kunne have kaldte dette noget. Jeg kunne have kaldt det "liste" eller en række andre ting. Men jeg kalder det "første", således at det flugter med dette billede. Så ligesom en streng kan være repræsenteret med adressen på sin første byte, så kan en linket liste. Og vi vil se andre data strukturer repræsenteres med blot en pegepind, en 32-bit pil, der peger i det første knudepunkt i strukturen. 

Men lad os nu forventer et problem. Hvis jeg kun huske i mit program adressen af det første knudepunkt, det første rektangel i denne datastruktur, hvad havde bedre være tilfældet om gennemførelse af resten af ​​min liste? Hvad er en afgørende detalje, der kommer at sikre, at dette rent faktisk virker? Og med "rent faktisk virker:" Jeg betyde, meget gerne en streng, lader os gå fra det første tegn i Davin navn til den anden, til den tredje til fjerde, til den bitre ende, hvordan kan vi vide, når vi er i slutningen af en sammenkædet liste, der ligner dette? Når det er nul. Og jeg har repræsenteret denne slags som ligesom en elektrisk ingeniør kraft, med den lille jordforbindelse symbol slags. Men det betyder bare nul i dette tilfælde. Du kan tegne det et vilkårligt antal måder, men denne forfatter skete for at bruge dette symbol her. 

Så længe vi snor alle disse knudepunkter sammen, kun huske hvor den første er, så længe som vi sætter et særligt symbol på den allersidste knude i listen, og vi vil bruge null, fordi det er hvad vi har til rådighed for os, denne liste er færdig. Og selv om jeg kun give dig en pegepind til det første element, du som programmør, kan sikkert adgang til resten af ​​det. Men lad os lade jeres sind vandre en lille smule, hvis de allerede er ikke helt wandered-- hvad er vil være køretiden for finde noget på denne liste? Damn det, det er store O af n, hvilket ikke er dårligt, i retfærdighed. Men det er lineær. Vi har givet op, hvad funktionen arrays ved at flytte flere mod dette billede af dynamisk vævet sammen eller er knyttet knuder? Vi har givet op random access. Et array er rart, fordi matematisk alt er tilbage til tilbage til tilbage til tilbage. Selvom dette billede ser temmelig, og selv selvom det ser ud som disse knudepunkter er pænt fordelt fra hinanden, i virkeligheden de kunne være hvor som helst. OX1, Ox50, Ox123, Ox99 disse knudepunkter kunne være overalt. Fordi malloc ikke tildele hukommelse fra den bunke, men overalt i bunke. Du behøver ikke nødvendigvis vide, at det er vil være tilbage til tilbage til tilbage. Og så dette billede i virkelighedens ikke kommer til at være helt denne smukke. 

Så det kommer til at tage lidt af arbejde for at gennemføre denne funktion. Så lad os gennemføre søgning nu. Og vi vil se sådan en smart måde at gøre dette. Så hvis jeg er en søgefunktion og Jeg får en variabel tal n at kigge efter, jeg har brug for at kende ny syntaks for at kigge indenfor af en struktur, der er pegede på, for at finde n. Så lad os gøre dette. 

Så først vil jeg tænkt mig at gå videre og erklære en node *. Og jeg har tænkt mig at kalde det pointer, blot ved konvention. Og jeg har tænkt mig at initialisere den til først. Og nu kan jeg gøre dette på en række måder. Men jeg har tænkt mig at tage en fælles tilgang. Mens markøren er ikke lig med null, og det er gyldig syntaks. Og det betyder blot gøre følgende, så længe du ikke peger på ingenting. Hvad ønsker jeg at gøre? 

Hvis pointer prik n, lad mig komme tilbage til at equals-- lig hvad? Hvilken værdi jeg leder efter? Selve n, der blev vedtaget i. Så her er en anden funktion C og mange sprog. Selvom struktur kaldet node har en værdi n helt legitimt også have en lokal argument eller variabel kaldet n. Fordi vi selv med menneskers øjne kan skelne at n er formentlig forskellig fra denne n. Fordi syntaksen er anderledes. Du har fået en prik og en pegepind, denne ene har noget sådant. Så det er OK. Det er OK at kalde dem de samme ting. 

Hvis jeg finder du dette, er jeg lyst til at gøre noget ligesom meddele, at vi har fundet n. Og vi vil overlade som en kommentere eller pseudokode kode. Else, og her er den interessant del, hvad ønsker jeg at gøre, hvis den aktuelle node ikke indeholdende N, som jeg bryder mig om? Hvordan kan jeg opnå følgende? Hvis min finger på øjeblik er PTR, og det er peger på uanset først peger på, Hvordan flytter jeg min finger til den næste node i koden? Nå, hvad er brødkrumme, vi er kommer til at følge i denne sag? Publikum: [uhørligt]. David J. MALAN: Ja, så næste. Så hvis jeg gå tilbage til mit kode her, ja, jeg er kommer til at gå videre og sige pointer, som er blot en midlertidig variable-- det er en underlig navn, PTR, men det er ligesom temp-- Jeg har tænkt mig at sætte markøren svarende til, hvad markøren er-- og igen, dette vil være en lille buggy for en moment-- prik næste. Med andre ord, vil jeg tage min finger, som peger på denne knude her, og jeg har tænkt mig at sige, du ved hvad, tage et kig på det næste felt og flytte din finger til hvad det peger på. Og det kommer til at gentag, gentag, gentag. Men når gør min finger stoppe med at gøre noget som helst? Så snart hvad linje kode spark i? Publikum: [uhørligt] David J. MALAN: Hvis punkt, mens pointer er ikke lig med nul. På et tidspunkt min finger vil være at pege på nul og jeg har tænkt mig at indse det er slutningen af ​​denne liste. Nu, dette er en smule hvid løgn om enkelhed. Det viser sig, at selv om vi lige lært denne dot notation af strukturer, pointer er ikke en struct. PTR er hvad? Bare for at være mere nitpicky. Det er en pointer til en node. Det er ikke en knude selv. Hvis jeg havde ingen stjerne her, pegepind absolutely-- det er et knudepunkt. Dette er ligesom uge én erklæring af en variabel, Selv om ordet "node" er nyt. 

Men så snart vi indføre en stjerne, er det nu en pointer til en node. Og desværre kan du ikke bruge dot notation for en pointer. Du er nødt til at bruge pilen notation, som mere slående, er første gang et stykke af syntaks ser intuitiv. Det ser bogstaveligt talt som en pil. Og så det er en god ting. Og hernede bogstaveligt ligner en pil. Så jeg tror, ​​det er den la-- jeg ikke tror, ​​jeg over-begå her-- jeg tror, ​​det er det sidste nye stykke af syntaks, vi kommer til at se. Og heldigvis, det er faktisk lidt mere intuitiv. 

Nu, for dem af jer der måske foretrækker den gamle måde, du kan stadig bruge dot notation. Men som pr mandagens samtale, vi først nødt til at gå der, gå til at adresse og derefter få adgang til området. Så dette er også korrekt. Og helt ærligt, det er en lidt mere pedantisk. Du er bogstaveligt talt sige, dereference markøren og derned. Så fat .n, feltet kaldet n. Men helt ærligt, ingen ønsker at skrive eller læse dette. Og så verden opfundet pilen notation, som er tilsvarende, identiske, det er bare syntaktisk sukker. Så en fancy måde at sige dette ser bedre ud, eller ser enklere. 

Så nu har jeg tænkt mig at gøre en anden ting. Jeg har tænkt mig at sige "pause" når jeg har fundet det så jeg ikke holde udkig efter det. Men dette er kernen af en søgefunktion. Men det er meget nemmere, i ende, ikke at gå gennem koden. Dette er faktisk den formelle gennemførelse af søgning i dagens uddeling kode. Jeg tør sige, at indsatsen ikke er særligt sjovt at gå igennem visuelt, er heller ikke slette, selv men ved slutningen af ​​dagen de koges ned til nogenlunde simple heuristik. 

Så lad os gøre dette. Hvis du vil humor mig her, jeg gjorde bringe en masse stress bolde. Jeg bragte en masse tal. Og kunne vi få et par frivillige at repræsentere 9, 17, 20, 22, 29, og 34? Så det væsentlige alle hvem der er her i dag. Det var en, to, tre, fire, fem, seks personer. Og jeg er blevet bedt om at go-- se, nej en i ryggen hæver deres hænder. OK, en, to, tre, fire, five-- lad mig indlæse balance-- seks. OK, du seks kom op. Vi har brug for andre mennesker. Vi bragte ekstra stress bolde. Og hvis du kunne, for bare et øjeblik, linje jer op lige ligesom dette billede her. 

Okay. Lad os se, hvad er dit navn? 

Publikum: Andrew. 

David J. MALAN: Andrew, du er nummer 9. Rart at møde dig. Værsgo. Publikum: Jen. David J. MALAN: Jen. David. Nummer 17. Ja? 

PUBLIKUM: Jeg er Julia. 

David J. MALAN: Julia, David. Nummer 20. Publikum: kristen. David J. MALAN Christian, David. Nummer 22. Og? 

Publikum: JP. David J. MALAN: JP. Number 29. Så gå videre og få in-- Uh oh. Uh oh. Standby. 20. Er der nogen der har en markør? Publikum: Jeg har en Sharpie. David J. MALAN: Har du en Sharpie? OK. Og nogen der har et stykke papir? Gem forelæsningen. Kom. PUBLIKUM: Vi har fået det. David J. MALAN: Vi fik det? Okay, tak. Her går vi. Var det fra dig? Du har lige reddet dagen. Så 29. Okay. Jeg stavede 29, men OK. Værsgo. Okay, vil jeg give dig pennen tilbage et øjeblik. Så vi har disse folk her. Lad os få en anden. Gabe, du ønsker at spille det første element her? Vi har brug for dig til at pege på disse fine folk. Så 9, 17, 20, 22, sortere af 29, og derefter 34. Har vi mister nogen? Jeg har en 34. Hvor did-- OK, der ønsker at være 34? OK, kom op, 34. Okay, vil dette være værd at klimaks. Hvad er dit navn? 

Publikum: Peter. 

David J. MALAN: Peter, kom op. Okay, så her er en hel masse noder. Hver af jer repræsenterer en af ​​disse rektangler. Og Gabe, det lidt underligt Menneske, repræsenterer først. Så hans pointer er lidt mindre på skærmen end alle andre. Og i dette tilfælde, hver af din venstre hænder vil enten pege ned, derved repræsenterer nul, så blot fravær af en pointer, eller det kommer til at pege ved et knudepunkt ved siden af ​​dig. 

Så lige nu, hvis du pryder jer som på billedet her, gå videre og punkt på hinanden, med Gabe navnlig peger på nummer 9 til at repræsentere listen. OK, og nummer 34, venstre hånd blot skal pege på gulvet. 

OK, så dette er den linkede liste. Så dette er det pågældende scenario. Og ja, det er repræsentativt af en klasse af problemer at du måske forsøge at løse med kode. Du ønsker at i sidste ende indsætte et nyt element i listen. I dette tilfælde vil vi prøve at indsætte nummer 55. Men der vil være forskellige sager at overveje. Og ja, dette vil være en af de store-billede grillbarer her, er, hvad er de forskellige sager. Hvad er anderledes, hvis betingelser eller grene at dit program kan have? 

Nå, det nummer, du forsøger at indsats, som vi ved nu at være 55, men hvis du ikke kender i forvejen, jeg daresay falder i mindst tre mulige situationer. Hvor kan et nyt element være? Publikum: Og enden eller midten. David J. MALAN: I slutningen, i midten, eller i begyndelsen. Så jeg hævder, at der er mindst tre problemer, vi er nødt til at løse. Lad os vælge, hvad der er måske nok den enkleste en, når det nye element hører i begyndelsen. Så jeg har tænkt mig at få koden helt ligesom at søge, som jeg lige har skrevet. Og jeg har tænkt mig at have ptr, som Jeg repræsenterer her med min finger, som sædvanlig. 

Og husk, hvilken værdi vi initialisere ptr til? Så vi initialiseret det til null i første omgang. Men hvad gjorde vi gøre, når vi var inde i vores søgefunktionen? Vi sætter det lig med det første, hvilket ikke betyder, at gøre dette. Hvis jeg sat ptr lig først, hvad skal min hånd virkelig peger på? Højre. Så hvis Gabe og jeg går at være lige store værdier her, er vi nødt til både punkt nummer 9. 

Så dette var begyndelsen af ​​vores historie. Og nu er det bare ligetil, selvom syntaksen er ny. Begrebsmæssigt er det bare lineær søgning. Er 55 svarende til 9? Eller rettere, lad os sige mindre end 9. Fordi jeg forsøger at regne ud, hvor at sætte 55. Mindre end 9, er mindre end 17 mindre end 20, mindre end 22, er mindre end 29, mindre end 34, no. Så nu er vi i tilfælde en af ​​mindst tre. 

Hvis jeg ønsker at indsætte 55 herovre, hvad kodelinjer behov for at få udført? Hvordan dette billede af mennesker har brug for at ændre? Hvad gør jeg med min venstre hånd? Dette bør være nul i første omgang, fordi jeg er i slutningen af ​​listen. Og hvad der skal ske her med Peter, var det? Han er naturligvis vil pege på mig. Så jeg hævder, at der er mindst to linjer kode i prøven koden fra i dag det kommer til at gennemføre denne scenario tilsætte 55 ved halen. Og kunne jeg have nogen hop op og bare repræsenterer 55? Okay, du er den nye 55. 

Så nu, hvad hvis det næste scenarie kommer sammen, og vi ønsker at indsætte på begynder eller lederen af ​​denne liste? Og hvad er dit navn, nummer 55? 

Publikum: Jack. 

David J. MALAN: Jack? OK, rart at møde dig. Velkommen ombord. Så nu vil vi indsætte, siger, nummer 5. Her er det andet tilfælde af tre vi kom op med før. Så hvis 5 hører i starten, lad os se, hvordan vi finder ud af det. Jeg initialisere min ptr pointer til nummer 9 igen. Og jeg indså, åh, 5 er mindre end 9. Så løse dette billede til os. Hvis hænder, Gabe eller Davids eller-- hvad er nummer 9 navn? 

Publikum: Jen. 

David J. MALAN: Jens hands-- hvilke af vores hænder nødt til at ændre? OK, så Gabe peger på, hvad nu? På mig. Jeg er den nye node. Så jeg vil bare slags træk her for at se det visuelt. Og i mellemtiden hvad gør jeg pege det? Stadig hvor jeg peger. Så det er det. Så bare virkelig én linje kode rettelser dette særlige spørgsmål, synes det. Okay, så det er godt. Og kan nogen være en pladsholder for 5? Kom op. Vi får dig næste gang. 

Okay, så nu-- og Som en sidebemærkning navne Jeg gør ikke udtrykkeligt nævner retten nu, Gæt pointer, forgænger pointer og nye pointer, det er blot navnene givet i prøven kode til pegepinde eller mine hænder der er slags peger rundt. Hvad er dit navn? 

Publikum: Christine. 

David J. MALAN: Christine. Velkommen ombord. Okay, så lad os overveje nu en lidt mere irriterende scenario hvorved jeg ønsker at indsætte noget lignende 26 i dette. 20? Hvad? Disse are-- god ting vi har denne pen. Okay, 20. Hvis nogen kunne få et andet stykke papir klar, bare i case-- okay. Åh, interessant. Nå dette er et eksempel af et foredrag bug. OK, så hvad er dit navn igen? Publikum: Julia. David J. MALAN: Julia, kan du pop ud og foregive du var aldrig der? OK, det aldrig sket. Tak. Så formoder, at vi vil indsætte Julia i denne forbundet liste. Hun er tallet 20. Og selvfølgelig er hun kommer til at høre til den begin-- ikke pege på noget endnu. Så din hånd kan slags være ned nul eller nogle skrald værdi. Lad os fortælle hurtig historie. Jeg peger på nummer 5 denne gang. Så tjek jeg 9. Så tjek jeg 17. Så tjek jeg 22. Og jeg indser, ooh, Julia nødt til at gå, før 22. Så hvad skal der ske? Hvis hænder nødt til at ændre? Julias, mine, eller-- hvad er dit navn igen? 

Publikum: kristen. 

David J. MALAN Christian eller? 

Publikum: Andy. 

David J. MALAN: Andy. Kristen eller Andy? Andy har brug for at pege på? Julia. Okay. Så Andy, vil du pege på Julia? Men vent et øjeblik. I historien hidtil, Jeg er den slags en i ladning, i den forstand, at pointer er den ting, der er bevæger sig gennem listen. Vi har måske et navn til Andy, men der er ingen variabel kaldet Andy. Den eneste anden variabel vi har, er første, der har repræsenteret af Gabe. 

Så dette er faktisk grunden således langt har vi ikke behov for dette. Men nu på skærmen er der nævne igen af ​​Pred pointer. Så lad mig være mere præcis. Hvis dette er pointer, jeg havde bedre få lidt mere intelligent om min iteration. Hvis du ikke har noget imod min går igennem her igen, peger her, peger her. Men lad mig få en Pred pointer, forgænger pointer, der er slags peger på element Jeg var lige ved. Så når jeg går her, nu min venstre hånd opdateringer. Når jeg går her min venstre hånd opdateringer. Og nu har jeg ikke blot en pegepind til det element, der går efter Julia, Jeg har stadig en pointer til Andy, elementet før. Så du har adgang til, i det væsentlige, rasp, hvis du vil, til alle de nødvendige pointere. 

Så hvis jeg peger på Andy og jeg også pege på Christian, hvis hænder bør nu påpeges andetsteds? Så Andy kan nu pege på Julia. Julia kan nu pege på Christian. Fordi hun kan kopiere min højre hånds pointer. Og der effektivt sætter dig tilbage til dette sted her. Så kort, selvom det tager os slags evigt faktisk opdatere en linkede liste, indser at operationerne er relativt enkle. Det er af en, to, tre linjer kode i sidste ende. Men svøbt omkring dem linjer kode formentlig er en smule logik, der effektivt spørger, hvor er vi? Er vi ved begyndelsen, midten, eller enden? 

Nu er der sikkert nogle andre operationer, vi kunne gennemføre. Og disse billeder her bare skildrer hvad vi lige gjorde med mennesker. Hvad om fjernelse? Hvis jeg vil, for eksempel, fjerne nummer 34 eller 55, Jeg kunne have den samme slags kode, men jeg har tænkt mig at brug et eller to trin. For hvad er nyt? Hvis jeg fjerner nogen i slutningen, som nummer 55 og derefter 34 hvad også har til at ændre, som jeg gør det? Jeg er nødt til ikke evict-- hvad er dit navn igen? 

Publikum: Jack. 

David J. MALAN: Jack. Jeg er nødt til ikke kun evict-- gratis Jack, så bogstaveligt ringe gratis Jack, eller i det mindste markøren der også, men nu hvad der skal ændres med Peter? Hans hånd bedre start pegende nedad. Fordi så snart jeg ringe gratis på Jack, hvis Peters stadig peger på Jack og derfor vil jeg holde gennemkører listen over og adgang denne pointer, det er når vores gamle segmentering ven fejl kan faktisk sparke. Fordi vi har givet den hukommelse tilbage til Jack. 

Du kan bo der akavet for bare et øjeblik. Fordi vi har bare et par slutoperationerne at overveje. Afskedigelse af lederen af ​​listen, eller beginning-- og denne ene er lidt irriterende. Fordi vi er nødt til at vide, at Gabe er en slags særligt i dette program. Fordi ja, han har sin egen pointer. Han er ikke bare at blive peget på, som er næsten alle andre her. 

Så når hovedet af listen er fjernet, hvis hænder nødt til at ændre nu? Hvad er dit navn igen? 

Publikum: Christine. 

David J. MALAN: Jeg er forfærdelig på navne, tilsyneladende. Så Christine og Gabe, hvis hænder nødt til at ændre når vi forsøger at fjerne Christine, nummer 5, fra billedet? OK, så lad os gøre Gabe. Gabe kommer til at pege, formodentlig på nummer 9. Men hvad næste der skal ske? Publikum: Christine burde være nul [uhørligt]. David J. MALAN: OK, bør man nok make-- Jeg hørte "nul" et eller andet sted. Publikum: Null og fri hende. David J. MALAN: Null hvad? Publikum: Null og fri hende. David J. MALAN: Null og fri hende. Så det er meget let. Og det er perfekt, at du nu sortere af stående der, der ikke tilhører. Fordi du har været afkoblet fra listen. Du har faktisk været forældreløse fra listen. Og så må vi hellere kalde gratis nu på Christine at give denne hukommelse tilbage. Ellers hver gang vi slette en node fra listen vi måske gøre listen kortere, men ikke faktisk faldende størrelse i hukommelsen. Og så hvis vi holde tilføje og tilføjer, tilføjer ting til listen, min computer kan få langsommere og langsommere og langsommere, fordi jeg kører ud af hukommelse, selv om jeg faktisk ikke hjælp Christines bytes hukommelse længere. 

Så i sidste ende er der andre scenarier, af course-- fjernelse i midten, fjernelse i slutningen, som vi så. Men mere interessant Udfordringen er nu vil være at overveje præcis hvad køretiden er. Så ikke alene kan du holde din stykker papir, hvis Gabe, du ville ikke have noget imod at give alle en stress bold. Tak så meget til vores linkede liste frivillige her, hvis du kunne. 

[Applaus] 

David J. MALAN: Okay. Så et par analytisk spørgsmål så, hvis jeg kunne. Vi har set denne notation før, store O og omega, øvre grænser og nedre grænser på køretid nogle algoritme. Så lad os overveje bare et par spørgsmål. 

En, og vi sagde det før, hvad er kørende tid søgen efter en liste i form af store O? Hvad er en øvre grænse på driften tid på at søge en linket liste som gennemført ved vores frivillige her? Det er stort O n, lineær. Fordi i værste fald, elementet, ligesom 55, vi måske være på udkig efter kan være, hvor Jack var, hele vejen i slutningen. Og desværre, i modsætning til et array vi kan ikke få lyst denne gang. Selvom alle vores mennesker var sorteret fra små elementer, 5, hele vejen op til det større element 55, det er normalt en god ting. Men hvad betyder denne antagelse ikke længere tillade os at gøre? Publikum: [uhørligt] David J. MALAN: Sig det igen? PUBLIKUM: Tilfældig adgang. David J. MALAN: Tilfældig adgang. Og til gengæld, der betyder, at vi ikke kan gøre længere bruge svag nuller, intuition, og nærliggende at bruge binær søg og del og hersk. For selvom vi mennesker kunne naturligvis se, at Andy eller Christian var omtrent i midten af ​​listen, Vi ved kun, at som et computer ved at skumme liste fra begyndelsen. Så vi har givet op at random access. 

Så stor O n nu er den øvre bundet på vores søgen tid. Hvad med omega i vores søgen? Hvad er den nedre grænse på at søge for nogle tal på denne liste? Publikum: [uhørligt] David J. MALAN: Sig det igen? Publikum: One. David J. MALAN: One. Så konstant tid. I bedste fald, Christine er faktisk i begyndelsen af ​​listen. Og vi leder efter nummer 5, så vi fandt hende. Så nogen big deal. Men hun er nødt til at være på starten af ​​listen i denne sag. Hvad med noget lignende Delete? Hvad hvis du ønsker at slette et element? Hvad er den øvre grænse og nedre grænse om sletning af noget fra en sammenkædet liste? Publikum: [uhørligt] David J. MALAN: Sig det igen? PUBLIKUM: n. David J. MALAN: n er faktisk den øvre grænse. Fordi der i værste fald forsøger vi at slette Jack, ligesom vi lige gjorde. Han er hele vejen i slutningen. Tager os for evigt, eller n trin for at finde ham. Så det er en øvre grænse. Det er lineær, helt sikkert. Og den bedste sag køretid, eller de nedre grænser i bedste fald ville være konstant tid. Fordi vi måske forsøger at slette Christine og vi bare få heldige hun er i begyndelsen. Vent nu lige lidt. Gabe var også i starten, og vi havde også til at opdatere Gabe. Så det var ikke kun et skridt. Så er det faktisk konstant tid, i bedste fald, at fjerne det mindste element? Det er, selv om det kan være to, tre, eller endda 100 linjer kode, hvis det er det samme antal linjer, ikke i nogen løkke, og uafhængigt af størrelsen af listen, absolut. Sletning elementet på begyndelsen af ​​listen, selv om vi har at gøre med Gabe er stadig konstant tid. 

Så dette virker som en massiv tilbageskridt. Og sikke et spild af tid hvis i uge én og uge nul havde vi ikke kun pseudokode kode, men den faktiske kode at gennemføre noget, der er log basen n, eller log snarere af n, bunden 2, i form af sin køretid. Så hvorfor dælen skulle vi ønsker at starte ved hjælp af noget som en sammenkædet liste? Ja. 

PUBLIKUM: Så du kan tilføje elementer til arrayet. David J. MALAN: Så du kan tilføje elementer til arrayet. Og det er også tematisk. Og vi vil fortsætte med at se dette afvejning, meget ligesom vi har set en trade-off med fusionere slags. Vi kunne virkelig fremskynde søgning eller sortering snarere hvis vi bruger lidt mere plads og have en ekstra bid af en hukommelse eller et array til sammenfletning slags. Men vi bruger mere plads, men vi sparer tid. I dette tilfælde er vi opgiver tid, men vi er opnå fleksibilitet, dynamik hvis du vil, som nok er et positivt træk. 

Vi er også at bruge rummet. I hvilken forstand er en sammenkædet liste dyrere i form af plads end et array? Hvor er den ekstra plads, der kommer fra? Ja? 

Publikum: [uhørligt] pointer. 

David J. MALAN: Ja, vi har også markøren. Så dette er minorly irriterende i, at der ikke længere er Jeg lagring bare en int at repræsentere en int. Jeg gemmer en int og en pointer, som også er 32 bit. Så jeg bogstaveligt talt fordobling mængden af ​​plads involveret. Så det er et trade-off, men det er i tilfælde af int. Antag, at du ikke opbevare int, men formoder hver af disse rektangler eller hver af disse mennesker repræsenterede et ord, et engelsk ord, der kan bestå af fem karakterer, 10 tegn, måske endda mere. Derefter tilføje blot 32 flere bits kan være mindre af en big deal. 

Hvad nu, hvis hver af de studerende i demonstrationen var bogstaveligt studerende structs der har navne og huse og måske telefonnumre og Twitter håndtag og lignende. Så alle felterne vi startede taler om den anden dag, meget mindre af en big deal som vores knudepunkter får mere interessant og store til at bruge, hvad, en ekstra pointer bare at linke dem sammen. Men ja, det er et trade-off. Og ja, koden er mere komplekse, som du vil se ved at skimme igennem det pågældende eksempel. Men hvad nu hvis der var nogle hellige gral her. Hvad hvis vi ikke tage et skridt baglæns, men et kæmpeskridt fremad og gennemføre en data- struktur via hvilken vi kan finde elementer som Jack eller Christine eller andre elementer i dette array i sand konstant tid? Søgning er konstant. Slet er konstant. Indsæt er konstant. Alle disse operationer er konstant. Det ville være vores hellige gral. Og det er, hvor vi vil afhente næste gang. Se dig derefter.