[Muzika] DOUG Lloyd: Në rregull. Pra, nëse ju sapo përfundoi se Video në listat e veçmas të lidhura i brengosur Kam lënë ju off në një bit e një cliffhanger. Por unë jam i kënaqur që ju jeni këtu për të përfunduar historia e listave dyfish-lidhura. 

Pra, nëse ju kujtohet nga se video, ne biseduam se si veçmas të lidhura Listat bëjnë pjesë në aftësinë tonë për t'u marrë me informacion ku numri i elementeve ose numri i artikujve në një listë mund të rritet ose tkurret. Ne tani mund të merren me diçka të tillë, ku ne nuk mund të merren me të me vargjeve. 

Por ata vuajnë nga një kufizim kritike që është që me një i lidhur në formë individuale lista, ne mund të lëvizin vetëm ndonjëherë në një drejtim të vetme nëpërmjet lista. Dhe vetëm situata reale ku që mund të bëhet një problem ishte kur ne ishim duke u përpjekur për fshini një element të vetëm. Dhe ne as nuk të diskutuar se si të bëhet kjo në një listë në formë individuale, të lidhura në pseudokod. Kjo sigurisht që është që mund të bëhet, por ajo mund të jetë pak e një sherr. Pra, nëse ju gjeni veten në një situatë ku ju jeni duke u përpjekur për të fshirë Elementet e vetme nga lista ose ajo do të jetë e nevojshme që ju do të fshirjes Elementet vetme nga lista, ju mund të dëshironi të marrin në konsideratë duke përdorur një të-lidhur dyfish lista në vend të një liste veçmas-lidhura. Sepse listat dyfish-lidhura t'ju lejojë për të lëvizur të dy përpara dhe prapa nëpër lista në vend të vetëm përpara përmes list-- vetëm duke shtuar një element shtesë përkufizimit tonë të strukturës për listën dyfish-lidhur nyje. 

Përsëri, në qoftë se ju nuk jeni duke shkuar për të të fshirjes elemente të vetme nga list--, sepse ne jemi duke shtuar një fushë shtesë për strukturën tonë Përkufizimi, vetë nyjet për listat dyfish-lidhura do të jetë më e madhe. Ata janë duke shkuar për të marrë deri më byte memorje. Dhe kështu që në qoftë se kjo nuk është diçka ju jeni do të duhet për të bërë, ju mund të vendosë se është nuk ia vlen të tregtisë off që duhet të kalojnë ekstra byte memorje kërkuara për një listë dyfish-lidhur në qoftë se ju nuk jeni do të jetë e fshirjes elemente të vetme. Por ata janë gjithashtu të ftohtë për gjëra të tjera shumë. 

Pra, siç thashë, ne vetëm duhet të shtoni një fushë e vetme në strukturën tonë definition-- këtë nocion një tregues i mëparshëm. Pra, me një listë në formë individuale-lidhura, ne kanë vlerën dhe treguesin tjetër, kështu lista dyfish i lidhur vetëm ka një mënyrë për të lëvizur prapa si. 

Tani në formë individuale të lidhura Lista Video, kemi biseduar në lidhje me këto janë pesë nga gjëra kryesore që ju duhet të jenë të në gjendje të bëjë për të punuar me listat e lidhura. Dhe për shumicën e këtyre, fakti se kjo është një listë dyfish i lidhur nuk është me të vërtetë një kërcim i madh. Ne ende mund të kërkoni përmes nga vetëm duke shkuar përpara nga fillimi në fund. Ne ende mund të krijojë një nyje jashtë ajrit hollë, shumë e shumë të njëjtën mënyrë. Ne mund të fshini listat goxha shumë të njëjtën mënyrë shumë. Të vetmet gjëra që janë të Subtly të ndryshme, me të vërtetë, janë futur nyjet e reja në listë, dhe ne fund do të flasim rreth fshirjes një element të vetme nga lista si. Përsëri, shumë e shumë tre të tjerët, ne jemi nuk do të flasim për to tani, sepse ata janë vetëm tweaks shumë të vogla në idetë diskutua në listën veçmas të lidhura me video. 

