[Glazbom] Doug LLOYD: U redu. Dakle, ako ste upravo završili da Video o jednostruko-povezanim popisima žao Te ostavio sam off na malo Cliffhanger. Ali drago mi je da ste ovdje završiti priča o dvostruko povezane liste. 

Dakle, ako se sjećate iz taj video, razgovarali smo kako pojedinačno povezani popisi ne pohađaju našu sposobnost da se bave informacijama gdje je broj elemenata ili broj predmeta u popis može rasti ili smanjivati. Sada možemo nositi s nešto slično, gdje nismo mogli nositi s njom s polja. 

Ali oni ne pate od jedne kritično ograničenje koje je da se uz pojedinačno povezani Popis, možemo samo uvijek kretati u jednom smjeru kroz listu. A jedini pravi stanje gdje da može postati problem bio je kada smo pokušali Brisanje jednog elementa. A nismo ni razgovarali o tome kako to učiniti u popisu pojedinačno-povezane u pseudokod. To je svakako izvodljiv, ali to može biti malo gnjavaža. Dakle, ako se nađete u situaciji u kojoj pokušavate izbrisati pojedinačni elementi iz popisa ili će to biti potrebno da ćete se brisanje pojedinačni elementi iz popis, možda želite razmotriti pomoću dvostruko povezani popis, umjesto popisa za jednostruko-povezane. Zbog dvostruko povezani popisi omogućuju vam premjestiti oba naprijed i natrag kroz popis, umjesto Samo naprijed kroz list-- Samo dodavanjem jednog dodatni element u našu definiciju strukture za dvostruko povezane liste čvora. 

Opet, ako ne ide na se brisanje pojedinačnih elemenata iz list-- jer mi dodajemo dodatni polje našem strukture definiciji, sami čvorovi za dvostruko povezane liste će biti veća. Oni će uzeti se više bajtova memorije. I tako, ako to nije nešto ti si idući u morati učiniti, možda odlučiti da je nije vrijedno trgovina off morati provesti extra bajta memorije potrebne za popis dvostruko povezana ako niste će se brisanje pojedinačne elemente. Ali oni su također super za druge stvari. 

Dakle, kao što sam rekao, samo moramo dodati jedan jedini polje našem strukture definition-- ovaj pojam prethodne pokazivača. Tako je s popisa za jednostruko povezanom smo imaju vrijednost i sljedeći pokazivač, tako da je popis dvostruko povezana je upravo način za pomicanje unatrag, kao dobro. 

Sada se u pojedinačno-linked Popis videa, razgovarali smo o su pet od Glavne stvari koje trebate biti u mogućnosti to učiniti za rad s povezanim popisima. A za većinu tih, činjenice da je popis s dvostruko povezani zapravo i nije veliki skok. Još uvijek možete pretraživati ​​po samo kreće naprijed od početka do kraja. Još uvijek možete stvoriti čvor iz zraku, prilično mnogo na isti način. Možemo brisati popise lijepa mnogo na isti način previše. Jedine stvari koje su suptilno različita, stvarno su umetanje novi čvorovi u popisu, pa ćemo napokon razgovarati o brisanju jedan element iz ljestvicu. Opet, prilično mnogo ostale tri, mi smo ne ide razgovarati o njima upravo sada, jer oni su samo vrlo male tweaks na idejama raspravlja u pojedinačno-povezanog popisa videozapisa. 

Tako ćemo umetnuti novi čvor u popisu dvostruko povezani. Razgovarali smo o to za pojedinačno povezani liste i, ali ima par extra hvata s dvostruko povezanim popisima. Mi smo [? prolazi?] u glavi od popis ovdje, a neke proizvoljne vrijednosti, i želimo dobiti novu glavu popisa iz ove funkcije. Zato vraća dllnode zvijezdu. Pa što su koraci? Oni su, opet, vrlo sličan za pojedinačno povezani liste s pomoćnim toga. Želimo dodjeljuje prostor za nova čvor i provjera kako bi bili sigurni da je valjana. Želimo ispuniti tu čvor se sa što informacije koje želite staviti u njega. Zadnje što trebamo do-- extra stvar koju trebate učiniti, rather-- je popraviti Prethodna pokazivač stare glave popisa. Zapamtite da zbog od dvostruko povezane liste, možemo krenuti naprijed i backwards-- koji znači da je svaki čvor zapravo ukazuje druga dva čvora, umjesto samo jednog. I tako moramo popraviti stari šef popisa ukazati natrag na novu glavu popis povezani, što je nešto nismo imali za napraviti prije. A kao i prije, samo smo se vratiti pokazivač na novu glavu na popisu. 

