[MUZIKO Ludante] DOUG LLOYD: Bone. Do se vi ĵus finis ke vídeo sur unuope-ligitaj listoj bedaŭras Mi forlasas vin en vojaĝo iom de cliffhanger. Sed mi ĝojas ke vi estas tie por fini la rakonto de duoble-ligitaj listoj. 

Do se vi memoras de ke vídeo, ni parolis pri kiel unuope-ligitaj listoj fari ĉeesti nian kapablon trakti informo kie la nombro de elementoj aŭ la nombro de artikoloj en listo povas kreski aŭ ŝrumpi. Ni povas nun trakti io simila, kie ni ne povis pritrakti ĝin kun tabeloj. 

Sed ili suferas de unu kritika limigo kiu estas ke per unuope-ligitaj listo, ni povas nur iam movas en sola direkto tra la listo. Kaj la sola reala situacio kie kiu povas igi problemon estis kiam ni provis forviŝi sola ero. Kaj ni eĉ ne diskuti kiel fari ĝin en unuope-ligillisto en _pseudocode_. Estas certe doable, sed ĝi povas esti iom de ĝenaĵo. Do se vi trovas vin en situacio kie vi provas forigi sola elementoj el la listo aŭ ĝi estas tuj estos postulita ke vi estos forviŝo sola elementoj el la listo, vi eble volas konsideri uzanta duoble-ligitaj listo anstataŭ unuope-ligillisto. Ĉar duoble-ligitaj listoj permesos movi ambaŭ antaŭen kaj malantaŭen tra la diskutlisto anstataŭ nur antaŭen tra la list-- nur aldonante unu ekstra elemento al nia strukturo difino por la duoble-ligillisto nodo. 

Denove, se vi ne tuj estu viŝante sola elementoj el la list-- ĉar ni aldono ekstran kampo al nia strukturo difinon, la nodoj sin por duoble-ligitaj listoj tuj estos granda. Ili iras preni supren pli bajtoj de memoro. Do se tio ne estas io Vi tuj bezonas fari, vi eble decidos ĝi estas Ne valoras la komerco ekstere devos elspezi la kroman bajtoj de memoro postulata por duoble-ligillisto se vi ne estas tuj estos forviŝo sola elementoj. Sed ili estas ankaŭ malvarmeta por aliaj aĵoj ankaŭ. 

Do kiel mi diris, ni nur devas aldoni unu sola kampo al nia strukturo definition-- ĉi nocio de antaŭa montrilo. Do kun unuope-ligillisto, ni havas la valoron kaj la Sekvanta montrilon, do la duoble-ligillisto nur havas manieron por movi malantaŭen tiel. 

Nun en la unuope-ligitaj listo filmetoj, ni parolis pri tiuj estas kvin el la ĉefa aĵoj vi bezonas esti kapabla fari labori kun ligitaj listoj. Kaj por la plej multaj el tiuj, la fakto ke ĝi estas duoble-ligillisto ne vere estas granda salto. Ni povas ankoraŭ traserĉi per nur antaŭeniras de komenco al fino. Ni ankoraŭ povos krei nodon el maldika aero, preskaux la sama maniero. Ni povas forviŝi listoj bela iom same ankaŭ. La nuraj aĵoj kiuj estas subtile malsama, vere, estas enmeto novaj nodoj en la listo, kaj ni fine paroli pri forviŝo sola elemento el la listo ankaŭ. Denove, preskaux la aliaj tri, ni estas Ne tuj parolos pri ili nun ĉar ili estas nur tre minora retuŝojn sur la ideoj diskutitaj en la unuope-ligillisto vídeo. 

