[Musikk spilles] DAVID J. MALAN: All right. Dette er CS50. Dette er uke fem fortsatte, og vi har noen gode nyheter og noen dårlige nyheter. Så gode nyheten er at CS50 lanserer denne fredagen. Hvis du ønsker å bli med oss, hodet til den vanlige URL her. Enda bedre nyheter, ingen forelesning kommende mandag den 13.. Litt mindre bedre nyheter, quiz null er neste onsdag. Flere detaljer kan være finnes på denne nettadressen her. Og i løpet av de neste par dagene vi skal fylle de tomme feltene med hensyn til rommene at vi vil har reservert. Bedre nyheter er at det vil være et kurs-wide gjennomgang sesjon denne kommende Mandag i kveld. Stay tuned til kursets Nettside for plassering og detaljer. Seksjoner, selv om det er en ferie, vil også møte også. Beste nyheten, foredrag neste fredag. Så dette er en tradisjon vi har, i henhold til pensum. Just-- det kommer til å bli fantastisk. Du vil se ting som konstant tidsdatastrukturer og hash tabeller og trær og prøver. Og vi skal snakke om bursdags problemer. En hel haug med ting venter neste fredag. OK. Anyhow. Så husker at vi har vært fokus på dette bildet av hva som er innsiden av våre datamaskinens minne. Så minne eller RAM er der programmene eksistere mens du kjører dem. Hvis du dobbeltklikker en ikonet for å kjøre noen program eller dobbeltklikk på et ikonet for å åpne noen fil, det er lastet fra hard stasjonen eller Solid State-stasjonen inn i RAM, Random Access Memory, der det lever til strømmen er av, laptop lokket lukkes, eller du avslutter programmet. 

Nå som minne, av som du sikkert har 1 gigabyte i disse dager, 2 GB, eller enda mer, er generelt lagt ut for et gitt program i denne typen rektangulær konseptuell modell hvorved vi har stabelen på bunnen og en haug med andre ting på toppen. Saken på toppen vi har sett på dette bildet før, men aldri snakket om er den såkalte tekstsegment. Tekstsegment er bare en fancy måte si nuller og enere som komponere din faktiske kompilert program. 

Så når du dobbeltklikker Microsoft Word på Mac eller PC, eller når du kjører dot slash Mario på en Linux-datamaskin i ditt terminalvindu, nuller og enere som komponerer Word eller Mario lagres midlertidig i datamaskinens RAM i den såkalte tekstsegment for et bestemt program. Nedenfor som går initialisert og uinitialiserte data. Dette er ting som globale variabler, at vi ikke har brukt mange av, men noen ganger har vi hadde globale variabler eller statisk definert strenger som er hardkodet ord som "hallo" som ikke er tatt inn fra brukeren som er hardkodet inn i programmet. 

Nå, ned på bunnen vi har den såkalte stabelen. Og bunken, så langt, vi har vært bruker for hva slags formål? Hva er bunken blitt brukt til? Yeah? 

MÃ¥lgruppe: funksjoner. 

DAVID J. MALAN: For funksjoner? I hvilken forstand for funksjoner? 

PUBLIKUM: Når du ringer en funksjon, den Argumentene er kopiert på stakken. 

DAVID J. MALAN: Nettopp. Når du ringer en funksjon, dens Argumentene er kopiert på stakken. Så noen X-eller Y-eller A-eller B at du sender inn en funksjon er midlertidig satt på den såkalte stabel, akkurat som en av Annenberg Dining Hall skuffer, og også ting som lokale variabler. Hvis foo funksjon eller swap funksjonen har lokale variabler, som temp, de to ende opp på stakken. Nå vil vi ikke snakke for mye om dem, men disse miljøvariabler på bunnen vi så en stund siden, da Jeg ble futzing på tastaturet en dag og jeg begynte å få tilgang til ting som argv 100 eller argv 1000, bare elements-- jeg glemmer den numbers-- men at skulle ikke nås av meg. Vi begynte å se noen funky symboler på skjermen. De var såkalte miljøvariabler som globale innstillinger for min program eller for min datamaskin, ikke relatert til den siste bug som vi snakket om, Shellshock, som har vært plager ganske mange datamaskiner. 

Nå til slutt, i dagens fokus Vi vil til slutt være på haugen. Dette er en annen del av minnet. Og fundamentalt alt dette minnet er de samme tingene. Det er den samme maskinvaren. Vi er bare en slags behandling av ulike klynger byte for ulike formål. Haugen er også kommer til å være der variabler og minne som du ber om fra operativsystemet lagres midlertidig. 

Men det er litt av et problem her, som i bildet innebærer. Vi liksom ha to skip om å kollidere. Fordi som du bruker mer og mer av stabelen, og som vi ser i dag videre, som du bruker mer og mer av haugen, sikkert dårlige ting kan skje. Og ja, vi kan indusere at bevisst eller ubevisst. Så cliffhanger siste gang var dette programmet, som ikke tjener noen funksjonell annet formål enn å demonstrere hvordan du som bad guy kan faktisk ta nytte av bugs i noens program og ta over et program eller en hele datasystemet eller server. Så bare å titte kort, du Legg merke til at hoved nederst tar i kommandolinjen argumenter, som per argv. Og den har et kall til en funksjon f, egentlig en navnløs funksjon kalt f, og det er forbikjøring i argv [1]. 

Så uansett hva ordet brukeren taster inn på ledeteksten etter dette programmets navn, og så denne vilkårlig funksjon opp toppen, f, tar i en streng, AKA char *, som vi har begynt å diskutere, og det bare kaller det "bar". Men vi kan kalle det noe. Og så erklærer inne av f, en rekke tegn kalt C-- 12 slike tegn. 

Nå, etter den historien jeg fortalte et øyeblikk siden, hvor i minnet er c, eller er de 12 chars kommer til å ende opp? Bare for å være klar. Yeah? 

PUBLIKUM: PÃ¥ stabelen. 

DAVID J. MALAN: På stabelen. Så c er en lokal variabel. Vi ber om 12 tegn eller 12 bytes. De kommer til å ende opp på den såkalte stabelen. Nå endelig er denne annen funksjon det er faktisk ganske nyttig, men vi har egentlig ikke brukt det selv, strncopy. Det betyr streng kopi, men bare n bokstaver, n tegn. Så n tegn vil være kopiert fra bar til c. Og hvor mange? Lengden på bar. Så med andre ord, at én linje, strncopy, kommer til å kopiere effektivt bar i til c. 

Nå, bare for å slags forutse Moralen i denne historien, hva er potensielt problematisk her? Selv om vi sjekker lengden av bar og føre det inn i strncopy, hva er din gut forteller deg er fremdeles ødelagt om dette programmet? Yeah? 

PUBLIKUM: Inkluderer ikke rom for nulltegn. DAVID J. MALAN: Inkluderer ikke rom for nulltegn. Potensielt, i motsetning til i tidligere praksis vi ikke engang har så mye som et pluss 1 til imøtekomme den null karakter. Men det er enda verre enn det. Hva annet skal vi unnlate å gjøre? Yeah? 

