>> [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.