[CHWARAE CERDDORIAETH] DOUG LLOYD: Pob hawl. Felly, os ydych newydd orffen bod 'n fideo ar restrau yn unigol-cysylltiedig n chwith Gadewais chi oddi ar dipyn o Cliffhanger. Ond rwy'n falch eich bod yma i orffen stori rhestrau ddwbl-gysylltiedig. 

Felly, os ydych yn cofio o hynny fideo, buom yn siarad am y ffordd unigol-cysylltiedig rhestrau yn mynychu ein gallu i ddelio â gwybodaeth lle mae nifer o elfennau neu'r nifer o eitemau yn Gall rhestr dyfu neu crebachu. Gallwn yn awr yn delio â rhywbeth fel 'na, lle y nid oeddem yn gallu ymdrin â hi gyda arrays. 

Ond maent yn dioddef o un cyfyngiad beirniadol sy'n yw y gyda-gysylltiedig yn unigol rhestr, ni allwn ond byth yn symud i gyfeiriad sengl drwy'r rhestr. A'r unig sefyllfa go iawn lle y gall hynny fod yn broblem pan oedd yr oeddem yn ceisio dileu elfen sengl. Ac nid oeddem hyd yn oed yn trafod sut i wneud hynny mewn rhestr unigol-gysylltiedig mewn pseudocode. Mae'n sicr yn doable, ond gall fod yn dipyn o drafferth. Felly, os ydych yn cael eich hun mewn sefyllfa lle ydych yn ceisio dileu elfennau unigol o'r rhestr neu mae'n mynd i fod yn ofynnol y byddwch yn dileu elfennau unigol o y rhestr, efallai y byddwch am ystyried defnyddio-cysylltu'n ddwbl rhestru yn hytrach na rhestr yn unigol-gysylltiedig. Oherwydd bod rhestrau ddwbl-gysylltiedig ydych yn caniatáu i symud ymlaen ac yn ôl drwy'r rhestr yn hytrach na dim ond ymlaen drwy'r list-- dim ond drwy ychwanegu un elfen ychwanegol at ein diffiniad strwythur ar gyfer y rhestr nôd ddwbl-gysylltiedig. 

Unwaith eto, os nad ydych yn mynd i yn cael ei ddileu elfennau unigol o'r list-- oherwydd ein bod yn ychwanegu maes yn ychwanegol at ein strwythur ddiffiniad, y nodau eu hunain ar gyfer rhestrau ddwbl-cysylltiedig yn mynd i fod yn fwy. Maent yn mynd i gymryd mwy o gof bytes. Ac felly os nad yw hyn yn rhywbeth rydych yn mynd i angen iddynt ei wneud, efallai y byddwch yn penderfynu ei fod yn Nid yw yn werth y fasnach off i gael i dreulio'r ychwanegol bytes o gof sy'n ofynnol am restr ddwbl-gysylltu os nad ydych yn mynd i fod yn dileu elfennau unigol. Ond maent hefyd yn oer ar gyfer pethau eraill hefyd. 

Felly, fel y dywedais, rydym yn unig rhaid i ni ychwanegu un maes unigol i'n strwythur definition-- syniad hwn o pwyntydd Blaenorol. Felly, gyda rhestr yn unigol-cysylltiedig, rydym yn yn cael y gwerth a'r pwyntydd Next, felly mae'r rhestr ddwbl-gysylltiedig yn unig wedi ffordd o symud yn ôl hefyd. 

Nawr yn y-gysylltiedig yn unigol Rhestr fideo, buom yn siarad am y rhain yw pump o'r prif bethau y mae angen i chi fod gallu ei wneud i weithio gyda rhestrau cysylltiedig. Ac ar gyfer y rhan fwyaf o'r rhain, mae'r ffaith ei fod yn rhestr ddwbl-cysylltiedig Nid mewn gwirionedd yn naid fawr. Gall Rydym yn dal i chwilio drwy at jyst symud ymlaen o'r dechrau i'r diwedd. Gall Rydym yn dal i greu nod allan o awyr denau, 'n bert lawer yr un ffordd. Gallwn ddileu rhestri 'n bert yr un modd hefyd. Yr unig bethau sy'n yn ychydig yn wahanol, mewn gwirionedd, yn cael eu mewnosod nodau newydd i mewn i'r rhestr, a byddwn yn olaf yn siarad am ddileu elfen unigol o'r rhestr hefyd. Unwaith eto, 'n bert lawer y tri arall, rydym yn Nid yw mynd i siarad am nhw ar hyn o bryd oherwydd eu bod yn unig mân iawn tweaks ar y syniadau a drafodwyd yn y rhestr fideo yn unigol-gysylltiedig. 