Pra, le të futur një nyje të re në një listë dyfish-lidhura. Kemi biseduar për të bërë këtë për listat veçmas të lidhura, si dhe, por ka disa ekstra kap me listat dyfish-lidhura. Ne jemi [? kaluar?] në kokën e të lista këtu dhe disa vlera arbitrare, dhe ne duam që të merrni kreun e ri e listës jashtë këtij funksioni. Kjo është arsyeja pse ajo kthehet një yll dllnode. Pra, çfarë janë hapat? Ata janë, përsëri, shumë të ngjashme për listat veçmas të lidhura me një shtesë ekstra. Ne duam që të ndan hapësirë ​​për një të ri nyje dhe kontrolloni për t'u siguruar se është e vlefshme. Ne duam për të mbushur atë nyje deri me çfarëdo informacioni ne duan të vënë në të. Gjëja e fundit që ne kemi nevojë për do-- gjë ekstra ne duhet të bëjmë, rather-- është për të rregulluar treguesin mëparshme e kreut të vjetër të listës. Mos harroni se për shkak se Listat e dyfish-lidhura, ne mund të lëvizin përpara dhe backwards-- që do të thotë se çdo nyje në fakt vë në të dy nyjet e tjera në vend të vetëm një. Dhe kështu që ne kemi nevojë për të rregulluar kreu i vjetër i listës për pikë prapa për të kreut të ri të lista e lidhur, e cila ishte diçka ne nuk kemi për të bërë para. Dhe si më parë, ne vetëm të kthehet një tregues për kreun e ri të listës. 

Kështu që këtu është një listë. Ne duam të futur 12 në këtë listë. Vini re se diagrami është paksa e ndryshme. Çdo nyjë përmban tre fields-- të dhënave, dhe një tregues tjetër në të kuqe, dhe një tregues e mëparshme në ngjyrë blu. Asgjë nuk vjen para 15 nyje, kështu akrep e tij të mëparshme është i pavlefshëm. Është fillimi i listës. Nuk ka asgjë para tij. Dhe asgjë nuk vjen pas 10 nyje, dhe kështu që është tregues tjetër është i pavlefshëm si. 

Pra, le të shtoni 12 në këtë listë. Ne kemi nevojë për [padëgjueshme] hapësirë ​​për nyjen. Ne kemi vënë 12 në brendësi të saj. Dhe pastaj përsëri, ne duhet të jetë me të vërtetë kujdesshëm për të mos për të thyer zinxhirin. Ne duam të korrigjoj pointers në mënyrë korrekte. Dhe nganjëherë kjo mund të mean-- si ne do të shohim veçanërisht me delete-- se ne kemi disa pointers tepërt, por kjo është në rregull. 

Pra, çfarë duam të bëjmë për herë të parë? Unë do të rekomandojë Gjërat që ju duhet ndoshta bëjnë janë për të plotësuar pointers e 12 nyje para se të prek dikush tjetër. Pra, çfarë është 12 do të tregojnë për tjetër? 15. Çfarë vjen para 12? Asgjë. Tani ne kemi mbushur informacion shtesë në 12 kështu që ka mëparshëm, Next, dhe vlera. 

Tani ne mund të kemi 15-- këtë shtesë hap ne ishim duke folur? Për ne mund të ketë 15 pikë prapa në 12. Dhe tani ne mund të lëvizin kokën e lista e lidhur të jetë edhe 12. Pra, kjo është goxha e ngjashme me atë që ne janë bërë me listat në formë individuale, të lidhura, me përjashtim të hapit shtesë të lidh kreun e vjetër e listës Kthehu në kreun e ri të listës. 

Tani le të më në fund të fshini një nyje nga një listë e lidhur. Pra, le të thonë se ne kemi disa funksion tjetër që është gjetur një nyje ne duam të fshini dhe na ka dhënë një tregues për pikërisht nyja që dëshironi të fshini. Ne as nuk need-- thonë se kokë është shpallur ende në nivel global. Ne nuk kemi nevojë kokën këtu. E gjithë ky funksion është duke bërë është që ne kemi gjeti një tregues për pikërisht në nyjen ne duan të heqin qafe e. Le të të shpëtoj prej tij. Kjo është një shumë më e lehtë me listat dyfish të lidhura. First-- është e vërtetë vetëm disa gjëra. Ne vetëm duhet për të rregulluar përreth Nyjet 'pointers në mënyrë që ata të kaloni mbi nyja ne duam të fshini. Dhe pastaj ne mund të fshini këtë nyje. Pra, përsëri, ne jemi vetëm duke kaluar nëpër këtu. Ne kemi vendosur me sa duket se ne duam të fshini nyjen X. Dhe përsëri, ajo që unë jam bërë here-- nga way-- është një rast i përgjithshëm për një nyje që është në mes. Nuk janë një çift i përjashtime shtesë që ju duhet të marrë parasysh kur ju jeni fshirjes fillimi shumë të listës ose në fund të listës. Ka një çift i veçantë Rastet qoshe për t'u marrë me të atje. 

Pra, kjo punon për fshirjes çdo nyje në mes të një list-- që ka një tregues legjitim përpara dhe një akrep legjitime prapambetur, legjitime akrep mëparshëm dhe të ardhshëm. Përsëri, në qoftë se ju jeni duke punuar me skajet, ju nevojë për të trajtuar ato pak më ndryshe, dhe ne nuk jemi duke shkuar për flasim për këtë tani. Por ju mund ndoshta kuptoj se çfarë duhet të bëhet vetëm duke shikuar këtë video. 

