>> [Mūzikas atskaņošanai]
Doug LLOYD: Nu labi.
Tātad, ja jūs tikko beidzis, ka video par atsevišķi saistītiem sarakstiem žēl
Es atstāju jūs off uz mazliet cliffhanger.
Bet es esmu priecīgs jūs esat šeit, lai pabeigtu stāsts par divkārt saistītiem sarakstiem.
>> Tātad, ja jūs atceraties no ka video, mēs runājām
par to, kā atsevišķi piesaistīto saraksti darīt apmeklēt mūsu spēju
lai izskatītu informāciju kur vairāki elementi
vai vienību skaits, kas sarakstu var augt un sarauties.
Tagad mēs varam tikt galā ar kaut kā tā, kur
mēs nevarētu tikt ar to galā ar masīviem.
>> Bet viņi cieš no viena kritiska ierobežojums, kas
ir tā, ka ar atsevišķi-linked sarakstu, mēs varam tikai kādreiz pārvietot
tikai vienā virzienā caur sarakstā.
Un vienīgais reālais stāvoklis kur, kas var kļūt par problēmu
bija, kad mēs cenšamies izdzēst vienu elementu.
Un mums nav pat apspriest, kā to izdarīt ar atsevišķi piesaistīta sarakstā pseudocode.
Tas noteikti ir veicams, bet tas var būt mazliet par problēmu.
Tātad, ja jums atrast sev situācijā, kad
jūs mēģināt izdzēst vienvietīgas elementi no saraksta
vai tas būs nepieciešams ka jums tiks svītrojot
single elementi no saraksts, jūs varētu vēlēties,
apsvērt iespēju izmantot divkārt saistīts uzskaitīt nevis atsevišķi piesaistīta sarakstā.
Tā kā divkārt, kas saistīti saraksti ļauj jums lai pārvietotos gan uz priekšu un atpakaļ
caur sarakstu, nevis tikai uz priekšu caur list--
vienkārši pievienojot vienu papildu elementu mūsu struktūru definīciju
par divkārt saistīts saraksta mezglā.
>> Atkal, ja jūs neesat gatavojas tikt svītrot atsevišķus elementus
No list-- jo mēs pievienojot papildu lauks mūsu struktūras
definīciju, paši mezgliem par divkārt saistītiem sarakstiem
gribam būt lielāks.
Viņi gatavojas veikt up vairāk baiti atmiņas.
Un tāpēc, ja tas nav kaut kas Jūs esat dodas uz nepieciešamību to darīt,
jūs varētu izlemt, tas ir nav vērts tirdzniecības off
jātērē papildu atmiņas baiti nepieciešams
par divkārt saistīta sarakstā, ja jūs neesat būs svītrot atsevišķus elementus.
Bet viņi arī foršs citas lietas pārāk.
>> Tātad kā jau teicu, mums vienkārši ir pievienot viena lauka uz mūsu struktūras
definition-- šo jēdzienu atkritumu iepriekšējā rādītāju.
Tātad ar atsevišķi piesaistīta sarakstā, mēs ir vērtība un nākamo rādītāju,
tāpēc divkārt saistīts saraksts vienkārši ir veids, kā virzīties atpakaļ, kā arī.
>> Tagad atsevišķi piesaistīto saraksts video, mēs runājām
par tiem ir pieci no Galvenās lietas, jums ir nepieciešams, lai būtu
spēj darīt, lai strādātu ar saistītiem sarakstiem.
Un lielākā daļa no šiem, uz to, ka tas ir divkārt saistīts saraksts
nav īsti liels lēciens.
Mēs joprojām varat pārlūkot, tikai virzās uz priekšu no sākuma līdz beigām.
Mēs joprojām varam izveidot mezglu ārā no zila gaisa, diezgan daudz pašā veidā.
Mēs varam izdzēst sarakstus diezgan daudz pašā veidā too.
Tikai lietas, kas ir smalki dažādi,
tiešām, ir ievietojot jaunos punktus fani sarakstā,
un mēs beidzot runājam par dzēšanu viens elements no saraksta, kā arī.
Atkal, diezgan daudz pārējie trīs, mēs
netaisos runāt par tām tiesības tagad, jo viņi vienkārši
ļoti nelielas tweaks par idejām apsprieda kas atsevišķi saistītajā sarakstā video.
>> Tātad pieņemsim ievietot jaunu mezglu par divkārt saistīta sarakstā.
Mēs runājām par to izdarīt atsevišķi piesaistītās sarakstus, kā arī,
bet tur ir pāris extra nozveju ar divkārt saistītiem sarakstiem.
Mēs esam [? iet?] galvā no uzskaitīt šeit un daži patvaļīgi vērtība,
un mēs gribam, lai saņemtu jaunu galvu saraksta ārā no šīs funkcijas.
Tieši tāpēc tas atgriež dllnode zvaigzni.
Tātad, kādi ir soļi?
Tie ir, atkal, ļoti līdzīgs lai atsevišķi piesaistītās saraksti
ar vienu papildu papildus.
Mēs vēlamies, lai piešķir telpu jauna mezglu un pārbaude, lai pārliecinātos, ka tas ir derīgs.
Mēs vēlamies, lai ieņemtu šo mezglu up ar kāda informācija mums
gribu, lai tajā.
Pēdējā lieta, mums ir nepieciešams, lai do-- extra lieta, kas mums jādara, rather--
ir noteikt Iepriekšējais rādītāju no vecās galvas sarakstā.
Atcerieties, ka tāpēc, ka divkārt piesaistīto sarakstus,
mēs varam virzīties uz priekšu un backwards-- kas
nozīmē, ka katrs mezgls faktiski norāda ar diviem citiem mezgliem, nevis tikai vienu.
Un tāpēc mums ir nepieciešams noteikt vecais vadītājs saraksta
norādīt atpakaļ uz jauno vadītāju piesaistītais saraksts, kas bija kaut kas
mums nebija ko darīt pirms.
Un tāpat kā iepriekš, mēs vienkārši atgriezt rādītāju uz jauno vadītāju sarakstā.
>> Tātad, šeit ir saraksts.
Mēs vēlamies, lai ievietotu 12 šajā sarakstā.
Ievērojiet, ka diagramma ir nedaudz atšķirīgs.
Katrs mezgls ir trīs fields-- dati, un Next rādītājs sarkanā krāsā,
un iepriekšējais rādītājs zilā krāsā.
Nekas nāk pirms 15 mezglu, tāpēc tās Iepriekšējais rādītājs ir nulle.
Tas ir sākums saraksta.
Tur nekas pirms tā.
Un nekas nāk pēc 10 mezglu, un tāpēc tas ir Nākamais rādītājs ir nulle, kā arī.
>> Tātad pieņemsim pievienot 12 šim sarakstam.
Mums ir nepieciešams [dzirdams] telpu mezglā.
Mēs ieliekam 12 iekšpusē no tā.
Un tad atkal, mums ir nepieciešams, lai būtu patiesi Uzmanieties, lai izjauktu ķēdi.
Mēs vēlamies, lai pārkārtotu norādes, kas pareizā secībā.
Un reizēm tas varētu mean-- jo mēs redzēsim īpaši
ar delete-- ka mums ir daži lieks norādes, bet tas ir OK.
>> Tātad, ko mēs vēlamies darīt vispirms?
Es ieteiktu lietas, jums ir iespējams
darīt ir jāaizpilda norādes no 12 mezgla pirms jūs pieskarties kāds cits.
Tātad, kas ir 12 gatavojas norādīt uz nākamo?
15.
Kas nāk pirms 12?
Nekas.
Tagad mēs esam piepilda papildu informācija 12
tāpēc tas ir iepriekšējo, nākamo, un vērtību.
>> Tagad mēs varam būt 15-- šo papildu solis mēs runājām about-- mēs
var būt 15 punktu atpakaļ uz 12.
Un tagad mēs varam virzīties uz galvas piesaistītais saraksts būt arī 12.
Tātad tas ir diezgan līdzīgs tam, ko mēs darīja ar atsevišķi saistītiem sarakstiem,
izņemot papildu soli savieno veco galvu saraksta
atpakaļ uz jauno galvas sarakstā.
>> Tagad beidzot dzēst mezglu no saistītā saraksta.
Tātad pieņemsim, ka mums ir dažas citas funkcijas,
ir atrast mezglu mēs vēlamies, lai izdzēstu un mums ir devis rādītāju tieši
mezglu, ka mēs vēlamies, lai izdzēstu.
Mums nav pat need-- teikt galva joprojām visā pasaulē pasludināts.
Mums nevajag galvu šeit.
Visa šī funkcija dara, ir, mēs esam konstatēja rādītāju uz tieši mezglu mēs
vēlas atbrīvoties no.
Pieņemsim atbrīvoties no tā.
Tas ir daudz vieglāk ar divkārt saistītas sarakstus.
First-- tas ir faktiski tikai pāris lietas.
Mums ir nepieciešams, lai noteiktu apkārtējo mezgli "norādes, lai viņi izlaist
mezglu mēs vēlamies izdzēst.
Un tad mēs varam izdzēst šo mezglu.
Tātad vēlreiz, mēs esam tikai iet cauri šeit.
Mēs esam acīmredzot nolēma, ka mēs vēlamies, lai izdzēstu mezglu X.
Un atkal, ko es esmu darot here-- ko way--
ir vispārējs gadījums priekšlikums mezgls, kas ir pa vidu.
Ir pāris papildu brīdinājumi, ka jūs
nepieciešams apsvērt, kad jūs dzēšot pats sākums saraksta
vai pašām beigām sarakstā.
Tur ir pāris īpašs stūra lietas risināt tur.
>> Tātad tas darbojas dzēšanas jebkuru mezglu vidū uz list-- vienu, kas
ir leģitīms rādītāju priekšu un likumīgs rādītājs atpakaļ,
likumīga iepriekšējo un nākamo rādītājs.
Atkal, ja jūs strādājat ar galiem, tu
nepieciešams apstrādāt tiem nedaudz atšķirīgi,
un mēs nebrauksim runāt par to tagad.
Bet jūs varat droši izdomāt, ko vajag
jādara tikai skatoties šo video.
>> Tāpēc mēs esam izolēti X. X ir mezgls mēs vēlamies, lai izdzēstu no saraksta.
Ko mēs darām?
Pirmkārt, mums ir nepieciešams, lai pārkārtotu Ārpus norādes.
Mums ir nepieciešams, lai pārkārtotu 9 ir blakus izlaist 13
un norāda uz 10-- kas ir tas, ko mēs esam tikko darīts.
Un mums arī pārkārtot 10 iepriekšējo
norādīt uz 9. vietā, norādot uz 13.
>> Tātad atkal, tas bija diagramma, lai sāktu ar.
Tas bija mūsu ķēdē.
Mums ir nepieciešams, lai izlaistu virs 13, bet mums ir arī saglabāt
integritāte saraksta.
Mēs nevēlamies zaudēt jebkādu informācija vienā vai otrā virzienā.
Tāpēc mums ir nepieciešams, lai pārkārtotu tad norādes uzmanīgi
tāpēc mums nav pārtraukumu ķēdi vispār.
>> Tātad, mēs varam teikt, 9 nākamais rādītāju norāda uz to pašu vietu
Trīspadsmit Next rādītājs norāda tieši tagad.
Tāpēc, ka mēs esam beidzot gatavojas vēlaties izlaist 13.
Tātad, kur 13 punkti Nākamais, jums gribu deviņi norādīt tur vietā.
Tātad tas, ka.
Un tad, kad vien 13 punkti atpakaļ to, kāds nāk pirms 13,
mēs gribam 10 norādīt 13, ka tā vietā.
Tagad paziņojums, ja jums sekot bultas, mēs varam nomest 13
bez faktiski nezaudējot informāciju.
Mēs esam tur integritāti saraksta, virzās uz priekšu un atpakaļ.
Un tad mēs varam tikai sava no tīrīt to uz augšu mazliet
pavelkot sarakstu kopā.
Tātad mēs pārkārtoja norādes uz vienu vai otru pusi.
Un tad mēs atbrīvoja X mezglu, ko satur 13,
un mums nav pārtraukumu ķēdi.
Tātad mums bija laba.
>> Galīgais piezīme šeit saistītas sarakstos.
Tātad gan singly- un divkārt piesaistītās saraksti, kā mēs esam redzējuši,
atbalsts patiešām efektīva ievietošanas un dzēšanu elementiem.
Jūs varat diezgan daudz darīt tā pastāvīgā laikā.
Ko mums darīt, lai dzēstu elements ir tikai otrais atpakaļ?
Mēs pārvietots vienu rādītāju.
Mēs pārcēlās citu rādītāju.
Mēs atbrīvots X- veica trīs operācijas.
Tas vienmēr ir trīs darbības, lai dzēst šo node-- lai atbrīvotu mezglu.
>> Kā mēs ievietot?
Nu, mēs esam tikai vienmēr tacking uz sākumu
ja mēs esam ievietojot efektīvi.
Tāpēc mums ir nepieciešams, lai rearrange-- atkarībā no tā, ja tas ir
singly- vai divkārt piesaistīto saraksts, mums var būt nepieciešams veikt trīs
vai četras operācijas max.
Bet atkal, tas vienmēr ir trīs vai četri.
Tas nav svarīgi, cik daudz elementi ir mūsu sarakstā,
tas vienmēr ir trīs vai četri operations-- tāpat kā svītrošana vienmēr
trīs vai četras operācijas.
Ir pienācis laiks nemainīgs.
Tātad tas ir tiešām liels.
>> Ar blokiem, mēs darām kaut kas līdzīgs ievietošanas kārtošanas.
Jūs droši vien atceraties, ka ievietošanas kārtot nav konstants laiks algoritmu.
Patiesībā tas ir diezgan dārgi.
Tātad tas ir daudz labāk par ievietošanas.
Bet kā jau minēju atsevišķi piesaistītās sarakstu video,
mēs esam ieguvuši negatīvie arī šeit, vai ne?
Mēs esam zaudējuši spēju nejauši piekļūt elementus.
Mēs nevaram teikt, es gribu elements Number Four vai elementu skaits 10 no saistītā saraksta
tāpat, ka mēs varam darīt ar masīvu
vai mēs varam vienkārši tieši indekss mūsu Array s elements.
>> Un tā mēģina atrast elements saistītajā list--
ja meklēšana ir important-- Tagad var veikt lineāru laiku.
Tā kā saraksts kļūst garāks, tas var veikt vienu papildu soli
par katru elementu sarakstā Lai palīdzētu atrast to, ko mēs meklējam.
Tātad tur ir kompromisus.
Tur ir mazliet pro un con elements šeit.
>> Un divkārt saistīti saraksti nav pēdējā veida datu struktūru kombinācijas
ka mēs runājam par, ņemot visas pamata ēku
bloki C liekot kopā.
Jo patiesībā, mēs varam pat darīt labāk nekā šis
izveidot datu struktūru, kas jūs varētu pārlūkot
pastāvīgā laiku too.
Bet vairāk par to citā video.
>> Es esmu Doug Lloyd.
Tas ir CS50.