Felly gadewch i ni mewnosod nod newydd i mewn i restr ddwbl-gysylltiedig. Rydym yn siarad am wneud hyn ar gyfer rhestrau fesul un-cysylltu'n hefyd, ond mae un neu ddau o ychwanegol dal gyda rhestrau ddwbl-gysylltiedig. Rydym yn [? fynd heibio?] yn y pen y rhestru yma ac mae rhai gwerth mympwyol, ac rydym am gael y pennaeth newydd y rhestr allan o'r swyddogaeth hon. Dyna pam ei bod yn dychwelyd yn seren dllnode. Felly beth yw'r camau? Maent yn, unwaith eto, yn debyg iawn i restrau yn unigol-cysylltiedig gydag un ychwanegiad ychwanegol. Rydym am dyrannu lle ar gyfer newydd nod a gwirio i wneud yn siŵr ei fod yn ddilys. Rydym yn awyddus i lenwi'r nod fyny gyda beth bynnag wybodaeth yr ydym yn eisiau rhoi ynddo. Y peth olaf mae angen i ni do-- i'r beth ychwanegol mae angen i ni ei wneud, rather-- yw i osod y pwyntydd Blaenorol o'r hen bennaeth y rhestr. Cofiwch fod oherwydd bod rhestrau o ddwbl-gysylltiedig, gallwn symud ymlaen ac backwards-- pa yn golygu bod pob nod mewn gwirionedd yn bwyntiau i ddau nodau arall yn hytrach na dim ond un. Ac felly mae angen i ni atgyweiria yr hen bennaeth y rhestr i bwynt yn ôl at y pennaeth newydd y y rhestr cysylltiedig, a oedd yn rhywbeth nad oedd yn rhaid i ni ei wneud o'r blaen. Ac fel o'r blaen, rydym yn unig dychwelyd Pointer i bennaeth newydd y rhestr. 

Felly dyma restr. Rydym am i fewnosod 12 i mewn i rhestr hon. Sylwch fod y diagram ychydig yn wahanol. Mae pob nod yn cynnwys tair fields-- data, ac pwyntydd Next mewn coch, ac mae pwyntydd blaenorol mewn glas. Daw Nid oes dim cyn y 15 nod, felly mae ei pwyntydd blaenorol yn null. Mae'n cychwyn y rhestr. Does dim byd ger ei fron. A dim byd yn dod ar ôl y 10 nod, ac felly mae'n pwyntydd nesaf null hefyd. 

Felly gadewch i ni ychwanegu 12 at y rhestr hon. Mae angen [Anghlywadwy] lle ar gyfer y nôd. Rydym yn rhoi 12 tu mewn iddo. Ac yna eto, mae angen i ni fod yn wirioneddol yn ofalus i beidio i dorri'r gadwyn. Rydym yn awyddus i ad-drefnu arwyddion yn y drefn gywir. Ac weithiau a allai mean-- fel y byddwn yn gweld yn arbennig gyda delete-- a wnawn gael rhywfaint o awgrymiadau ddi-waith, ond mae hynny'n iawn. 

Felly beth ydym ni eisiau ei wneud yn gyntaf? Byddwn yn argymell y pethau dylech yn ôl pob tebyg gwneud yw i lenwi'r awgrymiadau o'r 12 nod cyn i chi gyffwrdd unrhyw un arall. Felly, yr hyn sy'n 12 yn mynd i bwyntio at nesaf? 15. Beth sy'n dod cyn 12? Dim byd. Nawr rydym wedi llenwi'r Gwybodaeth ychwanegol mewn 12 felly mae wedi Blaenorol, Next, a gwerth. 