Dakle, ovdje je popis. Želimo umetnuti 12 u ovaj popis. Obavijest da je dijagram je malo drugačija. Svaki čvor ima tri fields-- podataka, a Sljedeća pokazivač crveno, a Prethodna pokazivač u plavom. Ništa dolazi prije 15 čvora, tako da je njegova Prethodna pointer je null. To je početak popisa. Nema ništa prije njega. I ništa ne dolazi nakon 10 čvora, te tako da je kazaljka Sljedeća je ništavan, kao dobro. 

Tako ćemo dodati 12 na ovaj popis. Trebamo [nečujan] prostor za čvor. Mi smo stavili 12 unutar nje. A onda opet, moramo biti jako Pazite da ne razbiti lanac. Želimo preurediti upućuje u ispravnom redoslijedu. A ponekad da bi mogli mean-- kao što ćemo vidjeti posebno s delete-- da imamo neke suvišne pokazivače, ali to je u redu. 

Dakle, ono što želimo učiniti prvi? Ja bih preporučiti stvari koje bi trebali vjerojatno to su popuniti naputke od 12 čvor prije nego što dodirnete bilo tko drugi. Pa što je 12 će ukazati na sljedeće? 15. Što dolazi prije 12? Ništa. Sada smo ispuni dodatne informacije u 12 tako da ima Prethodna, sljedeći, i vrijednosti. 

Sada možemo imati 15-- ovaj dodatni korak smo razgovarali about-- mi može imati 15 bod natrag na 12. I sada možemo pomaknuti glavu popis povezani i da se 12. Dakle, to je prilično slično onome što smo radili s pojedinačno-povezane liste, osim za dodatni korak povezivanje staru glavu na popis Natrag na novog šefa popisa. 

Sada ćemo konačno brisanje čvor s popisa povezane. Tako recimo imamo neke druge funkcije koje je pronalaženje čvor želimo obrisati i da nam je dao pokazivač na točno čvor koji želimo izbrisati. Mi ni ne need-- reći Glava je još uvijek globalno proglašen. Ne trebamo glavu ovdje. Sve to omogućuje radi je imamo pronašao pokazivač na točno čvor mi Želite se riješiti. Idemo dobiti osloboditi od njega. To je puno lakše s dvostruko povezane liste. First-- to je zapravo samo par stvari. Mi samo trebate popraviti okolno čvorovi 'pokazivače tako da oni preskaču čvor želimo izbrisati. A onda možemo izbrisati taj čvor. Pa opet, mi samo idemo ovuda. Mi očito su odlučili da želimo izbrisati čvor X. I opet, što sam radi here-- od way-- je opći slučaj za čvor koji je u sredini. Postoji nekoliko dodatni upozorenja da morate uzeti u obzir kada ste brisanja samog početka popisa ili samom kraju liste. Postoji nekoliko posebna Kutak za slučajeve da se bave tamo. 

Tako to radi za brisanje bilo čvor u sredini onoga koji list-- ima legitiman pokazivač naprijed i legitimna pokazivač unatrag, legitimna Prethodna Sljedeća i pokazivač. Opet, ako radite s krajevima, što morati nositi one malo drugačije, i nećemo se razgovarati o tome sada. Ali vjerojatno možete shvatiti što treba treba učiniti samo gledajući ovaj video. 