PUBLIKUM: [uhørbart] DAVID J. MALAN: Perfect. Vi har hardkodet 12 ganske vilkårlig. Det er ikke så mye problem, men faktum at vi ikke engang å sjekke om lengden på baren er mindre enn 12, i så fall kommer det til å være trygt å sette det inn i minnet kalt c at vi har tildelt. Faktisk, hvis bar er som 20 tegn lang, denne funksjon synes å være å kopiere 20 tegn fra bar til c, og dermed tar minst 8 byte at det ikke skal være. Det er implikasjonen her. 

Så kort sagt, ødelagte program. Ikke en så stor avtale. Kanskje du får en segmentering feil. Vi har alle hatt bugs i programmer. Vi alle kan ha bugs i programmer akkurat nå. Men hva er implikasjonen? Vel, her er en zoomet inn versjonen av det bildet av min datamaskinens minne. Dette er bunnen av bunken min. Og ja, helt nederst er det som er kalt forelder rutine stack, fancy måte å si at det viktigste. Slik at den som kalles funksjonen f som vi snakker om. Så dette er bunnen av bunken. Returadressen er noe nytt. Det har alltid vært der, alltid vært i det bildet. Vi kalte bare aldri oppmerksomhet til det. Fordi det blir slik vi c fungerer er at når en funksjonskall hverandre ikke bare gjør argumentene til at funksjon bli skjøvet inn på stabelen, ikke bare gjøre funksjonens lokale variablene bli skjøvet inn på stabelen, noe som kalles en returadresse også blir satt på stakken. Nærmere bestemt, hvis viktigste samtalene foo, da hoved sin egen adresse i minnet, okse noe, effektivt blir satt på stakken slik at når f er gjort utfører det vet hvor du skal hoppe tilbake til i teksten segmentet for å kunne fortsette å utføre. 

Så hvis vi er her konseptuelt, i hoved, deretter f blir kalt. Hvordan f vite hvem til håndkontrollen tilbake? Vel, denne lille brødsmule i rødt her, kalt returadresse, det bare sjekker, hva er det returadresse? Å, la meg hoppe tilbake til hoved her. Og det er litt av en overforenkling, fordi de nuller og enere for hoved er teknisk her oppe i tech-segmentet. Men det er tanken. f bare må vite hva til der kontroll til slutt går tilbake. 

Men måten datamaskiner har lenge lagt ut ting som lokale variabler og Argumentene er som dette. Så på toppen av dette bildet i blått er stabelen rammen for f, så alt av minnet som f spesifikt er bruker. Så tilsvarende, legge merke til at Baren er i dette bildet. Bar var sitt argument. Og vi hevdet at argumentene til funksjoner bli skjøvet inn på stabelen. Og c, er selvfølgelig også i dette bildet. 

Og bare for notasjonsmessig, merke øverst i venstre hjørne er hva som ville være c brakett 0 og så litt ned mot høyre er c brakett 11. Så med andre ord, kan du forestille deg at det er et rutenett av bytes Det første av disse er Øverst til venstre bunnen av som er den siste av disse 12 bytes. 

Men nå prøve å spole fremover. Hva er i ferd med å skje hvis vi passerer i en streng søyle som er lengre enn c? Og vi er ikke å sjekke om det er faktisk lengre enn 12 år. Som en del av dette bildet kommer til å bli overskrevet av byte 0, 1, 2, 3, dot dot dot, 11, og deretter dårlig, 12, 13 til 19? Hva kommer til å skje her, hvis du slutte fra bestilling at c brakett 0 er på toppen og c brakett 11 er liksom ned til høyre? Yeah? 

PUBLIKUM: Vel, det kommer å overskrive char * bar. 

DAVID J. MALAN: Ja, det ser ut som du kommer til å overskrive char * bar. Og enda verre, hvis du sender i en veldig lang streng, kan du selv overskrive hva? Returadressen. Som igjen er akkurat som en brødsmule å fortelle programmet hvor å gå tilbake til når f gjøres å bli kalt. 

Så hva skurkene vanligvis gjør er hvis de kommer over et program at de er nysgjerrig på om er utnyttes, buggy på en slik måte at han eller hun kan ta nytte av at bug, generelt de ikke får dette riktig første gang. De nettopp begynner å sende, f.eks tilfeldige strenger inn i programmet, enten på tastaturet, eller ærlig de trolig skrive et lite program for å bare automatisk generere strenger, og begynne banging på programmet ved sender i mange forskjellige innganger ved forskjellige lengder. 

Så snart programmet krasjer, det er en fantastisk ting. Fordi det betyr at han eller hun har oppdaget det som sannsynligvis er faktisk en bug. Og så de kan få mer smart og begynne å fokusere mer snevert om hvordan du kan utnytte at bug. Spesielt hva han eller hun kan gjøre er å sende, i beste fall, hallo. Ingen big deal. Det er en streng som er tilstrekkelig kort. Men hva hvis han eller hun sender, og vi vil generalisere det som, angrep code-- så nuller og de som gjør ting som rm-rf, som fjerner alt fra harddisken eller sende spam eller annen måte angripe maskinen? 

Så hvis hver av disse bokstavene A bare representerer, konseptuelt, angrep, angrep, angrep, angrep, noen dårlig kode at noen andre skrev, men hvis den personen er smart nok å ikke bare inkludere alle av de RM-rfs, men også har hans eller hennes siste bytes være et tall som tilsvarer til adressen til sitt eller hennes egen angrepskode at han eller hun gikk i bare ved å gi det ved ledeteksten, du effektivt kan lure datamaskinen til merke når f er gjort utførende, oh, er det på tide for meg å hoppe tilbake til den røde returadresse. Men fordi han eller hun har en eller annen måte overlappet som returadresse med sitt eget nummer, og de er smarte nok å ha konfigurert som nummer til å referere, som du se i super topp venstre hjørne der, den faktiske adresse i datamaskinens minne om noen av deres angrep kode, en bad guy kan lure datamaskinen til å utføre sin egen kode. 

Og den koden, igjen, kan være hva som helst. Det er generelt kalt shell-kode, som er bare en måte å si at det ikke er generelt noe så enkelt som rm-rf. Det er faktisk noe som Bash, eller en faktisk program som gir ham eller hennes programmakontrollen for å utføre noe annet som de vil. Så kort sagt, alt dette stammer fra det enkle faktum at denne feilen er involvert ikke sjekker grensene for klyngen. Og fordi måten datamaskiner arbeid er at de bruke stabelen fra effektivt, konseptuelt, nederst på opp, men deretter elementene du skyver på stakken vokse toppen og ned, dette er utrolig problematisk. Nå finnes det måter å omgå dette. Og ærlig talt, det finnes språk som å omgå dette. Java er immune, f.eks til dette spesielle problemet. Fordi de ikke gi deg tips. De vil ikke gi deg direkte minneadresser. Så med denne kraften som vi har å røre noe i minnet vi ønsker kommer riktignok stor risiko. 

Så hold et øye. Hvis, ærlig, i månedene eller årene som kommer, når som helst du lese om noen utnyttelse av et program eller en server, Hvis du noen gang ser et snev av noe som en buffer overflow-angrep, eller stack overflow er en annen type for angrep, ligner i ånden, mye som inspirerer nettstedets nevne, hvis du vet det, det er alle snakker om bare fylte størrelsen noen tegn matrise eller noen matrise mer generelt. Eventuelle spørsmål, da, om dette? Ikke prøv dette hjemme. 

