1 00:00:00,000 --> 00:00:03,381 >> [Zenelejátszási] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD: Rendben. 4 00:00:05,520 --> 00:00:07,860 Tehát, ha éppen befejezte, hogy video egyszeres kapcsolt listák sajnálom 5 00:00:07,860 --> 00:00:09,568 Hagytam ki egy Kicsit filmsorozat. 6 00:00:09,568 --> 00:00:12,790 De örülök, hogy itt vagy, hogy befejezze A történet a kétszeresen láncolt listák. 7 00:00:12,790 --> 00:00:15,250 >> Tehát, ha visszahívja hogy a videó, beszélgettünk 8 00:00:15,250 --> 00:00:18,500 hogyan egyszeres kapcsolt listák nem vesz részt a képességünket, 9 00:00:18,500 --> 00:00:22,090 foglalkozni információk ahol az elemek száma 10 00:00:22,090 --> 00:00:24,442 vagy az elemek számát listáját nőhet, vagy zsugorodik. 11 00:00:24,442 --> 00:00:26,400 Most már foglalkozni valami ilyesmi, ahol 12 00:00:26,400 --> 00:00:28,310 nem tudtunk foglalkozni vele tömbök. 13 00:00:28,310 --> 00:00:30,560 >> De ők szenvednek az egyik kritikus határértéket, amelyet 14 00:00:30,560 --> 00:00:33,790 az, hogy egy egyszeresen-kapcsolt lista, csak akkor tudjuk mozgatni valaha 15 00:00:33,790 --> 00:00:36,200 egy irányban végig a listát. 16 00:00:36,200 --> 00:00:39,010 És az egyetlen valós helyzetet ha ez a probléma lehet 17 00:00:39,010 --> 00:00:41,250 volt, amikor megpróbáltunk törölni egy elemet. 18 00:00:41,250 --> 00:00:46,000 És akkor még nem is megvitassák, hogyan kell csinálni egy egyszeres láncolt lista pszeudokód. 19 00:00:46,000 --> 00:00:48,797 Ez minden bizonnyal megvalósítható, de ez lehet egy kis szóváltás. 20 00:00:48,797 --> 00:00:50,630 Tehát, ha találsz magadnak egy olyan helyzetben, ahol a 21 00:00:50,630 --> 00:00:53,175 akarsz törölni Egyetlen elemet a listából 22 00:00:53,175 --> 00:00:55,430 vagy ez lesz szükség hogy akkor kell törölni 23 00:00:55,430 --> 00:00:57,970 Egyetlen elemek A lista, érdemes 24 00:00:57,970 --> 00:01:02,090 hogy fontolják meg egy kétszeresen kötött lista helyett egy egyszeresen láncolt listával. 25 00:01:02,090 --> 00:01:06,320 Mivel kétszeresen láncolt listák segítségével mozogni előre és hátra 26 00:01:06,320 --> 00:01:09,340 Ha a listában helyett Csak előre a list-- 27 00:01:09,340 --> 00:01:13,950 Csak úgy, hogy egy kiegészítő elemet hogy mi szerkezete meghatározása 28 00:01:13,950 --> 00:01:16,690 a kétszeresen láncolt lista csomópontot. 29 00:01:16,690 --> 00:01:19,770 >> Ismét, ha nem fogod törlésével egyes elemeinek 30 00:01:19,770 --> 00:01:24,810 A list-- mert mi hozzátéve extra mezőt szerkezetünk 31 00:01:24,810 --> 00:01:28,340 meghatározás, a csomópontok maguk A kétszeresen láncolt listák 32 00:01:28,340 --> 00:01:29,550 lesznek nagyobbak. 33 00:01:29,550 --> 00:01:31,600 Ők fognak venni több bájt memóriát. 34 00:01:31,600 --> 00:01:34,160 És így, ha ez nem olyasmi fogsz kell tennie, 35 00:01:34,160 --> 00:01:36,300 úgy is dönthet, hogy Nem éri meg a kompromisszum 36 00:01:36,300 --> 00:01:39,360 hogy kell költeni az extra bájt memória szükséges 37 00:01:39,360 --> 00:01:43,940 Egy kétszeresen láncolt lista, ha nem lesz törlésével egyes elemek. 38 00:01:43,940 --> 00:01:46,760 De ők is hűvös más dolgokat is. 39 00:01:46,760 --> 00:01:51,260 >> Tehát mint mondtam, csak kell hozzá egyetlen mezőt szerkezetünk 40 00:01:51,260 --> 00:01:55,360 definition-- ezt a fogalmat Egy Előző mutató. 41 00:01:55,360 --> 00:01:58,620 Tehát egy egyszeres láncolt lista, mi az értéke, és a hátralévő mutatót, 42 00:01:58,620 --> 00:02:02,850 így a kétszeresen láncolt lista csak meg olyan módon, hogy a hátra is. 43 00:02:02,850 --> 00:02:04,960 >> Most az egyszeresen kötött lista video, beszélgettünk 44 00:02:04,960 --> 00:02:07,210 körülbelül ezek az öt legfontosabb dolog, meg kell, hogy 45 00:02:07,210 --> 00:02:09,449 képes megtenni dolgozni láncolt listák. 46 00:02:09,449 --> 00:02:12,880 És a legtöbb ilyen, az a tény, hogy ez egy kétszeresen láncolt lista 47 00:02:12,880 --> 00:02:14,130 nem igazán nagy ugrás. 48 00:02:14,130 --> 00:02:17,936 Még mindig keresgélni, egyszerűen halad előre az elejétől a végéig. 49 00:02:17,936 --> 00:02:20,810 Még mindig hozzon létre egy csomópont ki semmiből, nagyjából ugyanúgy. 50 00:02:20,810 --> 00:02:23,591 Mi lehet törölni listákat, elég ugyanúgy túl. 51 00:02:23,591 --> 00:02:25,340 Az egyetlen dolog, ami a finoman más, 52 00:02:25,340 --> 00:02:28,970 Tényleg, illeszt új csomópontokat a listából, 53 00:02:28,970 --> 00:02:33,722 és mi végre beszélni törlése egyetlen elem a listából is. 54 00:02:33,722 --> 00:02:35,430 Ismét nagyon sok A másik három vagyunk 55 00:02:35,430 --> 00:02:37,888 Nem fog beszélni róluk most, mert ők csak 56 00:02:37,888 --> 00:02:43,920 Nagyon kisebb csíp a tárgyalt javaslatokra A külön-külön kötött lista videót. 57 00:02:43,920 --> 00:02:46,292 >> Úgyhogy be egy új csomópont egy kétszeresen láncolt listával. 58 00:02:46,292 --> 00:02:48,750 Beszéltünk csinálom ezt egyszeres kapcsolt listák is, 59 00:02:48,750 --> 00:02:52,020 de van egy-két extra elkapja a kétszeresen láncolt listák. 60 00:02:52,020 --> 00:02:55,280 Mi vagyunk [? halad?] a fejét a felsorolni és néhány tetszőleges értéket, 61 00:02:55,280 --> 00:02:58,600 és azt akarjuk, hogy az új vezetője A lista ki ezt a funkciót. 62 00:02:58,600 --> 00:03:01,414 Ez miért ad vissza dllnode csillag. 63 00:03:01,414 --> 00:03:02,330 Tehát mi a lépések? 64 00:03:02,330 --> 00:03:04,496 Ezek, ismét nagyon hasonló hogy egyszeres láncolt listák 65 00:03:04,496 --> 00:03:05,670 egy extra felül. 66 00:03:05,670 --> 00:03:08,900 Azt akarjuk, hogy foglalja le a helyet az új csomópontot, és győződjön meg róla, hogy érvényes-e. 67 00:03:08,900 --> 00:03:11,510 Azt akarjuk, hogy töltse ki, hogy node-ig mindazt az információt, amit 68 00:03:11,510 --> 00:03:12,564 kívánja helyezni azt. 69 00:03:12,564 --> 00:03:15,480 Az utolsó dolog, amit meg kell do-- a extra dolog, amit tennie kell, rather-- 70 00:03:15,480 --> 00:03:19,435 meg kell határoznia Előző mutatót A régi lista élére. 71 00:03:19,435 --> 00:03:21,310 Ne feledje, hogy azért, mert A kétszeresen láncolt listák, 72 00:03:21,310 --> 00:03:23,110 tudunk előrelépni és backwards-- amely 73 00:03:23,110 --> 00:03:27,080 azt jelenti, hogy minden csomópont valóban emlékeztet a másik két csomópont helyett csak egy. 74 00:03:27,080 --> 00:03:29,110 És így kell rögzíteni A régi lista élére 75 00:03:29,110 --> 00:03:32,151 hogy pont hátra az új vezetője A listába, ami valami 76 00:03:32,151 --> 00:03:33,990 nem kellett tennie, mielőtt. 77 00:03:33,990 --> 00:03:37,420 És mint korábban, csak vissza mutatót a lista élére. 78 00:03:37,420 --> 00:03:38,220 >> Tehát itt egy lista. 79 00:03:38,220 --> 00:03:40,144 Azt akarjuk, hogy helyezze be a 12. a listán. 80 00:03:40,144 --> 00:03:42,060 Figyeljük meg, hogy a rajz kicsit más. 81 00:03:42,060 --> 00:03:47,710 Minden csomópont három fields-- adatokat, és egy Következő mutató piros, 82 00:03:47,710 --> 00:03:50,170 és az előző mutató kék. 83 00:03:50,170 --> 00:03:54,059 Semmi nem jön, mielőtt a 15 csomópont, így a korábbi mutató null. 84 00:03:54,059 --> 00:03:55,350 Ez a lista elején. 85 00:03:55,350 --> 00:03:56,560 Semmi sem előtte. 86 00:03:56,560 --> 00:04:03,350 És semmi nem jön, miután a 10 csomópontot, így Következő mutató null is. 87 00:04:03,350 --> 00:04:05,616 >> Tehát tegyük hozzá 12 ehhez a listához. 88 00:04:05,616 --> 00:04:08,070 Szükségünk [hallhatatlan] helyet a csomópontot. 89 00:04:08,070 --> 00:04:11,480 Azt hogy 12 belsejébe. 90 00:04:11,480 --> 00:04:14,840 És akkor megint, mi kell igazán Vigyázzon, hogy ne megtörni a láncot. 91 00:04:14,840 --> 00:04:17,144 Azt akarjuk, hogy átrendezéséhez mutatók a megfelelő sorrendben. 92 00:04:17,144 --> 00:04:19,519 És néha, hogy talán értem-- mint látni fogjuk, különösen 93 00:04:19,519 --> 00:04:24,120 A delete--, hogy mi van néhány redundáns mutatók, de ez rendben van. 94 00:04:24,120 --> 00:04:25,750 >> Szóval mit akarunk csinálni először? 95 00:04:25,750 --> 00:04:28,290 Azt ajánlom a dolgok akkor valószínűleg 96 00:04:28,290 --> 00:04:35,350 nem kell kitölteni a mutató a 12 node, mielőtt megérintené bárki más. 97 00:04:35,350 --> 00:04:38,640 Tehát mi 12 fog mutatni a következő lépés? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 Mi jön 12-e előtt? 100 00:04:42,430 --> 00:04:43,640 Semmi. 101 00:04:43,640 --> 00:04:46,280 Most már betöltötte a Extra információk 12 102 00:04:46,280 --> 00:04:49,320 ezért az előző, következő, és az érték. 103 00:04:49,320 --> 00:04:53,505 >> Most mi lehet 15-- ezt a plusz lépésben beszéltünk about-- vagyunk 104 00:04:53,505 --> 00:04:56,590 lehet 15 pontot vissza 12. 105 00:04:56,590 --> 00:04:59,634 És most már tudjuk mozgatni a fejét A listába, hogy szintén 12. 106 00:04:59,634 --> 00:05:02,550 Szóval ez elég hasonló ahhoz, amit csinált a egyszeres láncolt listák, 107 00:05:02,550 --> 00:05:06,940 kivéve a további lépést, a összekötő régi lista élére 108 00:05:06,940 --> 00:05:09,810 vissza az új lista élére. 109 00:05:09,810 --> 00:05:12,170 >> Most végre törölni Egy csomópont egy láncolt lista. 110 00:05:12,170 --> 00:05:14,350 Tehát mondjuk van Néhány más, 111 00:05:14,350 --> 00:05:18,080 megtalálni egy csomópont akarunk törölni és adott nekünk egy mutatót pontosan 112 00:05:18,080 --> 00:05:19,710 A csomópont, hogy szeretnénk törölni. 113 00:05:19,710 --> 00:05:22,360 Még csak nem is need-- mondani a feje még mindig globálisan deklarált. 114 00:05:22,360 --> 00:05:23,590 Nem kell a fejét itt. 115 00:05:23,590 --> 00:05:26,830 Minden ezt a funkciót tesz, mi már Találtam egy mutatót pontosan csúcsba 116 00:05:26,830 --> 00:05:28,090 akar megszabadulni. 117 00:05:28,090 --> 00:05:28,940 Nézzük megszabadulni tőle. 118 00:05:28,940 --> 00:05:31,859 Ez egy sokkal könnyebb kétszeresen láncolt listák. 119 00:05:31,859 --> 00:05:33,650 First-- ez valójában csak egy pár dolgot. 120 00:05:33,650 --> 00:05:38,760 Csak meg kell kijavítani a környező csomópontok "mutatókat úgy, hogy átugorják 121 00:05:38,760 --> 00:05:40,240 A csomópont akarunk törölni. 122 00:05:40,240 --> 00:05:43,484 És akkor törölheti a csomóponton. 123 00:05:43,484 --> 00:05:45,150 Tehát újra, csak most megy keresztül itt. 124 00:05:45,150 --> 00:05:49,625 Mi már nyilvánvalóan úgy döntött, hogy akarjuk törölni a csomópont X. 125 00:05:49,625 --> 00:05:51,500 És ismét, milyen vagyok Ennek here-- a way-- 126 00:05:51,500 --> 00:05:54,580 Általános esetben egy csomóponton, amely a közepén. 127 00:05:54,580 --> 00:05:56,547 Van egy pár extra kikötéssel, hogy 128 00:05:56,547 --> 00:05:59,380 kell szem előtt tartania törlése A legelején a listát 129 00:05:59,380 --> 00:06:01,040 vagy a legvégén a lista. 130 00:06:01,040 --> 00:06:03,730 Van egy pár speciális sarok megoldandó eset van. 131 00:06:03,730 --> 00:06:07,960 >> Így működik ez a megsemmisítését csomópont a közepén a list-- egyik, hogy 132 00:06:07,960 --> 00:06:11,550 jogos mutatót előre és jogos mutató hátra, 133 00:06:11,550 --> 00:06:14,460 jogos Előző és Következő mutatót. 134 00:06:14,460 --> 00:06:16,530 Ismét ha dolgozik A végén, akkor 135 00:06:16,530 --> 00:06:18,500 kell kezelni azokat kicsit másképp, 136 00:06:18,500 --> 00:06:19,570 és mi nem fogunk beszélni, hogy most. 137 00:06:19,570 --> 00:06:21,319 De akkor talán kitalálni, mit kell 138 00:06:21,319 --> 00:06:24,610 meg kell tenni csak nézi ezt a videót. 139 00:06:24,610 --> 00:06:28,910 >> Így már elszigetelt X. X a csomópont szeretnénk törölni a listáról. 140 00:06:28,910 --> 00:06:30,140 Mit csináljunk? 141 00:06:30,140 --> 00:06:32,800 Először is meg kell átrendezni a külső mutatók. 142 00:06:32,800 --> 00:06:35,815 Meg kell átrendezni 9-es melletti átugorják 13 143 00:06:35,815 --> 00:06:38,030 és pont 10-- amely az, amit éppen most történik. 144 00:06:38,030 --> 00:06:41,180 És azt is meg kell átrendezheti 10 korábbi 145 00:06:41,180 --> 00:06:44,610 hogy pont 9 helyett mutató 13. 146 00:06:44,610 --> 00:06:46,490 >> Tehát újra, ez volt az rajz kezdeni. 147 00:06:46,490 --> 00:06:47,730 Ez volt a lánc. 148 00:06:47,730 --> 00:06:51,027 Meg kell, hogy átugorja a 13, de meg kell is megőrizheti 149 00:06:51,027 --> 00:06:52,110 a integritását a listán. 150 00:06:52,110 --> 00:06:54,680 Nem akarjuk elveszíteni bármilyen információ mindkét irányban. 151 00:06:54,680 --> 00:06:59,620 Tehát meg kell átrendezni A mutatók gondosan 152 00:06:59,620 --> 00:07:02,240 így nem megtörni a láncot egyáltalán. 153 00:07:02,240 --> 00:07:05,710 >> Így elmondhatjuk, 9 Next mutató rámutat, hogy ugyanazon a helyen 154 00:07:05,710 --> 00:07:08,040 A tizenhárom Next mutató most. 155 00:07:08,040 --> 00:07:10,331 Mert mi vagyunk végül szeretne majd átugorják 13. 156 00:07:10,331 --> 00:07:13,750 Így bárhol 13 pont következő, akkor szeretnénk kilenc pontra van helyette. 157 00:07:13,750 --> 00:07:15,200 Szóval ennyi. 158 00:07:15,200 --> 00:07:20,370 És akkor bárhol 13 pont vissza az, bármi is jön, mielőtt 13, 159 00:07:20,370 --> 00:07:24,800 akarunk 10 pontra hogy hogy ahelyett, hogy 13. 160 00:07:24,800 --> 00:07:29,290 Most észre, ha követi A nyilak, levehetjük 13 161 00:07:29,290 --> 00:07:32,380 anélkül, hogy elveszítené minden információt. 162 00:07:32,380 --> 00:07:36,002 Úgy írtuk meg a integritását a listán, mozgó előre és hátra. 163 00:07:36,002 --> 00:07:38,210 És akkor mi is csak amolyan A tiszta fel egy kicsit 164 00:07:38,210 --> 00:07:40,930 húzva a listáról össze. 165 00:07:40,930 --> 00:07:43,270 Tehát átrendezték a pointerek mindkét oldalán. 166 00:07:43,270 --> 00:07:46,231 És akkor felszabadul X a csomópont, amely tartalmazott 13, 167 00:07:46,231 --> 00:07:47,480 és mi nem megtörni a láncot. 168 00:07:47,480 --> 00:07:50,980 Szóval mi a jó. 169 00:07:50,980 --> 00:07:53,000 >> Utolsó megjegyzés itt láncolt listák. 170 00:07:53,000 --> 00:07:55,990 Így mindkét singly- és kétszeresen kötött listákat, mint láttuk, 171 00:07:55,990 --> 00:07:58,959 támogatást valóban hatékony beillesztés és törlésére vonatkozó elemeket. 172 00:07:58,959 --> 00:08:00,750 Akkor elég sok ez állandó időt. 173 00:08:00,750 --> 00:08:03,333 Mit kell tennünk, hogy törölje egy elem csak egy perce? 174 00:08:03,333 --> 00:08:04,440 Azért költöztünk egy mutatóval. 175 00:08:04,440 --> 00:08:05,920 Elköltöztünk egy másik mutatót. 176 00:08:05,920 --> 00:08:07,915 Mi szabadult X- vett három művelet. 177 00:08:07,915 --> 00:08:14,500 Mindig úgy három műveletek törölni, hogy node-- kiszabadítani egy csomópont. 178 00:08:14,500 --> 00:08:15,280 >> Hogyan írjunk? 179 00:08:15,280 --> 00:08:17,280 Nos, mi csak mindig tacking a kezdet 180 00:08:17,280 --> 00:08:19,400 ha már behelyezése hatékonyan. 181 00:08:19,400 --> 00:08:21,964 Tehát meg kell rearrange-- attól függően, hogy ha ez 182 00:08:21,964 --> 00:08:24,380 Egy singly- vagy kétszeresen kötött listáját, szükségünk lehet, hogy nem három 183 00:08:24,380 --> 00:08:26,824 vagy négy műveletek max. 184 00:08:26,824 --> 00:08:28,365 De ismétlem, ez mindig három vagy négy. 185 00:08:28,365 --> 00:08:30,531 Nem számít, hogy hány elemek vannak a listán, 186 00:08:30,531 --> 00:08:33,549 ez mindig három-négy operations-- mint törlés mindig 187 00:08:33,549 --> 00:08:35,320 három vagy négy műveletet. 188 00:08:35,320 --> 00:08:36,919 Ez folyamatos időben. 189 00:08:36,919 --> 00:08:38,169 Szóval ez tényleg jó. 190 00:08:38,169 --> 00:08:40,620 >> A tömbök, csinálunk valami, mint az elhelyezési sorrend. 191 00:08:40,620 --> 00:08:44,739 Valószínűleg emlékeztetni arra, hogy behelyezés A rendezés nem állandó algoritmust. 192 00:08:44,739 --> 00:08:46,030 Valójában nagyon drága. 193 00:08:46,030 --> 00:08:48,840 Tehát ez egy sokkal jobb behelyezésére. 194 00:08:48,840 --> 00:08:51,840 De ahogy már említettem az egyszeres láncolt lista video, 195 00:08:51,840 --> 00:08:54,030 megvan a hátránya is itt, igaz? 196 00:08:54,030 --> 00:08:57,580 Elvesztettük a képességét, hogy véletlenszerűen elemeinek elérésére. 197 00:08:57,580 --> 00:09:02,310 Nem mondhatjuk, szeretnék eleme a négyes vagy elem száma 10 egy láncolt lista 198 00:09:02,310 --> 00:09:04,990 Ugyanúgy, ahogy csak tudunk Ehhez egy sor 199 00:09:04,990 --> 00:09:08,630 vagy mi csak közvetlenül index a mi tömb eleme. 200 00:09:08,630 --> 00:09:10,930 >> És így próbál találni eleme a kapcsolódó list-- 201 00:09:10,930 --> 00:09:15,880 Ha keresés important-- Most már a lineáris idő. 202 00:09:15,880 --> 00:09:18,330 Mivel a lista egyre hosszabb, akkor Lehet, hogy egy további lépés 203 00:09:18,330 --> 00:09:22,644 minden egyes eleme a lista annak érdekében, hogy megtalálja, amit keres. 204 00:09:22,644 --> 00:09:23,560 Szóval van kompromisszumokra. 205 00:09:23,560 --> 00:09:25,780 Van egy kis pro és con eleme van. 206 00:09:25,780 --> 00:09:29,110 >> És kétszeresen kapcsolt listák nem az Utolsó féle adat struktúra kombinációja 207 00:09:29,110 --> 00:09:32,840 hogy fogunk beszélni, figyelembe az összes alapvető építési 208 00:09:32,840 --> 00:09:34,865 blokkok C egy összerakva. 209 00:09:34,865 --> 00:09:37,900 Mert valójában tudjuk még jobban, mint ez a 210 00:09:37,900 --> 00:09:41,970 hogy hozzon létre egy adatstruktúrát, amely akkor lehet, hogy keresni 211 00:09:41,970 --> 00:09:43,360 állandó időt is. 212 00:09:43,360 --> 00:09:46,080 De még az, hogy egy másik videó. 213 00:09:46,080 --> 00:09:47,150 >> Én Doug Lloyd. 214 00:09:47,150 --> 00:09:49,050 Ez CS50. 215 00:09:49,050 --> 00:09:50,877