Do ni enmeti novan nodon en duoble-ligillisto. Ni parolis pri faranta tion ĉi por unuope-ligitaj listoj tiel, Sed tie estas paro de ekstra kaptas kun duoble-ligitaj listoj. Ni estas [? pasante?] en la kapo de la listo tie kaj iuj arbitraj valoro, kaj ni volas atingi la novan estron de la listo el tiu funkcio. Tial ĝi resendas dllnode stelo. Do kio estas la paŝoj? Ili estas, denove, tre simila al unuope-ligitaj listoj kun unu ekstra aldono. Ni volas allocates spacon por nova nodo kaj ĉeko por certigi ĝi estas valida. Ni volas plenigi tiu nodo ĝis kun kiom informo ni volas meti en ĝin. La lasta afero ni devas do-- la ekstraj afero ni devas fari, rather-- estas fiksi la Antaŭa montrilon de la maljuna kapo de la listo. Memoru ke ĉar de duoble-ligitaj listoj, Ni povas movi antaŭen kaj backwards-- kiu signifas ke ĉiu nodo indikas reale al du aliaj nodoj anstataŭ nur unu. Kaj tial ni devas redifini la malnova kapo de la listo atentigi dorsen al la nova estro de la ligillisto, kiu estis iu ni ne devis fari antaŭe. Kaj kiel antaŭe, ni nur resendas sagon al la nova kapo de la listo. 

Do jen listo. Ni volas enmeti 12 en tiun liston. Rimarku ke la diagramo estas iomete malsamaj. Ĉiu nodo enhavas tri fields-- datumoj, kaj Next montrilon en ruĝa, kaj Antaŭa montrilon en blua. Nenio venas antaŭ la 15 nodon, do ĝia Antaŭa puntero estas nula. Ĝi estas la komenco de la listo. Nenio antaŭ ĝi. Kaj nenio venas post la 10 nodo, kaj do ĝi estas Sekva puntero estas nula krom. 

Do ni aldonu 12 al tiu listo. Ni bezonas [inaudible] spaco por la nodo. Ni metis 12 ene de ĝi. Kaj cetere, ni bezonas esti vere atenti ne rompi la ĉenon. Ni volas reordigi la punteros en la ĝusta ordo. Kaj foje ke povus mean-- kiel ni vidos aparte kun delete-- ke ni ja havas kelkajn redunda punteros, sed tio estas bone. 

Do kion ni volas fari unue? Mi rekomendus la aferojn vi supozeble fari estas plenigi la punteros de la 12 nodo antaŭ tuŝi iu alio. Do kio estas 12 tuj atentigi al sekva? 15. Kio venas antaŭ 12? Nenio. Nun ni plenigis la ekstra informo en 12 do ĝi havas antaŭa, sekva, kaj valoro. 

Nun ni povas havi 15-- tiu ekstra paŝo ni parolis about-- ni povas havi 15 punkto reen al 12. Kaj nun ni povas movi la kapon de la ligillisto ankaŭ esti 12. Do estas sufiĉe simila al kion ni faris per unuope-ligitaj listoj, krom la ekstra paŝo de konektante la malnova kapo de la listo Reen al la nova kapo de la listo. 

Nun ni fine forviŝi nodo de ligillisto. Do diru ni havas iu alia funkcio kiu estas trovanta nodo ni volas forigi kaj donis al ni puntero al ekzakte la nodo ke ni volas forigi. Ni eĉ ne need-- diri la kapo estas ankoraŭ tutmonde deklaris. Ni ne bezonas kapon tie. Ĉiuj ĉi funkcio faras estas ni trovis montrilon al ekzakte la nodo ni volas forigi. Ni forigi gxin. Estas multe pli facile per duoble-ligitaj listoj. First-- ĝi estas fakte nur kelkaj aferoj. Ni simple devas redifini la ĉirkaŭa nodoj 'punteros por ke ili transsaltu super la nodo ni volas forigi. Kaj tiam ni povas forviŝi tiu nodo. Do denove, ni simple tuj tra tie. Ni ŝajne decidis ke ni volas forigi la nodon X. Kaj cetere, kion mi faras here-- de bare estas ĝenerala kazo por nodo, kio estas en la mezo. Estas paro de ekstraj _caveats_ ke vi bezonas konsideri kiam vi forviŝo la komenco de la listo aŭ la tre fino de la listo. Ekzistas kelkaj specialaj angulo kazoj trakti tie. 

Do tiu funkcias por viŝante ajna nodo en la mezo de la list-- kiu havas legitiman montrilon antaŭen kaj legitima montrilo dorsdirekte legitima antaŭa kaj sekva puntero. Denove, se vi laboras kun la randoj, vi bezonas manipuli tiujn iomete malsame, kaj ni ne tuj paroli pri tio nun. Sed vi povas verŝajne elkompreni bezonas farenda nur rigardas ĉi video. 