Greit. Så malloc så langt har vært vår nye venn i at vi kan tildele minne at vi ikke nødvendigvis vet i forhånd at vi ønsker slik at vi ikke har til hard kode inn i vårt programnummer som 12. Når brukeren forteller oss hvor mye data han eller hun ønsker å legge inn, vi kan malloc så mye minne. 

Så malloc det viser seg, til grad vi har brukt det, eksplisitt siste gang, og deretter dere har brukt det for getstring uvitende for flere uker, alle av malloc minne kommer fra den såkalte heap. Og dette er grunnen getstring, f.eks kan tildele minne dynamisk uten å vite hva du er kommer til å skrive på forhånd, hånd du tilbake en peker til dette minnet, og at minnet er fortsatt ditt for alltid, selv etter getstring avkastning. Fordi tilbakekalling tross alt at stack er stadig går opp og ned, opp og ned. Og så snart det går ned, betyr at en hvilken som helst minne denne funksjonen som brukes skal ikke brukes av noen andre. Det er søppel verdier nå. 

Men haugen er her oppe. Og hva er fint om malloc er at når malloc tildeler minne opp her, det er ikke påvirket, for meste av stabelen. Og så noen funksjon kan få tilgang minne som har blitt malloc'd, selv av en funksjon som getstring, selv etter at den er returnert. 

Nå er det motsatte av malloc gratis. Og ja, den regelen du må begynne å ta i bruk er noen, noen, noen gang du bruker malloc du må selv bruke gratis, til slutt, på den samme pekeren. Hele denne tiden har vi vært å skrive buggy, buggy kode, av mange grunner. Men en av hvilke har vært bruker CS50 biblioteket, som selv er bevisst buggy, lekker det minne. Hver gang du har kalt getstring i løpet av de siste ukene vi ber drifts system, Linux, for minnet. Og du har aldri en gang gitt det tilbake. Og dette er ikke, i øve, en god ting. 

Og Valgrind, en av de verktøy introdusert i PSet 4, handler om å hjelpe deg nå finne bugs sånn. Men heldigvis for PSet 4 du ikke trenger å bruke CS50 biblioteket eller getstring. Så noen bugs relatert til minnet er slutt kommer til å være din egen. 

Så malloc er mer enn bare fordelaktig for dette formålet. Vi kan faktisk nå løse fundamentalt forskjellige problemer, og fundamentalt løse problemer mer effektivt som per uke null løfte. Så langt er dette den mest sexy datastruktur vi har hatt. Og ved datastruktur Jeg mener en måte å konseptualisere minne på en måte som går utover bare å si: Dette er en int, dette er et tegn. Vi kan begynne å klase ting sammen. 

Så en rekke så ut som dette. Og hva var nøkkelen i omtrent en matrise er at det gir deg back-to-back biter av hukommelse, hvor hver av disse kommer til å være av samme type, int, int, int, int, eller røye, røye, sjørøye, røye. Men det er noen ulemper. Dette er for eksempel en matrise av størrelse seks. Tenk deg at du fyller denne matrisen med seks tall og da, uavhengig av hvilken grunn, ditt brukeren ønsker å gi du en syvende nummer. Hvor setter du det? 

Hva er løsningen hvis du har opprettet en rekke på stakken, for eksempel, bare med uken to notasjon som vi innført, av hakeparenteser med et tall inni? Vel, du har seks Tallene i disse boksene. Hva ville instinktene dine være? Hvor ville du ønsker å plassere den? 

PUBLIKUM: [uhørbart] 

DAVID J. MALAN: Sorry? 

PUBLIKUM: Sett det på slutten. 

DAVID J. MALAN: Sett det på slutten. Så bare over til høyre, Utsiden av denne boksen. Som ville være fint, men det viser seg at du ikke kan gjøre det. Fordi hvis du ikke har bedt om for denne del av minnet, det kan være tilfeldig at dette brukes av en annen variabel helt. Tenk tilbake en uke eller så når vi lagt ut Zamyla og Davin og Gabes navn i minnet. De var bokstavelig talt rygg mot rygg mot rygg. Så vi kan ikke nødvendigvis Stol på at hva som står over her er tilgjengelig for meg å bruke. 

Så hva annet kan du gjøre? Vel, en gang innser du trenger en matrise av størrelse syv, du kan bare lage en matrise av størrelse syv deretter bruke en for løkke eller en stund loop, kopiere den inn i det nye utvalget, og deretter en eller annen måte bare bli kvitt denne matrisen eller bare slutte å bruke det. Men det er ikke spesielt effektiv. Kort sagt, gjør arrays ikke la du dynamisk endre størrelsen. 

Så på den ene siden du får random access, noe som er fantastisk. Fordi det lar oss gjøre ting som Splitt og hersk, binære søk, som alle vi har snakket om på skjermen her. Men du male selv inn i et hjørne. Så snart du treffer slutten av array, du trenger å gjøre en veldig kostbar operasjon eller skrive en hel haug med kode å nå håndtere det problemet. 

Så hva om stedet vi hadde noe som kalles en liste, eller en lenket liste spesielt? Hva om i stedet for å rektangler rygg mot rygg til rygg, vi har rektangler som forlater litt litt slingringsmonn i mellom dem? Og selv om jeg har trukket dette bilde eller tilpasset dette bildet fra en av tekstene her for å være tilbake til back to back veldig ryddig, i virkeligheten, en av disse rektangler kunne være her oppe i minnet. En av dem kunne være her oppe. En av dem kan være her oppe, over her, og så videre. 

Men hva om vi trakk, i dette tilfellet, piler som liksom knytte disse rektangler sammen? Faktisk har vi sett en teknisk inkarnasjonen av en pil. Hva har vi brukt i nyere dager som, under panseret, er representativ for en pil? En peker, ikke sant? 

Så hva om, i stedet for bare lagring av tall, som 9, 17, 22, 26, 34, hva om vi lagret ikke bare et tall, men en peker ved siden av hvert slikt nummer? Slik at mye som du ville tråden en nålen gjennom en hel haug med stoff, liksom binde ting sammen, kan likeledes vi med pekere, som inkarnert med piler her, slags veve sammen disse individuelle rektangler ved effektivt å bruke en peker ved siden av hvert nummer som peker på noen neste nummer, som peker mot, i sin tur, et neste nummer? Så med andre ord, hva hvis vi faktisk ønsket å gjennomføre noe sånt som dette? Vel dessverre, disse rektangler, i det minste den med 9, 17, 22, og så videre, er disse ikke lenger fine firkanter med enkle tall. Bunnen, rektangel under 9, for eksempel, representerer hva skal være en peker, 32 biter. Nå er jeg ikke ennå klar over noen datatype i C som gir deg ikke bare en int men en peker helt. 

Så hva er løsningen hvis vi ønsker å oppfinne vår egen svar på dette? Yeah? 

PUBLIKUM: [uhørbart] 

DAVID J. MALAN: Hva er det? 

PUBLIKUM: Ny struktur. 

