[Musiikkia] DOUG Lloyd: Selvä. Joten jos olet juuri että video yksittäin sidottujen luettelot pahoillani Jätin sinut pois hieman jännitysnäytelmä. Mutta olen iloinen että olet täällä loppuun tarina kaksinkertaisesti sidottu luetteloita. Joten jos muistatte että video, puhuimme miten yksittäin sidottu luettelot tehdä osallistua kykymme käsittelemään tietoa jossa alkioiden lukumäärä tai kohteiden määrä luettelo voi kasvaa tai kutistua. Voimme nyt käsitellä jotain, jos emme voineet käsitellä sitä paneelit. Mutta he eivät kärsi yhdestä kriittinen rajoitus joka on, että yksittäin sidottu lista, voimme vain koskaan liikkua yhteen suuntaan listan läpi. Ja ainoa todellinen tilanne jossa joka voi tulla ongelma oli, kun yritimme poistaa yksittäinen elementti. Ja emme edes keskustella siitä, miten tehdä se in yksittäin-linkitetyn listan pseudokoodilla. Se on varmasti toteutettavissa, mutta se voi olla hieman vaivaa. Joten jos löydät itsesi tilanteessa, jossa yrität poistaa single elementtejä listasta tai se tulee vaatia että sinun on poistaa single elementtejä luettelossa, saatat haluta harkita kahdesti sidottu luetella sijasta yksittäin-linkitetyn listan. Koska kaksinkertaisesti sidottu luetteloiden avulla voit liikkua sekä eteen- että taaksepäin luetteloa sijasta vain eteenpäin list-- vain lisäämällä yksi ylimääräinen elementti meidän rakenteen määrittely varten kaksoislaimennettu linkitetyn listan solmu. Jälleen, jos et aio voidaan poistaa yksi elementit alkaen list-- koska lisäämme lisäkenttä meidän rakenne määritelmä, solmut itse varten kaksinkertaisesti sidottu luettelot tulevat olemaan suurempia. He aikovat ottaa enemmän tavua muistia. Joten jos tämä ei ole jotain olet menossa tarvitse tehdä, saatat päättää se ei kannata vaihtokaupasta täytyy käyttää ylimääräistä tavua muistia tarvitaan varten kaksinkertaisesti sidottu lista, jos et ole aiotaan poistaa yhden elementtejä. Mutta he ovat myös viileä muita asioita liikaa. Joten kuten sanoin, meidän on vain lisätä yksi kenttä rakenteemme definition-- tätä käsitettä edellisen osoittimen. Joten yksittäin-linkitetty lista, me on arvo ja Seuraava osoitin, joten kaksoislaimennettu linkitetty lista vain on tapa liikkua taaksepäin samoin. Nyt yksinään sidottu lista video, puhuimme näistä on viisi tärkeimmät asiat sinun täytyy olla voi tehdä työskennellä linkitettyjen listojen. Ja useimmat näistä se, että se on kaksinkertaisesti linkitetty lista ei oikeastaan ​​ison hypyn. Voimme silti etsiä vain hieman eteenpäin alusta loppuun. Voimme silti luoda solmu ulos ohut ilma, melko samalla tavalla. Voimme poistaa luetteloita melko paljon samalla tavalla myös. Ainoat asiat, ovat hieman toisenlainen, todella, asennat uusi solmut listaan, ja me lopulta puhua poistaminen yksittäinen elementti luettelosta samoin. Jälleen melko paljon muut kolme, olemme aio puhua niistä juuri nyt, koska ne ovat vain hyvin pieniä parannuksia sen ajatuksista keskustellaan in yksittäin-linkitetyn listan video. Joten lisätä uusi solmu osaksi kaksinkertaisesti sidottu lista. Puhuimme tee tätä yksittäin sidoksissa luettelot samoin, mutta siellä on pari ylimääräistä saaliit kahdesti sidoksissa luetteloita. Olemme [? ohimennen?] vuonna pään luetella tässä ja joitakin mielivaltainen arvo, ja haluamme saada uusi johtaja luettelon pois tämän toiminnon. Siksi se palaa dllnode tähti. Mitä ovat vaiheet? Ne ovat, jälleen, hyvin samankaltainen että yksittäin sidottu luettelot yksi ylimääräinen lisäksi. Haluamme jakaa tilaa uuden solmu ja varmista, että se on voimassa. Haluamme täyttää että solmu ylös kanssa, mitä tietoa meillä haluavat laittaa se. Viimeinen asia, meidän do-- ylimääräinen asia, joka meidän täytyy tehdä, rather-- on korjata Edellinen osoitin vanhan pään luettelon. Muista, että koska aan kahdesti sidottu luettelot, voimme edetä ja backwards-- joka tarkoittaa, että jokainen solmu todella huomauttaa kaksi muuta solmut yhden sijasta. Ja niin meidän täytyy korjata vanha johtaja lista osoittamaan taaksepäin uusi johtaja linkitetty lista, joka oli jotain meillä ei tarvitse tehdä ennen. Ja kuten ennenkin, me vain palata Osoitin uusi johtaja luettelon. Joten tässä on luettelo. Haluamme lisätä 12 tähän luetteloon. Huomaa, että kaavio on hieman erilainen. Jokainen solmu sisältää kolme fields-- tiedot, ja Seuraava osoitin punainen, ja Edellinen osoitin sinisellä. Mitään tulee ennen 15 solmun, joten sen Edellinen osoitin on null. Se on listan alussa. Ei ole mitään ennen sitä. Ja mitään ei tule jälkeen 10 solmun, ja joten se seuraavaksi osoitin on tyhjä samoin. Joten lisätä 12 tähän luetteloon. Tarvitsemme [äänetön] tilaa solmu. Laitamme 12 sen sisälle. Ja sitten taas, meidän on oltava todella Varo katkaisemiseksi. Haluamme järjestää viitteitä oikeassa järjestyksessä. Ja joskus se voi mean-- kuten näemme erityisesti kanssa delete-- että meillä on joitakin tarpeeton osoittimia, mutta se on OK. Mitä me haluamme tehdä ensin? Suosittelen asioita sinun pitäisi luultavasti do ovat täyttää osoittimet 12 solmu ennen kuin kosketat ketään muuta. Joten mitä 12 menossa osoittamaan seuraavaksi? 15. Mitä tulee ennen 12? Mitään. Nyt olemme täynnä Lisätiedot 12 joten se on Edellinen, Seuraava, ja arvo. Nyt voimme olla 15-- tätä ylimääräistä askel puhuimme about-- me voi olla 15 kohta takaisin 12. Ja nyt voimme siirtyä pään linkitetty lista on myös 12. Joten se on melko samanlainen kuin mitä me tekivät kanssa yksittäin sidottu luettelot, lukuun ottamatta ylimääräinen vaihe yhdistää vanha pää luettelon Takaisin uusi johtaja luettelon. Nyt vihdoin poistaa solmu linkitetyn listan. Joten sanokaamme meillä joitakin muita toiminto on löytää solmu haluamme poistaa ja on antanut meille osoitin tarkalleen solmu, että haluamme poistaa. Emme edes need-- sanoa pää on edelleen maailmanlaajuisesti julistettu. Emme tarvitse pää täällä. Kaikki tämä toiminto tekee on olemme löytyi osoitin juuri solmu me haluavat päästä eroon. Mennään eroon siitä. Se on paljon helpompaa kaksinkertaisesti sidottu luetteloita. First-- se on todella vain pari asiaa. Meidän vain täytyy korjata ympäröivän solmut "viitteitä jotta he ohittaa solmu haluamme poistaa. Ja sitten voimme poistaa että solmu. Joten jälleen, me vain läpi täällä. Olemme ilmeisesti päättänyt, että haluamme poistaa solmuun X. Ja vielä, mitä olen tekee here-- mukaan way-- on yleinen asia solmu, joka on keskellä. On olemassa pari ylimääräisiä varoituksista, että olet täytyy harkita, kun olet poistat aivan listan alkuun tai erittäin luettelon loppuun. On pari erityinen kulma tapauksissa käsitellä siellä. Joten tämä toimii poistamatta solmu keskellä list-- joka on oikeutettu osoitin eteenpäin ja laillinen osoitin taaksepäin, oikeutettu Edellinen ja Seuraava osoitin. Jälleen, jos olet työskennellyt kanssa päättyy, sinun täytyy käsitellä niitä hieman eri tavalla, ja emme aio puhua siitä nyt. Mutta voit luultavasti selvittää, mitä on tehtävä vain katsomalla tämän videon. Joten olemme eristetty X. X on solmu haluamme poistaa listalta. Mitä me teemme? Ensinnäkin, meidän täytyy järjestää ulkopuolella viitteitä. Meidän on järjestää 9: n vieressä ohittaa 13 ja valitse 10-- joka on mitä olemme juuri tehneet. Ja meidän on myös järjestää 10: n Edellinen osoittamaan 9 sijasta osoittaa 13. Niin edelleen, tämä oli kaavio aloittaa. Tämä oli meidän ketju. Meidän on ohittaa 13, mutta meidän on myös säilyttää eheyden luettelon. Emme halua menettää tiedot kumpaankin suuntaan. Joten meidän täytyy järjestää viitteitä huolellisesti joten emme katkaisemiseksi ollenkaan. Voimme siis sanoa 9 Next osoitin viittaa samaan paikkaan että kolmetoista Next osoitin juuri nyt. Koska olemme lopulta menossa haluavat ohittaa 13. Joten missä 13 pistettä Seuraavaksi haluavat yhdeksän kohtaan siellä sijaan. Niin se siitä. Ja sitten missä 13 pistettä takaisin on, mitä tulee ennen 13, Haluamme 10 pisteeseen sen, että sen sijaan 13. Nyt huomaa, jos noudatat nuolet, voimme pudottaa 13 ilman todella menettämättä mitään tietoa. Olemme säilyttäneet eheyden luettelon, liikkuvat sekä eteen- ja taaksepäin. Ja sitten voimme vain eräänlainen ja puhdistaa sen hieman vetämällä luettelon yhdessä. Joten me jäsensi viitteitä kummallakin puolella. Ja sitten me vapautti X solmu, joka sisälsi 13, ja emme katkaisemiseksi. Joten teimme hyvää. Lopullinen huomautus täällä linkitettyjen listojen. Joten molemmat singly- ja kaksinkertaisesti sidottu luettelot, kuten olemme nähneet, tuki todella tehokas lisäys ja poistetaan elementtejä. Voit melko paljon tehdä se jatkuvasti ajan. Mitä meidän on tehtävä poistaa elementti vain toinen sitten? Muutimme yksi osoitin. Muutimme toinen osoitin. Me vapautti X-- kesti kolme toimintaa. Se vie aina kolme toimintaansa poistaa että node-- vapaa solmuun. Miten lisätä? No, olemme vain aina tacking alussa jos me lisäämällä tehokkaasti. Joten meidän on rearrange-- riippuen jos se on singly- tai kaksinkertaisesti sidottu luettelo, saatamme tarvita tehdä kolme tai neljä toimintaa max. Mutta jälleen kerran, se on aina kolme tai neljä. Sillä ei ole väliä kuinka monta elementit ovat listallamme, se on aina kolme tai neljä operations-- kuten poisto on aina kolme tai neljä toimintaa. Se on jatkuva aika. Niin se on todella suuri. Kanssa paneelit, teemme jotain lisäyslajittelun. Olet luultavasti muistaa, että lisäys lajitella ei ole vakio algoritmi. Se on oikeastaan ​​aika kallista. Joten tämä on paljon parempi lisäämällä. Mutta kuten mainitsin yksittäin-linkitetty lista video, meillä haittapuoli täälläkin, eikö? Olemme menettäneet kyvyn satunnaisesti käyttää elementtejä. Emme voi sanoa, haluan elementti numero neljä tai osa numero 10 linkitetty lista samalla tavalla kuin voimme tehdä sen array tai voimme vain suoraan indeksi meidän array elementti. Ja niin yritetään löytää elementti liittyy list-- jos haku on important-- voi vastedes ottaa lineaarinen aikaa. Koska lista pitenee, se saattaa kestää yksi lisävaihe jokaisesta elementti luettelossa jotta löytää mitä etsimme. Joten siellä on kompromisseista. On hieman pro ja con elementti tässä. Ja kaksinkertaisesti sidottu luettelot eivät ole viime millaisia ​​tietoja rakenteen yhdistelmä että me puhumme, kun kaikki perusrakenneosia lohkojen C koota. Koska itse asiassa, voimme jopa tehdä paremmin kuin tämä luoda tietojen rakenne, joka voit ehkä etsiä jatkuvassa aikaa. Mutta lisää, että toinen video. Olen Doug Lloyd. Tämä on CS50.