Pra, ne kemi izoluar X. X është nyja ne duam të fshini nga lista. Çfarë bëjmë ne? Së pari, ne duhet të korrigjoj pointers jashtë. Ne duhet të korrigjoj 9 e ardhshme për të kaloni mbi 13 dhe pika të cilat 10-- është ajo që ne kemi bërë vetëm. Dhe ne gjithashtu duhet të korrigjoj 10 e mëparshme të tregojnë për 9 në vend të treguar në 13. 

Pra, përsëri, ky ishte Diagrami për të filluar me. Kjo ishte zinxhir ynë. Ne duhet të kaloni mbi 13, por ne kemi nevojë për të ruajtur edhe integritetin e listës. Ne nuk duan të humbin ndonjë informacion në asnjë drejtim. Pra, ne duhet të korrigjoj pointers me kujdes kështu që ne nuk e thyejnë zinxhirin fare. 

Pra, ne mund të themi 9 për treguesin tjetër vë në të njëjtin vend se trembëdhjetë Next akrep tregon tani. Sepse ne jemi në fund do të dëshironi të kaloni mbi 13. Pra, kudo që 13 pikë tjetër, ju dua nëntë të theksoj aty në vend. Pra, kjo është ajo. Dhe pastaj kudo që 13 pikë prapa për të, çfarëdo që vjen para 13, ne duam 10 të theksoj për të që në vend të 13. Tani vini re, në qoftë se ju ndiqni shigjetat, ne mund të bjerë 13 në fakt pa humbur asnjë informacion. Ne e kemi mbajtur integritetin e listës, lëviz të dy përpara dhe prapa. Dhe pastaj ne mund vetëm lloj e pastruar atë pak duke tërhequr listën së bashku. Pra, ne riorganizohet pointers në të dyja anët. Dhe pastaj ne liruar X nyje që përmbante 13, dhe ne nuk e thyejnë zinxhirin. Pra, ne e bëmë mirë. 

Shënim i fundit këtu në listat e lidhura. Kështu që të dy singly- dhe dyfish të lidhura listat, siç e kemi parë, Mbështetja futje të vërtetë efikas dhe fshirjen e elementeve. Ju mund të pretty much të bëjë ajo në kohë të vazhdueshme. Çfarë duhet të bëjmë për të fshirë një element i vetëm një të dytë më parë? Ne kemi lëvizur një akrep. Ne kemi lëvizur një akrep. Ne liruar X-- mori tre operacione. Ajo gjithmonë merr tre operacione të fshini se node-- për të liruar një nyje. 

Si nuk kemi futur? E pra, ne jemi gjithmonë të vetëm tacking në fillim në qoftë se ne jemi duke futur në mënyrë efikase. Pra, ne kemi nevojë për të rearrange-- në varësi të nëse është një singly- ose dyfish të lidhura lista, ne mund të kenë nevojë për të bërë tre ose katër operacione max. Por përsëri, kjo është gjithmonë tre ose katër. Nuk ka rëndësi se sa shumë Elementet janë në listën tonë, ajo është gjithmonë tre ose katër operations-- ashtu si fshirje është gjithmonë tre ose katër operacione. Është koha konstante. Pra, kjo është me të vërtetë e madhe. 

Me vargjeve, ne ishim duke bërë diçka si futje lloji. Ju ndoshta kujtoni se shtënie lloj nuk është një algoritëm konstante kohë. Kjo është në fakt goxha i shtrenjtë. Pra, kjo është shumë më mirë për të futur. Por, siç e përmenda në veçmas të lidhura me lista video të, ne kemi marrë një dobësitë edhe këtu, apo jo? Ne e kemi humbur aftësinë për rastësisht hyrë elemente. Ne nuk mund të themi, unë dua numër element katër ose element numër 10 i një liste të lidhur në të njëjtën mënyrë që ne mund të të bëjë që me një grup ose ne mund vetëm të drejtpërdrejtë indeksi në elementin array tonë. 

Dhe kështu u përpjekur për të gjetur një element në një list-- lidhur në qoftë se në kërkim është important-- tani mund të marrë kohë lineare. Si lista merr më të gjatë, ajo mund të marrë një hap shtesë për çdo element të vetme në listën e mënyrë që të gjeni atë që ne jemi duke kërkuar për. Pra, ka të humbura të tregtisë. Nuk është pak e një pro dhe element con këtu. 

Dhe listat dyfish-lidhura jo janë lloj i fundit i kombinimit strukturës dhënave që ne do të flasim, duke marrë të gjitha ndërtimin themelore blloqe C një vënien së bashku. Sepse në fakt, ne mund të edhe të bëjë më mirë se ky për të krijuar një strukturë të dhënave që ju mund të jetë në gjendje për të kërkuar përmes në kohë të vazhdueshme shumë. Por më shumë se në një tjetër video. 

Unë jam Doug Lloyd. Kjo është CS50.