DAVID J. MALAN: Ja, så hvorfor Kan vi ikke lage en ny struktur, eller i C, en struct? Vi har sett structs før, hvis kort, hvor vi jobbet med en student struktur som dette, som hadde et navn og et hus. I PSet tre avslapnings du brukte en hel haug med structs-- GRect og GOvals at Stanford opprettet for å klynge informasjonen sammen. Så hva om vi tar den samme ideen om søkeordene "typedef" og "struct", og litt til student-spesifikke ting, og utvikle dette i følgende: typedef struct node-- og node er bare en svært generisk informatikk begrep for noe i en datastruktur, en beholder i en datastruktur. En node jeg hevder er nødt til en int n, helt grei, og deretter litt mer kryptisk, denne andre linje, struct node * neste. Men i mindre tekniske termer, hva er det andre linjen kode inne i klammeparentes? Yeah? 

PUBLIKUM: [uhørbart] DAVID J. MALAN: A Peker til en annen node. Så riktignok, syntaks litt kryptisk. Men hvis du leser det bokstavelig talt, neste er navnet på en variabel. Hva er dens datatype? Det er litt ordrik denne gangen, men det er av type struct node *. Hver gang vi har sett noe stjerne, som betyr at det er en peker til den datatypen. Så neste er tilsynelatende en peker til en struct node. 

Nå, hva er en struct node? Vel, du merker ser dem samme ordene øverst til høyre. Og ja, du også se ordet "Node" her nede nederst til venstre. Og dette er faktisk bare en bekvemmelighet. Legg merke til at i vår student definisjon det er ordet "student" bare én gang. Og det er fordi en student Målet var ikke selv-referensiell. Det er ingenting inne i en student som må peke til en annen student, persay. Det ville være slags rart i den virkelige verden. 

Men med en node i et koblet liste, ønsker vi en node å være referanse til en lignende gjenstand. Og så merke endringen her er ikke akkurat hva som er inne i klammeparentes. Men vi legge til ordet "node" på toppen, samt legge den til bunnen i stedet for "student". Og dette er bare en teknisk detalj slik at, igjen, din datastruktur kan være selvrefererende, slik at en node kan peke til en annen slik node. 

Så hva er dette til slutt kommer til å bety for oss? Vel, en, dette ting inni er innholdet i vårt node. Denne tingen her oppe, øverst til høyre, er bare så som, igjen, kan vi referere til oss selv. Og så den ytterste ting, selv om node er et nytt begrep, kanskje, er det fortsatt det samme som student og hva var under panseret i SPL. 

Så hvis vi nå ønsket å starte implementere denne lenket liste, hvordan kan vi oversette noe som dette å kode? Vel, la oss bare se en eksempel på et program som faktisk bruker en lenket liste. Blant dagens distribusjon kode er et program som heter List Zero. Og hvis jeg kjører dette jeg laget en super enkel GUI, grafisk brukergrensesnitt, men det er egentlig bare printf. Og nå har jeg gitt meg selv noen meny options-- Slett, Sett, Søk, og Traverse. Og sluttet. Dette er bare vanlige operasjoner på en datastruktur kjent som en koblingsliste. 

Nå Slett kommer til å slette et nummer fra listen. Sett inn kommer til å legge et nummer til listen. Søk kommer til å se for nummeret i listen. Og traversen er bare en fancy måte å si, gå gjennom listen, skrive det ut, men det er det. Ikke endre det på noen måte. 

Så la oss prøve dette. La oss gå videre og type 2. Og så kommer jeg til å sette inn nummeret, sier ni. Enter. Og nå mitt program er bare programmert til å si, er listen nå ni. Nå, hvis jeg går videre og setter inn igjen, la meg gå videre og zoome ut og skriv inn 17. Nå er min liste er 9, da 17. Hvis jeg gjør setter inn igjen, la oss hoppe over en. I stedet for 22, som per bildet vi har vært å se på her, la meg hoppe fremover og sett 26 neste. Så jeg kommer til å skrive 26. Listen er som jeg forventer. Men nå, bare for å se om denne koden kommer til å være fleksibel, la meg nå typen 22, som i det minste konseptuelt, hvis vi er Holder dette sortert, som er faktisk kommer til å bli nok et mål akkurat nå, bør gå i mellom 17 og 26. Så jeg trykker Enter. Faktisk fungerer det. Og så nå la meg sette inn siste, per bildet, 34. 

Greit. Så for nå la meg bestemme at Slett og Traverse og søk gjør det, faktisk fungerer. Faktisk, hvis jeg kjører søk, la oss søke etter nummeret 22, Enter. Det funnet 22. Så det er det denne Programlisten Zero gjør. 

Men hva som faktisk skjer på som implementerer dette? Vel, første jeg kan ha, og faktisk Jeg har en fil som heter list0.h. Og et sted der dette er linje, typedef, struct node, så jeg har mine klammeparentes, int n, og deretter struct-- hva var definisjonen? Struct node neste. Så vi trenger stjernen. Nå teknisk får vi inn vane med å tegne den her. Du kan se lærebøker og online referanser gjør det der. Det er tilsvarende funksjonalitet. Faktisk er dette en litt mer typisk. Men jeg skal være i samsvar med hva vi gjorde sist gang og gjøre dette. Og så til slutt, jeg kommer til å gjøre dette. 

Så i en header-fil et sted, i list0.h i dag er dette struct definisjon, og kanskje noen andre ting. I mellomtiden i list0c det er kommer til å være et par ting. Men vi kommer til å like starte og ikke fullføre dette. List0.h er en fil jeg vil ha å ta med i C-fil. Og så på et tidspunkt jeg er kommer til å ha int, main, ugyldig. Og så kommer jeg til å har noen to-do er her. Jeg er også tenkt å ha en prototype, som ugyldig, søk, int, n, er hvis formål i livet for å søke etter et element. Og deretter ned her jeg hevder i dagens kode, ugyldig, søk, int, n, ingen semikolon men åpne klammeparentes. Og nå vil jeg liksom søke for et element i denne listen. Men vi har ikke nok informasjon på skjermen ennå. Jeg har faktisk ikke representerte selve listen. Så en måte vi kunne implementere en lenket liste i et program er jeg slags ønsker å gjøre noe som erklærer lenket liste opp her. For enkelhets skyld kommer jeg til å gjøre denne globale, selv om vi generelt bør ikke gjøre dette for mye. Men det vil forenkle dette eksempel. Så jeg ønsker å erklære en lenket liste opp her. Nå, hvordan kan jeg gjøre det? 

Her er bildet av en lenket liste. Og jeg egentlig ikke vet i øyeblikket hvordan Jeg kommer til å gå om å representere så mange ting med bare ett variabel i minnet. Men tenker tilbake et øyeblikk. Hele denne tiden vi har hatt strenger, som vi deretter avslørt å være matriser av tegn, som vi deretter avslørt å bare være en peker til det første tegnet i en rekke tegn som er null terminert. Så ved den logikken, og med dette Bildet slags seeding dine tanker, Hva trenger vi egentlig skrive i vår kode for å representere en lenket liste? Hvor mye av denne informasjonen vi trenger gjøre å fange i C-kode, vil du si? Yeah? 