Tako smo izolirani X. X čvor želimo izbrisati s popisa. Što nam je činiti? Prvo, moramo preurediti vanjski naputke. Moramo preurediti 9 je uz preskočiti 13 a točka na kojoj 10-- je ono što smo upravo učinili. I mi također trebaju preurediti 10 prethodnih ukazati na 9 umjesto ukazujući na 13. 

Pa opet, to je bio dijagram za početak. To je bio naš lanac. Moramo preskočiti 13, ali moramo i sačuvati cjelovitost popisa. Mi ne želimo izgubiti bilo Informacije u oba smjera. Dakle, moramo preurediti se upućuje pozorno tako da ne razbiti lanac na sve. 

Tako možemo reći je sljedeće pokazivač 9 ukazuje na isto mjesto da trinaest je sljedeće pokazivač ističe upravo sada. Budući da smo na kraju će htjeti preskočiti 13. Dakle, gdje god je 13 bodova Sljedeći, te Želite devet ukazati tamo umjesto. Dakle, to je to. A onda gdje god 13 bodova natrag da, sve što dolazi prije 13 godina, želimo ukazati 10 da da, umjesto 13. Sada primijetite, ako slijedite strelice, možemo ispustiti 13 zapravo bez gubitka podataka. Mi smo zadržao cjelovitost popisa, kreće i naprijed i nazad. A onda možemo samo vrsta ga počistiti malo povlačenjem popis zajedno. Tako smo preuredio upućuje na obje strane. A onda smo oslobodili x čvor koji je sadržavao 13, a nismo razbiti lanac. Dobar Tako smo i učinili. 

Završna napomena ovdje na povezanim popisima. Tako i singly- i dvostruko povezani popisi, kao što smo vidjeli, Podrška jako učinkovit umetanje i brisanje elemenata. Možete prilično mnogo učiniti je u stalnom vremenu. Što moramo učiniti za brisanje element samo sekundu prije? Preselili smo jedan pokazivač. Krenuli smo još jedan pokazivač. Oslobođeni smo X-- uzeo tri operacije. Uvijek traje tri operacije na izbrišite node-- da oslobodi čvor. 

Kako umetnuti? Pa, mi smo samo uvijek letanja na početku Ako smo umetanje učinkovito. Dakle, moramo rearrange-- ovisno o tome je li to singly- ili dvostruko povezani Popis, možda moramo učiniti tri ili četiri operacije max. Ali opet, to je uvijek tri ili četiri. Nije bitno koliko je elementi u našem listu, to je uvijek tri ili četiri operations-- baš kao i brisanje je uvijek tri ili četiri operacije. To je konstanta vrijeme. Dakle, to je stvarno super. 

S polja, bili smo radili nešto poput umetanja vrste. Vjerojatno se sjetiti da je umetanje vrsta nije konstantna vremena algoritam. To je zapravo prilično skupo. Dakle, ovo je puno bolje za umetanje. Ali kao što sam spomenuo u pojedinačno povezani popis videozapisa, imamo downside ovdje, zar ne? Mi smo izgubili sposobnost slučajno pristupiti elemente. Ne možemo reći, želim elementa broj četiri ili je element broj 10 od popisa povezan isti način na koji možemo učiniti da se s nizom ili možemo jednostavno izravno indeksa u našu Array u elementu. 

I tako pokušava pronaći element u povezanom list-- Ako potrazi je important-- Sada mogu uzeti linearno vrijeme. Kao popis dobiva više, to možda uzeti jedan dodatni korak za svaki pojedini element u popisu u kako bi se pronašli ono što tražite. Dakle, postoji trgovina off. Tu je malo pro i protiv elementa ovdje. 

A dvostruko povezani popisi nisu Posljednji vrsta kombinacije strukture podataka da ćemo razgovarati, da sve osnovne zgrade blokovi C stavljajući zajedno. Jer, u stvari, možemo čak i bolje od toga stvoriti strukturu podataka koji možda ćete biti u mogućnosti da pretraživanje u stalnom vrijeme previše. No, više o tome u drugom videu. 

Ja sam Doug Lloyd. Ovo je CS50.