Do ni izolis X. X estas la nodo ni volas forigi el la listo. Kion ni faru? Unue, ni devas reordigi la ekstera punteros. Ni devas reordigi 9 La venonta salti super 13 kaj punkto al 10-- kiu Estas kion ni ĵus faris. Kaj ni ankaŭ bezonos reordigi 10 La Antaŭa atentigi al 9 anstataŭ indikante 13. 

Do denove, ĉi tiu estis la diagramo komence. Tiu estis nia ĉeno. Ni devas salti super 13, sed ni bezonas ankaŭ konservi la integreco de la listo. Ni ne deziras perdi ajnan informoj en ĉu direkto. Do ni devas reordigi la punteros singarde do ni ne rompi la ĉenon ajn. 

Do ni povas diri 9 Next montrilon notas al la sama loko ke dektri Next montrilo indikas ĝuste nun. Ĉar ni estas eventuale tuj volas salti super 13. Do kien 13 punktoj sekva, vin volas naŭ atentigi tie anstataŭe. Do jen tio. Kaj tiam Wherever 13 poentoj reen al, kio ajn venas antaŭ 13, ni volas 10 atentigi por ke anstataux 13. Nun rimarkas, se vi sekvas la sagoj, ni povas faligi 13 sen fakte perdi iun informon. Ni konservis la integrecon de la listo, movanta ambaŭ antaŭen kaj malantaŭen. Kaj tiam ni povas nur ia de purigi ĝin iomete tirante la listo kune. Do ni rearanĝis la punteros ambaŭflanke. Kaj tiam ni liberigis X nodo kiu enhavis 13 kaj ni ne rompis la ĉenon. Do ni bonfaris. 

Fino noto tie en ligitaj listoj. Do ambaŭ singly- kaj duoble-ligitaj listoj, kiel ni vidis, subteno vere efika inserción kaj forigo de elementoj. Vi povas sufiĉe tre faras ĝin en konstanta tempo. Kion ni devas fari por forviŝi ero nur dua antaŭe? Ni movita montrilo. Ni translokiĝis al alia puntero. Ni liberigita X-- prenis tri operacioj. Ĝi ĉiam prenas tri operacioj al forviŝi ke node-- liberigi nodo. 

Kiel ni enmeti? Nu, ni estas nur ĉiam tacking sur la komenco se ni enmeto kompetente. Do ni bezonas rearrange-- depende se ĝi estas a singly- aŭ duoble-ligitaj listo, ni eble bezonas por fari tri aŭ kvar operacioj maks. Sed denove, estas ĉiam tri aŭ kvar. Ne gravas kiom da elementoj estas en nia listo, ĝi estas ĉiam tri aŭ kvar operations-- samkiel forigo ĉiam tri aŭ kvar operacioj. Estas konstanta tempo. Do jen vere granda. 

Kun tabeloj, ni faris io kiel inserción varon. Vi probable memoras ke inserción varo estas ne konstanta tempa algoritmo. Estas efektive sufiĉe multekosta. Do tiu estas multe pli bone por enmeto. Sed, kiel mi menciis en la unuope-ligillisto vídeo, ni hvas downside ĉi tie tro, ĉu ne? Ni perdis la kapablon hazarde aliri elementojn. Ni ne povas diri, mi volas elemento numero kvar aŭ elemento numero 10 de ligitaj listo la sama maniero kiun ni povas fari tion kun tabelo aŭ ni povas nur rekte indekso en nia tabelo la elemento. 

Kaj tiel provas trovi elemento en ligitaj list-- se traserĉado estas important-- Eble nun prenu lineara tempo. Kiel la listo ricevas longa, ĝi povus preni unu plian paŝon por ĉiu unuopa elemento en la listo en Por trovi kion ni serĉas. Do ekzistas komerco offs. Ekzistas iom de avantaĝo kaj con elemento tie. 

Kaj duoble-ligitaj listoj ne estas la lasta speco de datumstrukturo kombinaĵo ke ni parolos pri, prenante ĉiujn bazajn konstruaĵo blokoj de C de kunmetado. Ĉar fakte, ni povas eĉ pli bone ol tio krei datumstrukturo ke vi eble povos traserĉi en konstanta tempo tro. Sed pli en kiuj en alia video. 

Mi Doug Lloyd. Jen CS50.