Nawr gallwn gael 15-- hon ychwanegol cam oeddem yn sôn about-- i ni yn gallu cael 15 pwynt yn ôl i 12. Ac yn awr gallwn symud y pennaeth y rhestr yn gysylltiedig â hefyd fod yn 12. Felly mae'n eithaf tebyg i'r hyn yr ydym yn ei wneud gyda rhestrau unigol-cysylltiedig, ac eithrio ar gyfer y cam ychwanegol o cysylltu'r hen bennaeth y rhestr yn ôl at y pennaeth newydd y rhestr. 

Nawr, gadewch i ni o'r diwedd dileu cainc o restr cysylltiedig. Felly, gadewch i ni ddweud ein bod wedi rhyw swyddogaeth arall sydd yn dod o hyd i nod yr ydym am ddileu'r ac wedi rhoi pwyntydd i union y nôd yr ydym am ddileu. Nid ydym yn hyd yn oed yn dweud y need-- pen yn dal i ddatgan yn fyd-eang. Nid oes angen pen Rydym yma. Mae pob swyddogaeth hon yn ei wneud yw rydym wedi dod o hyd i pwyntydd i'r union y nôd ydym eisiau cael gwared ar. Gadewch i ni gael gwared ohono. Mae'n llawer haws gyda rhestrau ddwbl-gysylltiedig. First-- ei fod mewn gwirionedd dim ond cwpl o bethau. Jyst angen i ni osod y cyfagos awgrymiadau nodau 'fel eu bod yn hepgor y nôd ydym am ddileu. Ac yna gallwn ddileu y nod. Felly unwaith eto, rydym yn jyst yn mynd drwy fan hyn. Mae'n debyg Rydym wedi penderfynu y rydym am ddileu'r X. nôd Ac eto, yr hyn rwy'n gwneud Yma-- gan y way-- yn achos cyffredinol ar gyfer nod sydd yn y canol. Mae un neu ddau o cafeatau ychwanegol y byddwch yn angen ystyried pan fyddwch yn dileu y cychwyn cyntaf y rhestr neu ddiwedd y rhestr. Mae un neu ddau o arbennig achosion cornel i ddelio â yno. 

Felly, mae hyn yn gweithio i ddileu unrhyw node yng nghanol y un list-- sy'n Mae gan pwyntydd dilys ymlaen ac mae pwyntydd dilys yn ôl, cyfreithlon pwyntydd Blaenorol a Nesaf. Unwaith eto, os ydych yn gweithio gyda'r dod i ben, byddwch yn Mae angen i drin y rhai ychydig yn wahanol, ac nid ydym yn mynd i siarad am hynny yn awr. Ond mae'n debyg y gallwch chyfrif i maes beth sydd angen i'w wneud yn unig drwy wylio fideo hwn. 

Felly rydym wedi hynysu X. X yw y nôd rydym eisiau dileu oddi ar y rhestr. Beth ydym yn ei wneud? Yn gyntaf, mae angen i aildrefnu yr awgrymiadau tu allan. Mae angen i ni ail-drefnu 9 yn nesaf i sgip dros 13 a phwynt i 10-- pa yr hyn yr ydym wedi ei wneud yn unig. Ac mae angen i ni hefyd aildrefnu 10 oed Blaenorol i bwyntio i 9 yn lle pwyntio at 13. 

Felly unwaith eto, dyma oedd y diagram i ddechrau. Roedd hyn yn ein cadwyn. Mae angen i ni sgip dros 13, ond mae angen hefyd i warchod uniondeb y rhestr. Nid ydym am i golli unrhyw gwybodaeth yn y ddau gyfeiriad. Felly mae angen i aildrefnu yr awgrymiadau yn ofalus felly nid ydym yn torri'r gadwyn o gwbl. 

