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