PUBLIKUM: Vi trenger en peker til en node. DAVID J. MALAN: En peker til en node. I særdeleshet, som node ville din instinkter være å holde en peker til? 

PUBLIKUM: Den første noden. 

DAVID J. MALAN: Yeah, trolig bare den første. Og legg merke til, den første node er en annen form. Det er bare halve størrelsen av struct, fordi det er faktisk bare en peker. Så hva du faktisk kan gjøre er å erklære en lenket liste for å være av typen node *. Og la oss bare kalle det første og initialisere den til null. Så null, igjen, er kommer inn i bildet her. Ikke bare er null brukt som som en spesiell returverdi for ting som getstring og malloc, er null også null pekeren, mangelen på en peker, hvis du vil. Det betyr bare ingenting er ennå her. Nå først, jeg kunne har kalte dette noe. Jeg kunne ha kalt det "liste" eller hvilket som helst antall av andre ting. Men jeg kaller det "første", slik at det linjer med dette bildet. Så akkurat som en streng kan være representert med adressen til den første byte, så kan en lenket liste. Og vi vil se andre data strukturer være representert med bare ett pekeren, en 32-bit pilen peker på det første knutepunktet i strukturen. 

Men la oss nå forutse et problem. Hvis jeg bare huske i mitt program adressen av den første node, den første rektangel i dette datastrukturen, det hadde bedre være tilfelle om gjennomføringen av resten av listen min? Hva er en nøkkel detalj som kommer å sikre at dette faktisk fungerer? Og med "faktisk fungerer" Jeg mener, omtrent som en streng, lar oss gå fra det første tegnet i Davin navn til den andre, til den tredje, til fjerde, helt til enden, hvordan vet vi når vi er på slutten av en lenket liste som ser slik ut? Når det er null. Og jeg har representert denne typen som som elektroingeniør makt, med den lille jording symbol, av former. Men det betyr bare null i dette tilfellet. Du kan tegne det en rekke måter, men denne forfatteren skjedd å bruke dette symbolet her. 

Så lenge vi strenger alle disse nodene sammen, bare huske hvor den første er, så lenge som vi setter et spesielt symbol på den aller siste node i listen, og vi vil bruke null, fordi det er hva vi har tilgjengelig for oss, listen er fullstendig. Og selv om jeg bare gi deg en peker til det første elementet, du, programmerer, kan sikkert få tilgang til resten av det. Men la oss la ditt sinn vandre litt, hvis de allerede ikke er ganske wandered-- hva som er kommer til å være kjøretiden å finne noe i denne listen? Pokker, det er stor O av n, som ikke er dårlig, i rettferdighet. Men det er lineær. Vi har gitt opp hva funksjonen av matriser ved å flytte mer mot dette bildet av dynamisk vevd sammen eller koblede noder? Vi har gitt opp random access. En rekke er fint fordi matematisk alt er rygg mot rygg mot rygg mot rygg. Selv om dette bildet ser pen, og selv selv om det ser ut som disse nodene er pent plassert fra hverandre, i virkeligheten de kan være hvor som helst. OX1, Ox50, Ox123, Ox99, disse Nodene kan være hvor som helst. Fordi malloc gjør allokere minne fra haugen, men hvor som helst i haugen. Du trenger ikke nødvendigvis vet at det er kommer til å være tilbake til rygg mot rygg. Og så dette bildet i virkelighetens ikke kommer til å være ganske dette pen. 

Så det kommer til å ta en bit av arbeide for å implementere denne funksjonen. Så la oss gjennomføre søk nå. Og vi vil se en slags smart måte å gjøre dette på. Så hvis jeg er en søkefunksjon og Jeg får en variabel, heltall n skal se etter, jeg trenger å vite nye syntaksen for å se innsiden av en struktur som finnes pekte på, for å finne n. Så la oss gjøre dette. 

Så først skal jeg gå videre og erklære en node *. Og jeg kommer til å kalle det pekeren, bare ved konvensjonen. Og jeg kommer til å initialisere den til først. Og nå kan jeg gjøre dette på en rekke måter. Men jeg kommer til å ta en felles tilnærming. Mens pekeren er ikke lik null, og det er gyldig syntaks. Og det betyr bare gjøre følgende, så lenge du ikke peker på noe. Hva ønsker jeg å gjøre? 

Hvis pekeren dot n, la meg komme tilbake til det, tilsvarer equals-- hva? Hvilken verdi Jeg leter etter? Selve n som ble vedtatt i. Så her er en annen funksjon av C og mange språk. Selv om strukturen som kalles noden har en verdi n, helt legitimt til også å ha en lokal argument eller variabel kalt n. Fordi selv vi, med menneskelige øyne kan skille at dette n er formodentlig forskjellig fra dette n. Fordi syntaksen er annerledes. Du har fått en prikk og en peker, mens denne har ikke noe slikt. Så dette er OK. Det er OK å kalle dem de samme tingene. 

Hvis jeg finner du dette, er jeg kommer til å ønske å gjøre noe som kunngjøre at vi har funnet n. Og vi skal la det som en kommentere eller pseudokode. Else, og her er den interessante delen, hva ønsker jeg å gjøre hvis den aktuelle noden ikke inneholder n at jeg bryr meg om? Hvordan oppnår jeg følgende? Hvis fingeren på øyeblikket er PTR, og det er peker på uansett først peker på, hvordan flytter jeg min finger til neste node i kode? Vel, hva er brødsmule vi er kommer til å følge i dette tilfellet? PUBLIKUM: [uhørlig]. DAVID J. MALAN: Ja, så neste. Så hvis jeg går tilbake til min koden her, ja, jeg er kommer til å gå videre og si pekeren, som er bare en midlertidig variable-- det er en merkelig navn, PTR, men det er akkurat som temp-- Jeg kommer til å sette pekeren lik uansett pekeren er-- og igjen, dette kommer til å bli en litt buggy for en moment-- prikk ved. Med andre ord, jeg kommer til å ta min finger som peker på denne noden her, og jeg kommer til å si, vet du hva, ta en titt på neste felt og beveger fingeren til hva det peker på. Og dette kommer til å gjenta, gjenta, gjenta. Men da gjør min finger slutte å gjøre noe som helst? Så snart det kodelinje spark i? PUBLIKUM: [uhørbart] DAVID J. MALAN: Hvis punkt mens pekeren er ikke lik null. På et tidspunkt min milli kommer til å peke på null og jeg kommer til å realisere det er slutten av denne listen. Nå er dette en lite hvit løgn for enkelhet. Det viser seg at selv om vi bare lært dette dot notasjon for konstruksjoner, er pekeren ikke en struct. PTR er hva? Bare for å være mer pirkete. Det er en peker til en node. Det er ikke en node i seg selv. Hvis jeg hadde ingen stjerne her, peker absolutely-- det er en node. Dette er som uke en erklæring av en variabel, selv om ordet "node" er nye. 

