1 00:00:00,000 --> 00:00:03,381 >> [REPRODUCCIÓ DE MÚSICA] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD: D'acord. 4 00:00:05,520 --> 00:00:07,860 Així que si vostè acaba d'acabar que de vídeo a les llistes per separat vinculats sorry 5 00:00:07,860 --> 00:00:09,568 Et vaig deixar en un mica d'un cliffhanger. 6 00:00:09,568 --> 00:00:12,790 Però m'alegro que estiguis aquí per acabar la història de les llistes doblement enllaçades. 7 00:00:12,790 --> 00:00:15,250 >> Així que si vostè recorda de aquest vídeo, parlem 8 00:00:15,250 --> 00:00:18,500 sobre com lligat individualment- llistes fan assistir a la nostra capacitat 9 00:00:18,500 --> 00:00:22,090 per fer front a la informació on el nombre d'elements 10 00:00:22,090 --> 00:00:24,442 o el nombre d'articles en una llista pot créixer o encongir-se. 11 00:00:24,442 --> 00:00:26,400 Ara podem fer front a alguna cosa així com que, quan 12 00:00:26,400 --> 00:00:28,310 no podíem tractar amb ell amb matrius. 13 00:00:28,310 --> 00:00:30,560 >> Però ells pateixen d'un limitació crítica que 14 00:00:30,560 --> 00:00:33,790 és que amb vinculats per separat, un llista, podem només sempre moure 15 00:00:33,790 --> 00:00:36,200 en una sola direcció a través de la llista. 16 00:00:36,200 --> 00:00:39,010 I l'única situació real on això pot esdevenir un problema 17 00:00:39,010 --> 00:00:41,250 va ser quan estàvem tractant de suprimir un sol element. 18 00:00:41,250 --> 00:00:46,000 I ni tan sols discutim com fer-ho en una llista simplement enllaçada en pseudocodi. 19 00:00:46,000 --> 00:00:48,797 Sens dubte, és factible, però que pot ser una mica complicat. 20 00:00:48,797 --> 00:00:50,630 Així que si vostè es troba en una situació on 21 00:00:50,630 --> 00:00:53,175 vostè està tractant d'eliminar elements individuals de la llista 22 00:00:53,175 --> 00:00:55,430 o que serà necessari que se li esborrant 23 00:00:55,430 --> 00:00:57,970 elements individuals de la llista, és possible que vulgueu 24 00:00:57,970 --> 00:01:02,090 considerar l'ús lligada doblement 01:00 llista en lloc d'una llista simplement enllaçada. 25 00:01:02,090 --> 00:01:06,320 Perquè les llistes doblement enllaçades, que permeten per moure cap endavant i cap enrere 26 00:01:06,320 --> 00:01:09,340 a través de la llista en lloc de just davant a través de la pel·lícules-- 27 00:01:09,340 --> 00:01:13,950 només mitjançant l'addició d'un element extra a la nostra definició de l'estructura 28 00:01:13,950 --> 00:01:16,690 per al node de la llista doblement enllaçada. 29 00:01:16,690 --> 00:01:19,770 >> Un cop més, si no vas a ser esborrat d'elements individuals 30 00:01:19,770 --> 00:01:24,810 Del pel·lícules-- perquè estem afegint un camp addicional a la nostra estructura 31 00:01:24,810 --> 00:01:28,340 definició, els propis nodes per a les llistes doblement enlazadas- 32 00:01:28,340 --> 00:01:29,550 van a ser més gran. 33 00:01:29,550 --> 00:01:31,600 Ells van a tenir fins a més bytes de memòria. 34 00:01:31,600 --> 00:01:34,160 I pel que si això no és una cosa vostè va a haver de fer, 35 00:01:34,160 --> 00:01:36,300 vostè pot decidir que és No val la pena el trade off 36 00:01:36,300 --> 00:01:39,360 a haver de passar l'extra bytes de memòria necessaris 37 00:01:39,360 --> 00:01:43,940 per obtenir una llista doblement enllaçada si no estàs va a ser esborrat d'elements individuals. 38 00:01:43,940 --> 00:01:46,760 Però també són fresc per a altres coses també. 39 00:01:46,760 --> 00:01:51,260 >> Així com he dit, només hem d'afegir un sol camp per a la nostra estructura 40 00:01:51,260 --> 00:01:55,360 definition-- aquesta noció d'un punter anterior. 41 00:01:55,360 --> 00:01:58,620 Així que amb una llista simplement enllaçada, ens tenir el valor i el punter següent, 42 00:01:58,620 --> 00:02:02,850 de manera que la llista doblement enllaçada només té una manera de moure cap enrere també. 43 00:02:02,850 --> 00:02:04,960 >> Ara a lligades individualment-la llista de vídeos, parlem 44 00:02:04,960 --> 00:02:07,210 sobre aquests estan cinc de la coses principals que necessita per ser 45 00:02:07,210 --> 00:02:09,449 capaç de fer per treballar amb llistes enllaçades. 46 00:02:09,449 --> 00:02:12,880 I per a la majoria d'ells, el fet de que es tracta d'una llista doblement enllaçada 47 00:02:12,880 --> 00:02:14,130 no és realment un gran salt. 48 00:02:14,130 --> 00:02:17,936 Podem encara buscar a través de tot just avançant des del principi fins al final. 49 00:02:17,936 --> 00:02:20,810 Encara podem crear un node de res, més o menys la mateixa manera. 50 00:02:20,810 --> 00:02:23,591 Podem eliminar llistes bastant de la mateixa manera també. 51 00:02:23,591 --> 00:02:25,340 Les úniques coses que són subtilment diferents, 52 00:02:25,340 --> 00:02:28,970 Realment, s'insereix nous nodes a la llista, 53 00:02:28,970 --> 00:02:33,722 i finalment parlarem sobre l'eliminació un sol element de la llista també. 54 00:02:33,722 --> 00:02:35,430 Un cop més, més o menys els altres tres, que estem 55 00:02:35,430 --> 00:02:37,888 no vaig a parlar d'ells en aquest moment perquè són just 56 00:02:37,888 --> 00:02:43,920 ajustos molt de menor importància en les idees discutides en la llista de vídeo simplement enllaçada. 57 00:02:43,920 --> 00:02:46,292 >> Així que anem a inserir un nou node en una llista doblement enllaçada. 58 00:02:46,292 --> 00:02:48,750 Parlem sobre fer això per llistes simplement enllaçada, així, 59 00:02:48,750 --> 00:02:52,020 però hi ha un parell de addicional les captures amb les llistes doblement enllaçades. 60 00:02:52,020 --> 00:02:55,280 Estem [? passant?] al cap de la enumerar aquí i una mica de valor arbitrari, 61 00:02:55,280 --> 00:02:58,600 i volem que el nou cap de la llista d'aquesta funció. 62 00:02:58,600 --> 00:03:01,414 És per això que torna un estel dllnode. 63 00:03:01,414 --> 00:03:02,330 Quins són els passos? 64 00:03:02,330 --> 00:03:04,496 Ells són, de nou, molt similar a les llistes lligades individualment- 65 00:03:04,496 --> 00:03:05,670 amb una addició extra. 66 00:03:05,670 --> 00:03:08,900 Volem assigna espai per a un nou node i de verificació per assegurar-se que és vàlid. 67 00:03:08,900 --> 00:03:11,510 Volem omplir aquest node fins amb qualsevol informació que 68 00:03:11,510 --> 00:03:12,564 vol posar en ell. 69 00:03:12,564 --> 00:03:15,480 L'última cosa que necessitem fer-- el cosa extra que hem de fer, rather-- 70 00:03:15,480 --> 00:03:19,435 és fixar el punter Anterior de l'antic cap de la llista. 71 00:03:19,435 --> 00:03:21,310 Recordeu que a causa llistes d'enllaços doblement, 72 00:03:21,310 --> 00:03:23,110 podem avançar i backwards-- que 73 00:03:23,110 --> 00:03:27,080 vol dir que cada node assenyala en realitat a altres dos nodes en lloc d'un de sol. 74 00:03:27,080 --> 00:03:29,110 I així hem d'arreglar l'antic cap de la llista 75 00:03:29,110 --> 00:03:32,151 apuntar cap enrere per al nou cap de la llista enllaçada, que era una cosa 76 00:03:32,151 --> 00:03:33,990 que no havíem de fer abans. 77 00:03:33,990 --> 00:03:37,420 I com abans, només tornem una punter a la nova cap de la llista. 78 00:03:37,420 --> 00:03:38,220 >> Així que aquí està una llista. 79 00:03:38,220 --> 00:03:40,144 Volem inserir 12 en aquesta llista. 80 00:03:40,144 --> 00:03:42,060 Tingueu present que el diagrama és lleugerament diferent. 81 00:03:42,060 --> 00:03:47,710 Cada node conté tres fields-- dades i un punter Següent a vermell, 82 00:03:47,710 --> 00:03:50,170 i un punter anterior en blau. 83 00:03:50,170 --> 00:03:54,059 Res ve abans que el node 15, pel que la seva punter anterior és nul. 84 00:03:54,059 --> 00:03:55,350 És el principi de la llista. 85 00:03:55,350 --> 00:03:56,560 No hi ha res abans. 86 00:03:56,560 --> 00:04:03,350 I res ve després que el node 10 i per la qual cosa és Següent punter és nul també. 87 00:04:03,350 --> 00:04:05,616 >> Així que anem a afegir 12 a aquesta llista. 88 00:04:05,616 --> 00:04:08,070 Necessitem [inaudible] espai per al node. 89 00:04:08,070 --> 00:04:11,480 Posem 12 a l'interior de la mateixa. 90 00:04:11,480 --> 00:04:14,840 I, de nou, hem de ser molt compte de no trencar la cadena. 91 00:04:14,840 --> 00:04:17,144 Volem canviar el punters en l'ordre correcte. 92 00:04:17,144 --> 00:04:19,519 I a vegades això pot dir-- com veurem en particular 93 00:04:19,519 --> 00:04:24,120 amb delete-- que tenim alguns punters redundants, però això està bé. 94 00:04:24,120 --> 00:04:25,750 >> Llavors, què és el que volem fer primer? 95 00:04:25,750 --> 00:04:28,290 Jo recomanaria el Coses que vostè ha, probablement, 96 00:04:28,290 --> 00:04:35,350 fer són per omplir els punters del 12 node abans de tocar a ningú més. 97 00:04:35,350 --> 00:04:38,640 Llavors, què està passant 12 per assenyalar a continuació? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 Què ve abans dels 12? 100 00:04:42,430 --> 00:04:43,640 Res. 101 00:04:43,640 --> 00:04:46,280 Ara hem omplert el Informació addicional en 12 102 00:04:46,280 --> 00:04:49,320 pel que té Anterior, Següent, i valor. 103 00:04:49,320 --> 00:04:53,505 >> Ara podem tenir 15-- aquest accessori pas que estàvem parlant sobre-- ens 104 00:04:53,505 --> 00:04:56,590 pot tenir 15 punts de nou a 12. 105 00:04:56,590 --> 00:04:59,634 I ara podem moure el cap de la llista enllaçada a ser també 12. 106 00:04:59,634 --> 00:05:02,550 Així que és bastant similar al que estaven fent amb les llistes simplement enllaçada, 107 00:05:02,550 --> 00:05:06,940 excepte pel pas addicional de que connecta l'antic cap de la llista 108 00:05:06,940 --> 00:05:09,810 donar suport a la nova cap de la llista. 109 00:05:09,810 --> 00:05:12,170 >> Ara anem a per fi eliminar un node d'una llista enllaçada. 110 00:05:12,170 --> 00:05:14,350 Així que anem a dir que tenim alguna altra funció que 111 00:05:14,350 --> 00:05:18,080 és trobar un node que volem eliminar i ens ha donat un punter a exactament 112 00:05:18,080 --> 00:05:19,710 el node que volem eliminar. 113 00:05:19,710 --> 00:05:22,360 Ni tan sols need-- diem la cap està encara a nivell mundial ha declarat. 114 00:05:22,360 --> 00:05:23,590 No necessitem el cap aquí. 115 00:05:23,590 --> 00:05:26,830 Tota aquesta funció està fent és que hem trobat un punter a exactament el que el node 116 00:05:26,830 --> 00:05:28,090 vol desfer. 117 00:05:28,090 --> 00:05:28,940 Anem a desfer-se'n. 118 00:05:28,940 --> 00:05:31,859 És molt més fàcil amb llistes doblement enllaçada. 119 00:05:31,859 --> 00:05:33,650 Primer-- en realitat només un parell de coses. 120 00:05:33,650 --> 00:05:38,760 Només hem de fixar l'envolta punters nodes 'perquè se salten més 121 00:05:38,760 --> 00:05:40,240 el node que voleu eliminar. 122 00:05:40,240 --> 00:05:43,484 I llavors podem eliminar aquest node. 123 00:05:43,484 --> 00:05:45,150 Així que de nou, només anem per aquí. 124 00:05:45,150 --> 00:05:49,625 Aparentment Hem decidit que volem eliminar el node X. 125 00:05:49,625 --> 00:05:51,500 I de nou, el que estic fent aquí-- pel manera- 126 00:05:51,500 --> 00:05:54,580 és un cas general d'una node que es troba en el medi. 127 00:05:54,580 --> 00:05:56,547 Hi ha un parell de advertiments addicionals que vostè 128 00:05:56,547 --> 00:05:59,380 considerar quan s'està esborrant el principi de la llista 129 00:05:59,380 --> 00:06:01,040 o el final de la llista. 130 00:06:01,040 --> 00:06:03,730 Hi ha un parell d'especials casos de cantonada per fer front a allà. 131 00:06:03,730 --> 00:06:07,960 >> Així que això funciona per esborrar qualsevol node en el medi de la qual pel·lícules-- 132 00:06:07,960 --> 00:06:11,550 té un punter legítima cap endavant i un punter legítima cap enrere, 133 00:06:11,550 --> 00:06:14,460 legítim punter anterior i següent. 134 00:06:14,460 --> 00:06:16,530 Un cop més, si vostè està treballant amb els extrems, que 135 00:06:16,530 --> 00:06:18,500 necessari per manejar els lleugerament diferent, 136 00:06:18,500 --> 00:06:19,570 i nosaltres no anem a parlar d'això ara. 137 00:06:19,570 --> 00:06:21,319 Però vostè pot probablement esbrinar el que necessita 138 00:06:21,319 --> 00:06:24,610 de fer amb només mirar aquest vídeo. 139 00:06:24,610 --> 00:06:28,910 >> Així que ens hem aïllat X. X és el node volem eliminar de la llista. 140 00:06:28,910 --> 00:06:30,140 Què fem? 141 00:06:30,140 --> 00:06:32,800 En primer lloc, hem de reorganitzar els punters fora. 142 00:06:32,800 --> 00:06:35,815 Hem de reorganitzar 9 del proper per saltar més de 13 143 00:06:35,815 --> 00:06:38,030 i apunten a 10-- que és el que acabem de fer. 144 00:06:38,030 --> 00:06:41,180 I també hem de reorganitzar 10 Anterior 145 00:06:41,180 --> 00:06:44,610 per assenyalar a 9 en lloc d'apuntar a 13. 146 00:06:44,610 --> 00:06:46,490 >> Així que de nou, aquesta va ser la diagrama per començar. 147 00:06:46,490 --> 00:06:47,730 Aquesta va ser la nostra cadena. 148 00:06:47,730 --> 00:06:51,027 Hem de saltar sobre 13, però necessitem també preservar 149 00:06:51,027 --> 00:06:52,110 la integritat de la llista. 150 00:06:52,110 --> 00:06:54,680 No volem perdre cap informació en qualsevol direcció. 151 00:06:54,680 --> 00:06:59,620 Així que hem de reordenar els punters acuradament 152 00:06:59,620 --> 00:07:02,240 pel que no trenquem la cadena en absolut. 153 00:07:02,240 --> 00:07:05,710 >> Així que podem dir de 9 Següent punter apunta al mateix lloc 154 00:07:05,710 --> 00:07:08,040 que dels tretze Següent punter apunta ara. 155 00:07:08,040 --> 00:07:10,331 Perquè som el temps voldrà saltar sobre 13. 156 00:07:10,331 --> 00:07:13,750 Així que allà on 13 punts següent, volen nou a punt no lloc. 157 00:07:13,750 --> 00:07:15,200 Així que això és tot. 158 00:07:15,200 --> 00:07:20,370 I a continuació, sempre que sigui 13 punts enrere a, el que ve abans dels 13, 159 00:07:20,370 --> 00:07:24,800 volem assenyalar 10 perquè en lloc de 13. 160 00:07:24,800 --> 00:07:29,290 Ara noti, si vostè segueix les fletxes, que poden caure 13 161 00:07:29,290 --> 00:07:32,380 sense arribar a perdre la informació. 162 00:07:32,380 --> 00:07:36,002 Hem mantingut la integritat de la llista, movent-se cap endavant i cap enrere. 163 00:07:36,002 --> 00:07:38,210 I llavors podem només una espècie de netejar-una mica 164 00:07:38,210 --> 00:07:40,930 tirant de la llista junts. 165 00:07:40,930 --> 00:07:43,270 Així que va reorganitzar la punters a cada costat. 166 00:07:43,270 --> 00:07:46,231 I llavors ens alliberem X el node que contenia 13, 167 00:07:46,231 --> 00:07:47,480 i no ens trenquem la cadena. 168 00:07:47,480 --> 00:07:50,980 Així ho vam fer bé. 169 00:07:50,980 --> 00:07:53,000 >> Nota final aquí a llistes enllaçades. 170 00:07:53,000 --> 00:07:55,990 Així doncs, tant singly- i doblement enllaçada llistes, com hem vist, 171 00:07:55,990 --> 00:07:58,959 suport inserció realment eficient i cancel·lació de les seves elements. 172 00:07:58,959 --> 00:08:00,750 Vostè pot gairebé fer a temps constant. 173 00:08:00,750 --> 00:08:03,333 Què havíem de fer per eliminar un element només un segon enrere? 174 00:08:03,333 --> 00:08:04,440 Ens mudem d'un punter. 175 00:08:04,440 --> 00:08:05,920 Ens mudem altre punter. 176 00:08:05,920 --> 00:08:07,915 Ens alliberem X-- prendre tres operacions. 177 00:08:07,915 --> 00:08:14,500 Sempre porta tres operacions a eliminar aquesta node-- per alliberar un node. 178 00:08:14,500 --> 00:08:15,280 >> Com ens inserim? 179 00:08:15,280 --> 00:08:17,280 Bé, estem simplement sempre virades al començament 180 00:08:17,280 --> 00:08:19,400 si estem inserint de manera eficient. 181 00:08:19,400 --> 00:08:21,964 Així que hem de rearrange-- depenent de si es tracta de 182 00:08:21,964 --> 00:08:24,380 1 singly- o doblement enllaçada llista, pot ser que hagi de fer de tres 183 00:08:24,380 --> 00:08:26,824 o max quatre operacions. 184 00:08:26,824 --> 00:08:28,365 Però, de nou, sempre és tres o quatre. 185 00:08:28,365 --> 00:08:30,531 No importa quants elements estan en la nostra llista, 186 00:08:30,531 --> 00:08:33,549 sempre tres o quatre operations-- de la mateixa manera que l'eliminació és sempre 187 00:08:33,549 --> 00:08:35,320 tres o quatre operacions. 188 00:08:35,320 --> 00:08:36,919 És temps constant. 189 00:08:36,919 --> 00:08:38,169 Així que això és realment genial. 190 00:08:38,169 --> 00:08:40,620 >> Amb els arranjaments, que estàvem fent alguna cosa així com l'ordenació per inserció. 191 00:08:40,620 --> 00:08:44,739 Vostè probablement recordarà que la inserció espècie no és un algoritme de temps constant. 192 00:08:44,739 --> 00:08:46,030 En realitat és bastant car. 193 00:08:46,030 --> 00:08:48,840 Així que això és molt millor per a la inserció. 194 00:08:48,840 --> 00:08:51,840 Però com he esmentat en el individualment lligada llista de vídeos, 195 00:08:51,840 --> 00:08:54,030 tenim un desavantatge aquí també, oi? 196 00:08:54,030 --> 00:08:57,580 Hem perdut la capacitat de accedir aleatòriament elements. 197 00:08:57,580 --> 00:09:02,310 No podem dir, vull element número quatre o l'element número 10 d'una llista enllaçada 198 00:09:02,310 --> 00:09:04,990 de la mateixa manera que podem fer això amb una matriu 199 00:09:04,990 --> 00:09:08,630 o podem simplement directament índex en l'element de la nostra matriu. 200 00:09:08,630 --> 00:09:10,930 >> I així, tractant de trobar una element d'una pel·lícules-- vinculats 201 00:09:10,930 --> 00:09:15,880 si la recerca és important-- Ara pot prendre temps lineal. 202 00:09:15,880 --> 00:09:18,330 Com la llista s'allarga, es podria donar un pas addicional 203 00:09:18,330 --> 00:09:22,644 per a cada element en la llista de Per trobar el que estem buscant. 204 00:09:22,644 --> 00:09:23,560 Així que no hi ha compensacions. 205 00:09:23,560 --> 00:09:25,780 Hi ha una mica d'un professional i l'element aire aquí. 206 00:09:25,780 --> 00:09:29,110 >> I les llistes doblement enllaçades, no n'hi ha últim tipus d'estructura de dades de combinació 207 00:09:29,110 --> 00:09:32,840 que parlarem, tenint tot l'edifici bàsic 208 00:09:32,840 --> 00:09:34,865 blocs de C 1 armant. 209 00:09:34,865 --> 00:09:37,900 Perquè, de fet, podem fins i tot una mica millor que això 210 00:09:37,900 --> 00:09:41,970 per crear una estructura de dades que vostè podria ser capaç de buscar a través de 211 00:09:41,970 --> 00:09:43,360 en temps constant també. 212 00:09:43,360 --> 00:09:46,080 Però més sobre això en un altre vídeo. 213 00:09:46,080 --> 00:09:47,150 >> Sóc Doug Lloyd. 214 00:09:47,150 --> 00:09:49,050 Això és CS50. 215 00:09:49,050 --> 00:09:50,877