Felly, gallwn ddweud 9 yn pwyntydd Nesaf yn cyfeirio at yr un lle bod tri ar ddeg yn Next pwyntydd pwyntiau ar hyn o bryd. Oherwydd ein bod yn y pen draw mynd i eisiau i sgip dros 13. Felly ble bynnag 13 pwynt nesaf, byddwch yn eisiau naw i bwynt yno yn lle hynny. Felly dyna hynny. Ac yna ble bynnag 13 pwynt yn ôl i, beth bynnag a ddaw cyn 13, rydym am 10 i bwynt at hynny yn hytrach na 13. Yn awr yn sylwi, os byddwch yn dilyn y saethau, gallwn alw heibio 13 heb holi i golli unrhyw wybodaeth. Rydym wedi cadw cyfanrwydd y rhestr, symud y ddau ymlaen ac yn ôl. Ac yna y gallwn yn unig fath o lanhau ychydig bach drwy dynnu ar y rhestr at ei gilydd. Felly, rydym yn haildrefnu y awgrymiadau ar y naill ochr. Ac yna rydym yn rhyddhau X y nod a oedd yn cynnwys 13, ac nid oeddem yn torri'r gadwyn. Felly, rydym yn gwneud yn dda. 

Nodyn Terfynol yma ar restrau cysylltiedig. Felly y ddau singly- ac yn ddwbl-cysylltiedig rhestrau, fel yr ydym wedi gweld, cefnogaeth mewnosod 'n sylweddol effeithlon a dileu elfennau. Gallwch 'n bert lawer yn ei wneud mewn pryd gyson. Beth oedd yn rhaid i ni ei wneud i ddileu elfen yn unig eiliad yn ôl? Rydym yn symud un pwyntydd. Rydym yn symud pwyntydd arall. Rydym yn rhyddhau Cymerodd X-- tri gweithrediadau. Mae bob amser yn cymryd tair gweithrediadau i dileu y node-- i ryddhau un nod. 

Sut ydym yn mewnosod? Wel, rydym yn unig bob amser tacio ar y dechrau os ydym yn mewnosod yn effeithlon. Felly mae angen i rearrange-- yn dibynnu ar os yw'n a singly- neu ddwbl-cysylltiedig rhestr, efallai y bydd angen i ni ei wneud tri neu max pedwar gweithrediad. Ond unwaith eto, mae bob amser tri neu bedwar. Nid oes ots faint o elfennau yn ein rhestr, mae bob amser yn dair neu bedair operations-- yn union fel dileu bob amser tri neu pedwar gweithrediad. Mae'n amser yn gyson. Felly dyna wirioneddol wych. 

Gyda araeau, rydym yn ei wneud rhywbeth fel math fewnosod. Mae'n debyg y byddwch yn cofio bod mewnosod Nid yw fath yn algorithm amser cyson. Mae'n mewn gwirionedd yn eithaf drud. Felly, mae hyn yn llawer gwell i fewnosod. Ond fel y soniais yn y yn unigol-gysylltu rhestr fideo, mae gennym anfantais yma hefyd, dde? Rydyn ni wedi colli'r gallu i gael mynediad at elfennau hap. Ni allwn ddweud, yr wyf am yr elfen rhif pedwar neu elfen rif 10 o restr cysylltiedig yr un ffordd y gallwn gwneud hynny gydag amrywiaeth neu a allwn yn unig yn uniongyrchol mynegai i mewn i elfen ein casgliad ar. 

Ac felly ceisio dod o hyd i elfen mewn list-- cysylltiedig os chwilio yn important-- Efallai yn awr yn cymryd amser llinol. Gan fod y rhestr yn cael mwy o amser, mae'n Gallai cymryd un cam ychwanegol ar gyfer pob elfen unigol yn y rhestr yn Er mwyn dod o hyd i beth yr ydym yn chwilio amdano. Felly mae 'na offs masnach. Mae 'na dipyn o pro ac elfen con yma. 

Ac nid y rhestrau ddwbl-gysylltiedig yn cael eu math olaf o gyfuniad strwythur data y byddwn yn siarad am, gan ystyried yr holl adeiladu sylfaenol blociau o C yn rhoi at ei gilydd. Oherwydd yn wir, y gallwn hyd yn oed yn gwneud yn well na hyn i greu strwythur data y efallai y byddwch yn gallu chwilio trwy mewn amser cyson hefyd. Ond yn fwy am hynny yn y fideo arall. 

Rwy'n Doug Lloyd. Mae hyn yn CS50.