Men så snart vi innføre en stjerne, er det nå en peker til en node. Og dessverre kan du ikke bruke dot notasjon for en peker. Du må bruke pilen notasjon, som påfallende, er første gang en brikke syntaks ser intuitivt. Dette ser bokstavelig talt ut som en pil. Og så det er en god ting. Og her nede bokstavelig talt ser ut som en pil. Så jeg tror det er la-- jeg ikke tror jeg over-begå her-- jeg tror det er det siste nye stykke syntaks vi kommer til å se. Og heldigvis er det faktisk en litt mer intuitiv. 

Nå, for de av dere som kanskje foretrekker den gamle måten, du kan fortsatt bruke dot notasjon. Men som per mandagens samtale, må vi først trenger å gå dit, gå til den adresse, og deretter få tilgang til feltet. Så dette er også korrekt. Og ærlig talt, dette er en litt mer pedantisk. Du er bokstavelig talt si, dereferanse markøren og gå dit. Så grip .N, feltet kalt n. Men ærlig, ønsker ingen å skrive eller lese dette. Og så verden oppfunnet pilen notasjon, som er tilsvarende, identiske, det er bare syntaktisk sukker. Så en fancy måte å si dette ser bedre ut, eller ser enklere. 

Så nå er jeg kommer til å gjøre en annen ting. Jeg kommer til å si "break" når jeg har fant det så jeg ikke holde utkikk etter den. Men dette er hovedpunkt av en søkefunksjon. Men det er mye enklere, i ende, for ikke å gå gjennom koden. Dette er faktisk den formelle gjennomføringen søk i dagens distribusjons kode. Jeg tør si at innsatsen ikke er spesielt morsomt å gå gjennom visuelt, og heller ikke er slette, selv selv ved slutten av dagen de koker ned til ganske enkle heuristikk. 

Så la oss gjøre dette. Hvis du vil humor meg her, jeg gjorde ta med en haug med stress baller. Jeg tok en haug med tall. Og kan vi få bare noen få frivillige å representere 9, 17, 20, 22, 29, og 34? Så egentlig alle hvem som er her i dag. Det var en, to, tre, fire, fem, seks personer. Og jeg har blitt bedt om å Vær så god se, ingen en på baksiden hever sine hender. OK, en, to, tre, fire, five-- la meg laste balance-- seks. OK, du seks Kom opp. Vi trenger andre mennesker. Vi tok ekstra stress baller. Og hvis du kunne, for bare et øyeblikk, linje dere opp bare som dette bildet her. 

Greit. La oss se, hva heter du? 

PUBLIKUM: Andrew. 

DAVID J. MALAN: Andrew, du er nummer ni. Hyggelig å møte deg. Her kan du gå. PUBLIKUM: Jen. DAVID J. MALAN: Jen. David. Number 17. Ja? 

PUBLIKUM: Jeg er Julia. 

DAVID J. MALAN: Julia, David. Nummer 20. PUBLIKUM: Christian. DAVID J. MALAN: Christian, David. Number 22. Og? 

PUBLIKUM: JP. DAVID J. MALAN: JP. Number 29. Så gå videre og få i-- Uh oh. Uh oh. Standby. 20. Har noen en markør? PUBLIKUM: Jeg har en Sharpie. DAVID J. MALAN: Du fikk en Sharpie? OK. Og er det noen som har et stykke papir? Lagre forelesningen. Kom igjen. PUBLIKUM: Vi har fått det. DAVID J. MALAN: Vi fikk den? Greit, takk. Here we go. Var dette fra deg? Du reddet dagen. Så 29. Greit. Jeg feilstavet 29, men OK. Gå fremover. Greit, jeg skal gi deg pennen tilbake et øyeblikk. Så vi har disse folkene her. La oss ha en annen. Gabe, ønsker du å spille det første elementet her? Vi trenger deg til å peke på disse fine folk. Så 9, 17, 20, 22, liksom over 29, og deretter 34. Har vi mister noen? Jeg har en 34. Hvor did-- OK, som ønsker å være 34? OK, kom igjen opp, 34. Greit, vil dette være vel verdt klimaks. Hva heter du? 

PUBLIKUM: Peter. 

DAVID J. MALAN: Peter, kom opp. Ok, så her er en hel haug med noder. Hver av dere representerer en av disse rektangler. Og Gabe, litt merkelig mannen ut, representerer først. Så hans pekeren er litt mindre på skjermen enn alle andre. Og i dette tilfellet, hver av venstre hendene skal enten peke ned, derved representerer null, slik at bare fravær av en peker, eller det kommer til å peke på en node ved siden av deg. 

Så akkurat nå hvis du pryde dere som på bildet her, gå videre og peker på hverandre, med Gabe spesielt peker på nummer 9 til å representere listen. OK, og nummer 34, venstre hånd skal bare peke på gulvet. 

OK, så dette er det lenket liste. Så dette er scenariet i spørsmålet. Og ja, dette er representativt av en klasse av problemer at du kan prøve å løse med kode. Du vil til slutt sette inn et nytt element i listen. I dette tilfellet skal vi prøv å sette inn nummer 55. Men det kommer til å bli ulike tilfeller å vurdere. Og ja, dette kommer til å være en av den store bildet gatekjøkken her, er, hva er de forskjellige sakene. Hva er det annerledes hvis forholdene eller grener som programmet ditt kan ha? 

Vel, det nummeret du prøver å innsats, som vi vet nå å være 55, men hvis du ikke visste på forhånd, daresay jeg faller inn i minst tre mulige situasjoner. Der kan et nytt element være? PUBLIKUM: Og slutten eller midten. DAVID J. MALAN: På slutten, i midten, eller i begynnelsen. Så jeg hevder det er minst tre problemer vi må løse. La oss velge hva som er kanskje uten tvil den enkleste en, der den nye element hører i begynnelsen. Så jeg kommer til å ha kode ganske som søker, som jeg nettopp skrev. Og jeg kommer til å ha ptr, som Jeg skal representere her med min finger, som vanlig. 

Og husk, hvilken verdi gjorde vi initial ptr til? Så vi initialisert det til null i utgangspunktet. Men så hva gjorde vi når vi var inne i vår søkefunksjon? Vi setter den lik første, som betyr ikke gjør dette. Hvis jeg satt ptr lik første, hva skal min hånd virkelig være å peke på? Høyre. Så hvis Gabe og jeg kommer å være like verdier her, vi trenger både poeng på nummer ni. 

Så dette var begynnelsen på vår historie. Og nå er dette bare grei, selv om syntaksen er nytt. Konseptuelt dette er bare lineær søk. Er 55 lik 9? Eller rettere sagt, la oss si mindre enn 9. Fordi jeg prøver å finne ut hvor du skal plassere 55. Mindre enn 9 og mindre enn 17, mindre over 20, mindre enn 22 og mindre enn 29. mindre enn 34, no. Så nå er vi i tilfelle en av minst tre. 

Hvis jeg ønsker å sette inn 55 over her, hva linjer med kode behov for å få utført? Hvordan virker dette bildet av mennesker trenger å forandre? Hva gjør jeg med min venstre hånd? Dette bør være null i utgangspunktet, fordi jeg er på slutten av listen. Og hva som skal skje her med Peter, var det? Han åpenbart kommer til å peke på meg. Så jeg hevder det er minst to linjer av koden i eksempelkode fra i dag som kommer til å gjennomføre dette scenario med å legge 55 på halen. Og kan jeg få noen hop opp og bare representerer 55? Greit, du er den nye 55. 

