1 00:00:00,000 --> 00:00:03,381 >> [MUSIK SPELA] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD: Okej. 4 00:00:05,520 --> 00:00:07,860 Så om du precis avslutat att video på enstaka-länkade listor sorry 5 00:00:07,860 --> 00:00:09,568 Jag lämnade dig ut på en bit av en cliffhanger. 6 00:00:09,568 --> 00:00:12,790 Men jag är glad att du är här för att avsluta berättelsen om dubbelt-länkade listor. 7 00:00:12,790 --> 00:00:15,250 >> Så om du minns från att video, vi pratade 8 00:00:15,250 --> 00:00:18,500 om hur enstaka bunden listor gör delta i vår förmåga 9 00:00:18,500 --> 00:00:22,090 att ta itu med uppgifter där antalet element 10 00:00:22,090 --> 00:00:24,442 eller antalet artiklar i en lista kan växa eller krympa. 11 00:00:24,442 --> 00:00:26,400 Vi kan nu ta itu med något liknande, där 12 00:00:26,400 --> 00:00:28,310 Vi kunde inte ta itu med det med arrayer. 13 00:00:28,310 --> 00:00:30,560 >> Men de lider av en kritisk begränsning som 14 00:00:30,560 --> 00:00:33,790 är att med en enstaka bunden lista, kan vi bara någonsin flytta 15 00:00:33,790 --> 00:00:36,200 i en enda riktning genom listan. 16 00:00:36,200 --> 00:00:39,010 Och det enda verkliga situationen där detta kan bli ett problem 17 00:00:39,010 --> 00:00:41,250 var när vi försökte radera ett enskilt element. 18 00:00:41,250 --> 00:00:46,000 Och vi inte ens diskutera hur man gör det i en enkelt-länkad lista i pseudokod. 19 00:00:46,000 --> 00:00:48,797 Det är förvisso genomförbart, men Det kan vara lite av ett besvär. 20 00:00:48,797 --> 00:00:50,630 Så om du befinner dig i en situation där 21 00:00:50,630 --> 00:00:53,175 du försöker ta bort enskilda element från listan 22 00:00:53,175 --> 00:00:55,430 eller det kommer att krävas att du kommer att ta bort 23 00:00:55,430 --> 00:00:57,970 enskilda element från listan, kanske du vill 24 00:00:57,970 --> 00:01:02,090 överväga att använda en dubbelbunden lista istället för en enstaka-länkad lista. 25 00:01:02,090 --> 00:01:06,320 Eftersom dubbelt-länkade listor låter dig att flytta både framåt och bakåt 26 00:01:06,320 --> 00:01:09,340 igenom listan i stället för bara framåt genom list-- 27 00:01:09,340 --> 00:01:13,950 bara genom att lägga en extra inslag till vår struktur definition 28 00:01:13,950 --> 00:01:16,690 för det två gånger länkad lista nod. 29 00:01:16,690 --> 00:01:19,770 >> Återigen, om du inte kommer att att ta bort enskilda element 30 00:01:19,770 --> 00:01:24,810 från list-- eftersom vi lägger ett extra fält till vår struktur 31 00:01:24,810 --> 00:01:28,340 definition, noderna själva för dubbelt-länkade listor 32 00:01:28,340 --> 00:01:29,550 kommer att bli större. 33 00:01:29,550 --> 00:01:31,600 De kommer att ta upp fler byte minne. 34 00:01:31,600 --> 00:01:34,160 Och så om detta inte är något du kommer att behöva göra, 35 00:01:34,160 --> 00:01:36,300 du kan besluta att det är inte värt avvägning 36 00:01:36,300 --> 00:01:39,360 att behöva spendera extra byte av minne som krävs 37 00:01:39,360 --> 00:01:43,940 för en dubbelbunden listan om du inte kommer att radera enskilda element. 38 00:01:43,940 --> 00:01:46,760 Men de är också coolt för andra saker också. 39 00:01:46,760 --> 00:01:51,260 >> Så som sagt, vi måste bara lägga ett enda fält till vår struktur 40 00:01:51,260 --> 00:01:55,360 definition-- detta begrepp av en tidigare pekare. 41 00:01:55,360 --> 00:01:58,620 Så med en enkelt-länkad lista, vi har värdet och nästa pekaren, 42 00:01:58,620 --> 00:02:02,850 så de två gånger länkad lista har bara ett sätt att gå bakåt också. 43 00:02:02,850 --> 00:02:04,960 >> Nu i den ensamma bundna videolistan, vi pratade 44 00:02:04,960 --> 00:02:07,210 om dessa är fem av viktigaste saker du behöver vara 45 00:02:07,210 --> 00:02:09,449 kunna göra för att arbeta med länkade listor. 46 00:02:09,449 --> 00:02:12,880 Och för de flesta av dessa, det faktum att det är en dubbelbunden listan 47 00:02:12,880 --> 00:02:14,130 är egentligen inte ett stort hopp. 48 00:02:14,130 --> 00:02:17,936 Vi kan fortfarande söka igenom genom att bara framåt från början till slut. 49 00:02:17,936 --> 00:02:20,810 Vi kan fortfarande skapa en nod ur tunn luft, ungefär samma sätt. 50 00:02:20,810 --> 00:02:23,591 Vi kan ta bort listor ganska ungefär på samma sätt också. 51 00:02:23,591 --> 00:02:25,340 De enda saker som är subtilt annorlunda, 52 00:02:25,340 --> 00:02:28,970 verkligen, sätter nya noder i listan, 53 00:02:28,970 --> 00:02:33,722 och vi kommer slutligen tala om att ta bort en enda element från listan också. 54 00:02:33,722 --> 00:02:35,430 Igen, ganska mycket de andra tre, vi är 55 00:02:35,430 --> 00:02:37,888 kommer inte att tala om dem just nu eftersom de är bara 56 00:02:37,888 --> 00:02:43,920 mycket små tweaks på de idéer diskuteras i enstaka bundna videolistan. 57 00:02:43,920 --> 00:02:46,292 >> Så låt oss sätta en ny nod in i ett dubbelt-länkad lista. 58 00:02:46,292 --> 00:02:48,750 Vi pratade om att göra detta för enskilt bundna listor samt, 59 00:02:48,750 --> 00:02:52,020 men det finns ett par extra fångster med dubbel-länkade listor. 60 00:02:52,020 --> 00:02:55,280 Vi är [? passerar?] i huvudet av lista här och några godtyckligt värde, 61 00:02:55,280 --> 00:02:58,600 och vi vill få ny chef av förteckningen av denna funktion. 62 00:02:58,600 --> 00:03:01,414 Det är därför det returnerar en dllnode stjärna. 63 00:03:01,414 --> 00:03:02,330 Så vad är stegen? 64 00:03:02,330 --> 00:03:04,496 De är, igen, mycket liknande att ensamma länkade listor 65 00:03:04,496 --> 00:03:05,670 med ett extra tillägg. 66 00:03:05,670 --> 00:03:08,900 Vi vill allokerar utrymme för en ny nod och kontroll för att se till att det är giltigt. 67 00:03:08,900 --> 00:03:11,510 Vi vill fylla den noden upp med den information vi 68 00:03:11,510 --> 00:03:12,564 vill sätta i det. 69 00:03:12,564 --> 00:03:15,480 Det sista vi behöver do-- den extra sak som vi måste göra, rather-- 70 00:03:15,480 --> 00:03:19,435 är att fastställa föregående pekaren av den gamla chef för listan. 71 00:03:19,435 --> 00:03:21,310 Kom ihåg att eftersom av dubbelt-länkade listor, 72 00:03:21,310 --> 00:03:23,110 vi kan gå vidare och backwards-- vilka 73 00:03:23,110 --> 00:03:27,080 betyder att varje nod som faktiskt pekar till två andra noder i stället för bara en. 74 00:03:27,080 --> 00:03:29,110 Och så måste vi fixa den gamla chef på listan 75 00:03:29,110 --> 00:03:32,151 att peka bakåt till ny chef för den länkade listan, vilket var något 76 00:03:32,151 --> 00:03:33,990 Vi behövde inte göra innan. 77 00:03:33,990 --> 00:03:37,420 Och som tidigare, vi bara tillbaka en pekare till ny chef för listan. 78 00:03:37,420 --> 00:03:38,220 >> Så här är en lista. 79 00:03:38,220 --> 00:03:40,144 Vi vill infoga 12 i den här listan. 80 00:03:40,144 --> 00:03:42,060 Lägg märke till att diagrammet är något annorlunda. 81 00:03:42,060 --> 00:03:47,710 Varje nod innehåller tre fields-- data och en nästa pekare i rött, 82 00:03:47,710 --> 00:03:50,170 och en Föregående pekaren i blått. 83 00:03:50,170 --> 00:03:54,059 Ingenting kommer före 15 noden, så dess Föregående pekare är noll. 84 00:03:54,059 --> 00:03:55,350 Det är början av listan. 85 00:03:55,350 --> 00:03:56,560 Det finns inget innan det. 86 00:03:56,560 --> 00:04:03,350 Och ingenting kommer efter 10 noden, och så det är nästa pekare är noll också. 87 00:04:03,350 --> 00:04:05,616 >> Så låt oss lägga 12 till denna lista. 88 00:04:05,616 --> 00:04:08,070 Vi behöver [OHÖRBAR] utrymme för noden. 89 00:04:08,070 --> 00:04:11,480 Vi lägger 12 inne i den. 90 00:04:11,480 --> 00:04:14,840 Och sen igen, måste vi vara riktigt noga med att inte bryta kedjan. 91 00:04:14,840 --> 00:04:17,144 Vi vill ordna pekare i rätt ordning. 92 00:04:17,144 --> 00:04:19,519 Och ibland som kan mean-- som vi kommer att se särskilt 93 00:04:19,519 --> 00:04:24,120 med delete-- att vi har några redundanta pekare, men det är OK. 94 00:04:24,120 --> 00:04:25,750 >> Så vad vill vi göra först? 95 00:04:25,750 --> 00:04:28,290 Jag skulle rekommendera saker du bör förmodligen 96 00:04:28,290 --> 00:04:35,350 göra är att fylla pekare av 12 nod innan du rör någon annan. 97 00:04:35,350 --> 00:04:38,640 Så vad är 12 kommer att peka på nästa? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 Vad kommer före den 12? 100 00:04:42,430 --> 00:04:43,640 Ingenting. 101 00:04:43,640 --> 00:04:46,280 Nu har vi fyllt extra information i 12 102 00:04:46,280 --> 00:04:49,320 så det har Föregående, Nästa och värde. 103 00:04:49,320 --> 00:04:53,505 >> Nu kan vi ha 15-- denna extra steg vi talade about-- vi 104 00:04:53,505 --> 00:04:56,590 kan ha 15 poäng tillbaka till 12. 105 00:04:56,590 --> 00:04:59,634 Och nu kan vi flytta chefen för länklistan också vara 12. 106 00:04:59,634 --> 00:05:02,550 Så det är ganska likt det vi gjorde med ensamma-länkade listor, 107 00:05:02,550 --> 00:05:06,940 med undantag för det extra steget att ansluter gamla chef på listan 108 00:05:06,940 --> 00:05:09,810 tillbaka till ny chef för listan. 109 00:05:09,810 --> 00:05:12,170 >> Nu äntligen bort en nod från en länkad lista. 110 00:05:12,170 --> 00:05:14,350 Så låt oss säga att vi har någon annan funktion som 111 00:05:14,350 --> 00:05:18,080 är att hitta en nod vi vill radera och har gett oss en pekare till exakt 112 00:05:18,080 --> 00:05:19,710 noden som vi vill ta bort. 113 00:05:19,710 --> 00:05:22,360 Vi vet inte ens need-- säga Huvudet är fortfarande globalt deklareras. 114 00:05:22,360 --> 00:05:23,590 Vi behöver inte huvudet här. 115 00:05:23,590 --> 00:05:26,830 Allt detta funktionen gör är att vi har hittade en pekare till exakt noden vi 116 00:05:26,830 --> 00:05:28,090 vill bli av med. 117 00:05:28,090 --> 00:05:28,940 Låt oss bli av med det. 118 00:05:28,940 --> 00:05:31,859 Det är mycket enklare med dubbelt länkade listor. 119 00:05:31,859 --> 00:05:33,650 First-- det är faktiskt bara ett par saker. 120 00:05:33,650 --> 00:05:38,760 Vi behöver bara fixa det omgivande noder "pekare så att de hoppa över 121 00:05:38,760 --> 00:05:40,240 noden vill vi ta bort. 122 00:05:40,240 --> 00:05:43,484 Och då kan vi ta bort den noden. 123 00:05:43,484 --> 00:05:45,150 Så återigen, vi bara gå igenom här. 124 00:05:45,150 --> 00:05:49,625 Vi har uppenbarligen bestämt att Vi vill ta bort noden X. 125 00:05:49,625 --> 00:05:51,500 Och återigen, vad jag gör här-- av way-- 126 00:05:51,500 --> 00:05:54,580 är ett allmänt fall för en nod som är i mitten. 127 00:05:54,580 --> 00:05:56,547 Det finns ett par extra varningar som du 128 00:05:56,547 --> 00:05:59,380 måste tänka på när du raderar början av listan 129 00:05:59,380 --> 00:06:01,040 eller slutet av listan. 130 00:06:01,040 --> 00:06:03,730 Det finns ett par special hörn fall att ta itu med det. 131 00:06:03,730 --> 00:06:07,960 >> Så detta fungerar för att ta bort någon nod i mitten av den list-- en som 132 00:06:07,960 --> 00:06:11,550 har ett legitimt pekare framåt och en legitim pekare bakåt, 133 00:06:11,550 --> 00:06:14,460 legitima Föregående och Nästa pekare. 134 00:06:14,460 --> 00:06:16,530 Återigen, om du arbetar med ändarna, du 135 00:06:16,530 --> 00:06:18,500 behöver för att hantera de något annorlunda, 136 00:06:18,500 --> 00:06:19,570 och vi kommer inte att prata om det nu. 137 00:06:19,570 --> 00:06:21,319 Men du kan förmodligen räkna ut vad som behöver 138 00:06:21,319 --> 00:06:24,610 göras bara genom att titta på den här videon. 139 00:06:24,610 --> 00:06:28,910 >> Så vi har isolerat X. X är noden Vi vill ta bort från listan. 140 00:06:28,910 --> 00:06:30,140 Vad gör vi? 141 00:06:30,140 --> 00:06:32,800 Först måste vi ordna utanför pekare. 142 00:06:32,800 --> 00:06:35,815 Vi måste ordna 9 nästa för att hoppa över 13 143 00:06:35,815 --> 00:06:38,030 och pekar på 10-- som är vad vi just har gjort. 144 00:06:38,030 --> 00:06:41,180 Och vi måste också ordna 10 s Föregående 145 00:06:41,180 --> 00:06:44,610 att peka på 9 stället för att peka till 13. 146 00:06:44,610 --> 00:06:46,490 >> Så återigen, var detta diagram för att börja med. 147 00:06:46,490 --> 00:06:47,730 Detta var vår kedja. 148 00:06:47,730 --> 00:06:51,027 Vi måste hoppa över 13, men vi måste också bevara 149 00:06:51,027 --> 00:06:52,110 integriteten av listan. 150 00:06:52,110 --> 00:06:54,680 Vi vill inte förlora någon informationen i endera riktningen. 151 00:06:54,680 --> 00:06:59,620 Så vi behöver för att ordna pekarna noggrant 152 00:06:59,620 --> 00:07:02,240 så att vi inte bryter kedjan alls. 153 00:07:02,240 --> 00:07:05,710 >> Så vi kan säga 9 Next pekare pekar på samma ställe 154 00:07:05,710 --> 00:07:08,040 att tretton Next pekaren pekar just nu. 155 00:07:08,040 --> 00:07:10,331 Eftersom vi är så småningom kommer att vilja hoppa över 13. 156 00:07:10,331 --> 00:07:13,750 Så var 13 poäng nästa, du vill nio peka dit istället. 157 00:07:13,750 --> 00:07:15,200 Så det är det. 158 00:07:15,200 --> 00:07:20,370 Och sedan överallt där 13 poäng tillbaka till allt som kommer före den 13, 159 00:07:20,370 --> 00:07:24,800 vi vill 10 till punkt till att i stället för 13. 160 00:07:24,800 --> 00:07:29,290 Nu märker, om du följer pilarna, kan vi släppa 13 161 00:07:29,290 --> 00:07:32,380 utan att förlora någon information. 162 00:07:32,380 --> 00:07:36,002 Vi har hållit integritet listan, flytta både framåt och bakåt. 163 00:07:36,002 --> 00:07:38,210 Och då kan vi bara sorts av städa upp lite 164 00:07:38,210 --> 00:07:40,930 genom att dra i listan tillsammans. 165 00:07:40,930 --> 00:07:43,270 Så vi ordnas om pekare på vardera sidan. 166 00:07:43,270 --> 00:07:46,231 Och sedan befriade vi X nod som innehöll 13, 167 00:07:46,231 --> 00:07:47,480 och vi inte bryta kedjan. 168 00:07:47,480 --> 00:07:50,980 Så vi gjorde bra. 169 00:07:50,980 --> 00:07:53,000 >> Sist här på länkade listor. 170 00:07:53,000 --> 00:07:55,990 Så både singly- och dubbelt bunden listor, som vi har sett, 171 00:07:55,990 --> 00:07:58,959 stöd verkligen effektiv införing och borttagning av element. 172 00:07:58,959 --> 00:08:00,750 Du kan ganska mycket göra den i konstant tid. 173 00:08:00,750 --> 00:08:03,333 Vad gjorde vi måste göra för att ta bort ett element bara en sekund sedan? 174 00:08:03,333 --> 00:08:04,440 Vi flyttade en pekare. 175 00:08:04,440 --> 00:08:05,920 Vi flyttade en annan pekare. 176 00:08:05,920 --> 00:08:07,915 Vi befriade X-- tog tre operationer. 177 00:08:07,915 --> 00:08:14,500 Det tar alltid tre verksamheten till ta bort den node-- att befria en nod. 178 00:08:14,500 --> 00:08:15,280 >> Hur ska vi sätta? 179 00:08:15,280 --> 00:08:17,280 Tja, vi är bara alltid tacking på början 180 00:08:17,280 --> 00:08:19,400 om vi sätter i ett effektivt sätt. 181 00:08:19,400 --> 00:08:21,964 Så vi behöver rearrange-- beroende på om det är 182 00:08:21,964 --> 00:08:24,380 en singly- eller dubbelbundna listan kan vi behöva göra tre 183 00:08:24,380 --> 00:08:26,824 eller fyra operationer max. 184 00:08:26,824 --> 00:08:28,365 Men återigen, det är alltid tre eller fyra. 185 00:08:28,365 --> 00:08:30,531 Det spelar ingen roll hur många elementen är i vår lista, 186 00:08:30,531 --> 00:08:33,549 det är alltid tre eller fyra operations-- precis som raderingen är alltid 187 00:08:33,549 --> 00:08:35,320 tre eller fyra operationer. 188 00:08:35,320 --> 00:08:36,919 Det är konstant tid. 189 00:08:36,919 --> 00:08:38,169 Så det är riktigt bra. 190 00:08:38,169 --> 00:08:40,620 >> Med arrayer, gjorde vi något liknande insättningssortering. 191 00:08:40,620 --> 00:08:44,739 Ni minns säkert att inför sortera är inte en konstant tidsalgoritm. 192 00:08:44,739 --> 00:08:46,030 Det är faktiskt ganska dyrt. 193 00:08:46,030 --> 00:08:48,840 Så det här är en mycket bättre för införande. 194 00:08:48,840 --> 00:08:51,840 Men som jag nämnde i enskilt-länkad lista video, 195 00:08:51,840 --> 00:08:54,030 vi har en avigsida här också, eller hur? 196 00:08:54,030 --> 00:08:57,580 Vi har förlorat förmågan att slumpmässigt tillgång element. 197 00:08:57,580 --> 00:09:02,310 Vi kan inte säga, jag vill elementnummer fyra eller elementnummer 10 av en länkad lista 198 00:09:02,310 --> 00:09:04,990 på samma sätt som vi kan göra det med en array 199 00:09:04,990 --> 00:09:08,630 eller vi kan bara direkt index i vår samling är element. 200 00:09:08,630 --> 00:09:10,930 >> Och så försöker hitta en elementet i en länkad list-- 201 00:09:10,930 --> 00:09:15,880 Om du söker är important-- Nu kan ta linjär tid. 202 00:09:15,880 --> 00:09:18,330 Eftersom listan blir längre, det kan ta ett ytterligare steg 203 00:09:18,330 --> 00:09:22,644 för varje enskilt element i listan i För att hitta det vi letar efter. 204 00:09:22,644 --> 00:09:23,560 Så det finns kompromisser. 205 00:09:23,560 --> 00:09:25,780 Det är lite av ett proffs och con inslag här. 206 00:09:25,780 --> 00:09:29,110 >> Och dubbelt-länkade listor är inte sista typ av datastruktur kombination 207 00:09:29,110 --> 00:09:32,840 att vi ska tala om, med all den grundläggande bygg 208 00:09:32,840 --> 00:09:34,865 block av C en sätta ihop. 209 00:09:34,865 --> 00:09:37,900 Eftersom i själva verket kan vi ens göra bättre än så här 210 00:09:37,900 --> 00:09:41,970 att skapa en datastruktur som du skulle kunna söka igenom 211 00:09:41,970 --> 00:09:43,360 i konstant tid också. 212 00:09:43,360 --> 00:09:46,080 Men mer om det i en annan video. 213 00:09:46,080 --> 00:09:47,150 >> Jag är Doug Lloyd. 214 00:09:47,150 --> 00:09:49,050 Detta är CS50. 215 00:09:49,050 --> 00:09:50,877