Så nå hva om den neste scenario kommer sammen, og vi ønsker å sette på begynner eller leder av denne listen? Og hva er ditt navn, nummer 55? 

PUBLIKUM: Jack. 

DAVID J. MALAN: Jack? OK, hyggelig å møte deg. Velkommen om bord. Så nå skal vi sette inn, si, nummer fem. Her er det andre tilfellet av tre vi kom opp med før. Så hvis 5 tilhører i begynnelsen, la oss se hvordan vi finne det ut. Jeg initial min ptr pekeren til nummer 9 igjen. Og jeg skjønte, oh, 5 er mindre enn 9. Så fikse dette bilde for oss. Hvis hender, Gabe eller Davids or-- hva som er nummer ni navn? 

PUBLIKUM: Jen. 

DAVID J. MALAN: Jen hands-- hvilke av våre hender må endre? OK, så Gabe peker på hva nå? På meg. Jeg er den nye noden. Så jeg vil bare slags trekk her for å se det visuelt. Og i mellomtiden hvilket punkt jeg gjøre det? Fortsatt der jeg peker. Så det er det. Så bare virkelig en linje med kode rettinger dette spesielle problemet, vil det synes. Ok, så det er bra. Og kan noen være en plassholder for 5? Kom opp. Vi skal få deg neste gang. 

Greit, så now-- og Som en side, navnene Jeg gjør ikke eksplisitt omtale av retten nå, pred pekeren, forgjenger pekeren og ny pekeren, det er bare navnene gitt i eksempelkoden til pekere eller mine hender som er slags peker rundt. Hva heter du? 

PUBLIKUM: Christine. 

DAVID J. MALAN: Christine. Velkommen om bord. Ok, så la oss vurdere nå en litt mer irriterende scenario, der jeg ønsker å sette inn noe sånt som 26 inn i dette. 20? Hva? Disse er-- bra vi har denne pennen. Greit, 20. Hvis noen kunne få en annen del av papir klar, bare i case-- all right. Oh, interessant. Vel, dette er et eksempel av et foredrag bug. OK, så hva heter du igjen? PUBLIKUM: Julia. DAVID J. MALAN: Julia, kan du pop ut og late som du aldri har vært der? OK, dette aldri skjedd. Takk. Så antar vi vil sette inn Julia inn i dette lenket liste. Hun er nummer 20. Og selvfølgelig hun er kommer til å tilhøre på begin-- ikke peke på noe ennå. Så din hånd kan slags være ned null eller noen søppel verdi. La oss fortelle rask historie. Jeg peker på nummer fem denne gangen. Så jeg sjekke ni. Så jeg sjekke 17. Så jeg sjekke 22. Og jeg skjønner, ooh, Julia trenger å gå før 22.. Så hva som må skje? Hvis hender må endre? Julia, gruve, or-- hva heter du igjen? 

PUBLIKUM: Christian. 

DAVID J. MALAN: Christian eller? 

PUBLIKUM: Andy. 

DAVID J. MALAN: Andy. Christian eller Andy? Andy trenger å peke på? Julia. Greit. Så Andy, har du lyst til å peke på Julia? Men vent litt. I historien så langt, Jeg er liksom en ansvaret, i den forstand at pekeren er det som er beveger seg gjennom listen. Vi kan ha et navn for Andy, men det er ingen variabel kalt Andy. Den eneste andre variable vi har er først, hvem representert ved Gabe. 

Så dette er egentlig hvorfor dermed langt vi ikke har behov for dette. Men nå på skjermen er nevne igjen av Pred pekeren. Så la meg være mer eksplisitt. Hvis dette er pekeren, hadde jeg bedre få litt mer intelligent om min iterasjon. Hvis du ikke tankene mine går gjennom her igjen, peker her, peker her. Men la meg ha en Pred peker, forgjenger pekeren, det er slags peker på element jeg var bare på. Så når jeg går her, nå min venstre hånd oppdateringer. Når jeg går her min venstre hånd oppdateringer. Og nå har jeg ikke bare en peker til elementet som går etter Julia, Jeg har fortsatt en peker til Andy, elementet før. Så du har tilgang, i hovedsak, brødsmuler, om du vil, til alle de nødvendige pekere. 

Så hvis jeg peker på Andy og jeg er også peker på Christian, hvis hender skal nå være påpekt andre steder? Så Andy kan nå peke på Julia. Julia kan nå peke på Christian. Fordi hun kan kopiere min høyre hånd pekeren. Og som effektivt setter deg tilbake til dette stedet her. Så kort sagt, selv om dette tar oss slags evig å faktisk oppdatere en lenket liste, skjønner at virksomheten er forholdsvis enkel. Det er av en, to, tre linjer med kode til slutt. Men pakket rundt dem linjer med kode formodentlig er litt av logikken som effektivt stiller spørsmålet, hvor er vi? Er vi i begynnelsen, midten eller slutten? 

Nå er det absolutt annen operasjonene vi kan iverksette. Og disse bildene her bare skildre hva vi nettopp gjorde med mennesker. Hva om fjerning? Hvis jeg vil, for eksempel, fjerne nummer 34 eller 55, Jeg kan ha den samme typen kode, men jeg kommer til å trenge ett eller to trinn. Fordi hva er nytt? Hvis jeg fjerner noen på slutten, som nummer 55 og deretter 34, hva har også å endre så jeg gjøre det? Jeg må ikke evict-- hva heter du igjen? 

PUBLIKUM: Jack. 

DAVID J. MALAN: Jack. Jeg må ikke bare evict-- gratis Jack, så bokstavelig ringe gratis Jack, eller i det minste pekeren der også, men nå hva som må endres med Peter? Hånden hans bedre start peker nedover. Fordi så snart jeg ringe gratis på Jack, hvis Peters fremdeles peker på Jack og jeg derfor holde traversering listen og få tilgang til denne pekeren, det er da vår gamle venn segmentering feil kan faktisk sparke i. Fordi vi har gitt minne tilbake til Jack. 

Du kan bo der klønete for bare et øyeblikk. Fordi vi har bare et par endelige operasjoner for å vurdere. Fjerne hodet av listen, eller beginning-- og dette ens litt irriterende. Fordi vi må vite at Gabe er slags spesielle i dette programmet. Fordi ja, har han sin egen pekeren. Han er ikke bare å peke på, som er nesten alle andre her. 

Så når hodet av listen er fjernet, hvis hender trenger å endre seg nå? Hva heter du igjen? 

PUBLIKUM: Christine. 

DAVID J. MALAN: Jeg er forferdelig ved navn, tilsynelatende. Så Christine og Gabe, hvis hender må endre når vi prøver å fjerne Christine, nummer fem, fra bildet? OK, så la oss gjøre Gabe. Gabe kommer til å peke, formodentlig, i nummer ni. Men hva blir det neste som skal skje? PUBLIKUM: Christine bør være null [uhørbart]. DAVID J. MALAN: OK, vi burde kanskje make-- jeg hørt "null" et sted. PUBLIKUM: Null og gratis henne. DAVID J. MALAN: Null hva? PUBLIKUM: Null og gratis henne. DAVID J. MALAN: Null og gratis henne. Så dette er veldig enkelt. Og det er perfekt at du er nå liksom av å stå der, ikke tilhørighet. Fordi du har vært dekoblet fra listen. Du har effektivt blitt foreldreløs fra listen. Og så vi hadde bedre ringe gratis nå Christine å gi den minne tilbake. Ellers hver gang vi slette en node fra listen vi kan være å lage en liste kortere, men faktisk ikke avtagende størrelsen i minnet. Og så hvis vi fortsetter å legge og legge til, legge ting til listen datamaskinen min kan bli tregere og tregere og tregere, fordi jeg kjører ut av minne, selv om jeg faktisk ikke bruker Christines bytes minne lenger. 

Så til slutt er det andre scenarier, av course-- fjerning i midten, fjerning på slutten, som vi så. Men jo mer interessant Utfordringen nå kommer til å være å vurdere nøyaktig hva driftstiden er. Så ikke bare kan du holde biter av papir, hvis, Gabe, du ville ikke tankene å gi alle en stress ball. Takk så mye til vår lenket liste av frivillige her, hvis du kunne. 

[APPLAUSE] 

DAVID J. MALAN: All right. Så et par analytisk spørsmål da, hvis jeg kunne. Vi har sett denne notasjonen før, Big O og omega, øvre grenser og nedre grenser på kjøretid på noen algoritme. Så la oss vurdere bare et par spørsmål. 

En, og vi sa det før, hva er driften tidspunktet for søk etter en liste i form av stor O? Det finnes en øvre grense på løpe tid for å søke en lenket liste som gjennomføres av våre frivillige her? Det er stor O av n, lineær. Fordi i verste fall elementet, slik som 55, vi kan være ute etter kan være der Jack var, helt på slutten. Og dessverre, i motsetning til en rekke vi kan ikke få fancy denne gangen. Selv om alle våre mennesker var sortert fra små elementer, 5, hele veien opp til den større del, 55, er det vanligvis en god ting. Men hva gjør denne antakelsen ikke lenger tillate oss å gjøre? PUBLIKUM: [uhørbart] DAVID J. MALAN: Si det igjen? PUBLIKUM: Random access. DAVID J. MALAN: Random access. Og i sin tur betyr det at vi ikke kan gjøre lenger bruke svak nuller, intuisjon, og selvfølgelighet å bruke binær søke og splitt og hersk. For selv om vi mennesker kunne åpenbart se at Andy eller Christian var omtrent i midten av listen, Vi vet bare at som en datamaskin ved skimming listen helt fra begynnelsen. Så vi har gitt opp at random access. 

Så stor O av n er nå den øvre bundet på vår søketiden. Hva om omega av våre søk? Hva er nedre grense på å søke for noen nummer i denne listen? PUBLIKUM: [uhørbart] DAVID J. MALAN: Si det igjen? PUBLIKUM: One. DAVID J. MALAN: One. Så konstant tid. I beste fall er Christine faktisk på begynnelsen av listen. Og vi leter etter nummer fem, så vi fant henne. Så ingen big deal. Men hun er nødt til å være på begynnelsen av listen i dette tilfellet. Hva med noe sånt som Slette? Hva om du ønsker å slette et element? Hva er den øvre grensen og nedre grense om sletting av noe fra en koblet listen? PUBLIKUM: [uhørbart] DAVID J. MALAN: Si det igjen? PUBLIKUM: n. DAVID J. MALAN: n er faktisk den øvre grensen. Fordi i verste fall vi prøver å slette Jack, som vi nettopp gjorde. Han er helt på slutten. Tar oss alltid, eller n skritt for å finne ham. Så det er en øvre grense. Det er lineær, sikkert. Og den beste fall driftstid, eller nedre grenser i beste fall ville være konstant tid. Fordi kanskje vi prøver å slette Christine, og vi bare få heldige hun er i begynnelsen. Vent nå litt. Gabe var også i begynnelsen, og vi måtte også oppdatere Gabe. Så det var ikke bare ett trinn. Så er det faktisk konstant tid, i beste fall for å fjerne det minste elementet? Det er, selv om det kan være to, tre, eller 100 linjer med kode, hvis det er samme antall linjer, ikke i noen loop, og uavhengig av størrelsen av listen, absolutt. Slette element på begynnelsen av listen, selv om vi har å forholde seg til Gabe, er fortsatt konstant tid. 

Så dette virker som en massiv skritt bakover. Og hva en bortkastet tid hvis, i uke en og uke null hadde vi ikke bare pseudokode, men selve koden å gjennomføre noe som er log basen n, eller logg, snarere, n, base 2, i form av sin driftstid. Så hvorfor pokker ville vi ønsker å starte ved hjelp av noe som en lenket liste? Yeah. 

PUBLIKUM: Så du kan legge til elementer til matrisen. DAVID J. MALAN: Så du kan legge til elementer i array. Og dette er også tematisk. Og vi vil fortsette å se dette, denne avveiingen, mye som vi har sett en trade-off med flettingen slag. Vi kunne virkelig fremskynde søke eller sortering, heller, hvis vi bruke litt mer plass og har en ytterligere del av en minne eller en matrise for flettingen slag. Men vi bruker mer plass, men vi sparer tid. I dette tilfellet er vi gi opp tid, men vi er få fleksibilitet, dynamikk om du vil, som er uten tvil en positiv funksjon. 

Vi er også å bruke plass. I hvilken forstand er en koblet liste dyrere i form av plass enn en matrise? Hvor er den ekstra plassen kommer fra? Yeah? 

PUBLIKUM: [uhørlig] pekeren. 

DAVID J. MALAN: Ja, vi har også pekeren. Så dette er minorly irriterende i at det ikke lenger er am Jeg lagrer bare en int å representere en int. Jeg lagrer en int og en spisser, som også er 32 biter. Så jeg bokstavelig talt en dobling hvor mye plass som er involvert. Så det er en trade-off, men det er i tilfelle av int. Anta at du ikke lagrer int, men antar at hver av disse rektangler eller hver av disse menneskene var som representerer et ord, et engelsk ord som kan være fem tegn, 10 tegn, kanskje enda mer. Deretter legger bare 32 flere biter kan være mindre av en stor avtale. 

Hva om hver av elevene i demonstrasjonen var bokstavelig talt student structs som har navn og hus og kanskje telefonnumre og Twitter håndtak og lignende. Så alle feltene vi startet snakker om her om dagen, mye mindre av en stor avtale som våre noder få mer interessant og stor til å bruke, eh, en ekstra pekeren bare for å koble dem sammen. Men ja, det er en trade-off. Og ja, er koden mer kompleks, som du vil se ved å tråle gjennom det bestemte eksempelet. Men hva om det var noen hellige gral her. Hva hvis vi ikke tar et skritt bakover, men en massiv skritt fremover og implementere en data struktur via som vi kan finne elementer som Jack eller Christine eller andre elementer i denne matrisen i ekte konstant tid? Søk er konstant. Slett er konstant. Sett er konstant. Alle disse operasjonene er konstant. Det ville være vår hellige gral. Og det er der vi vil ta seg opp neste gang. Se deg da.