1 00:00:00,000 --> 00:00:03,381 >> [MUSIC nagpe-play] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD: Lahat ng karapatan. 4 00:00:05,520 --> 00:00:07,860 Kaya't kung ikaw lang tapos na video sa isa-isa-link listahan ng paumanhin 5 00:00:07,860 --> 00:00:09,568 Iniwan ko sa iyo off sa isang piraso ng isang cliffhanger. 6 00:00:09,568 --> 00:00:12,790 Ngunit Natutuwa akong nandito ka upang matapos ang kuwento ng doble-link list. 7 00:00:12,790 --> 00:00:15,250 >> Kaya kung ang pagpapabalik sa iyo mula sa video na, usapan natin 8 00:00:15,250 --> 00:00:18,500 tungkol sa kung paano isa-isa na naka-link mga listahan ng gagawin dumalo sa aming kakayahan 9 00:00:18,500 --> 00:00:22,090 sa pakikitungo sa mga impormasyon kung saan ang bilang ng mga elemento 10 00:00:22,090 --> 00:00:24,442 o ang bilang ng mga item sa isang listahan ay maaaring lumaki o pag-urong. 11 00:00:24,442 --> 00:00:26,400 Maaari naming ngayon makikitungo sa isang bagay tulad na, kung saan 12 00:00:26,400 --> 00:00:28,310 hindi namin ma haharapin ang mga ito sa array. 13 00:00:28,310 --> 00:00:30,560 >> Subalit sila magtiis sa isa kritikal na limitasyon na 14 00:00:30,560 --> 00:00:33,790 ay na may isang isa-isa na naka-link listahan, maaari naming lamang kailanman ilipat 15 00:00:33,790 --> 00:00:36,200 sa isang solong direksyon sa pamamagitan ng mga listahan. 16 00:00:36,200 --> 00:00:39,010 At ang tanging tunay na sitwasyon saan na maaaring maging isang problema 17 00:00:39,010 --> 00:00:41,250 ay kapag kami ay nagsisikap na tanggalin ang isang elemento. 18 00:00:41,250 --> 00:00:46,000 At hindi namin kahit na pag-usapan kung paano ito gawin sa isang isa-isa-link na listahan sa pseudocode. 19 00:00:46,000 --> 00:00:48,797 Ito ay tiyak na maaaring gawin, ngunit maaaring ito ay isang bit ng isang problema. 20 00:00:48,797 --> 00:00:50,630 Kaya kung nakita mo ang iyong sarili sa isang sitwasyon na kung saan ang 21 00:00:50,630 --> 00:00:53,175 sinusubukan mong tanggalin ang single elemento mula sa listahan 22 00:00:53,175 --> 00:00:55,430 o ito ay pagpunta sa kinakailangan na kayo ay pagbubura 23 00:00:55,430 --> 00:00:57,970 single elemento mula sa listahan, maaari mong isaalang 24 00:00:57,970 --> 00:01:02,090 isaalang-alang ang paggamit ng isang doble-link ilista sa halip ng isang isa-isa-link na listahan. 25 00:01:02,090 --> 00:01:06,320 Dahil magpapahintulot sa inyo doble-link na listahan upang ilipat ang parehong pasulong at pabalik 26 00:01:06,320 --> 00:01:09,340 sa pamamagitan ng mga listahan sa halip ng lamang pasulong sa pamamagitan ng list-- 27 00:01:09,340 --> 00:01:13,950 sa pamamagitan lamang ng pagdaragdag ng isa dagdag na elemento sa aming mga kahulugan ng istraktura 28 00:01:13,950 --> 00:01:16,690 para sa mga doble-link listahan node. 29 00:01:16,690 --> 00:01:19,770 >> Muli, kung hindi ka pagpunta sa ay pagtanggal single elemento 30 00:01:19,770 --> 00:01:24,810 mula sa list-- dahil kami ay nagdadagdag ng ng dagdag na field sa aming istraktura 31 00:01:24,810 --> 00:01:28,340 kahulugan, ang nodes sa kanilang sarili para sa doble-link na listahan 32 00:01:28,340 --> 00:01:29,550 ay magiging mas malaki. 33 00:01:29,550 --> 00:01:31,600 Sila ay pagpunta sa tumagal up pa bytes ng memorya. 34 00:01:31,600 --> 00:01:34,160 At kaya kung hindi ito ay isang bagay ikaw ay pagpunta sa kailangan upang gawin, 35 00:01:34,160 --> 00:01:36,300 maaari kang magpasya ito ay Hindi karapat-dapat ang off kalakalan 36 00:01:36,300 --> 00:01:39,360 na magkaroon ng gastusin sa dagdag na bytes ng memory kinakailangan 37 00:01:39,360 --> 00:01:43,940 para sa isang doble-link na listahan kung hindi ka pagpunta sa pagtanggal ng nag-iisang sangkap. 38 00:01:43,940 --> 00:01:46,760 Ngunit ang mga ito rin ay cool na para sa masyadong iba pang mga bagay. 39 00:01:46,760 --> 00:01:51,260 >> Kaya tulad ng sinabi ko, kami na lang si isang single field sa aming istraktura 40 00:01:51,260 --> 00:01:55,360 definition-- ito paniwala ng isang Previous pointer. 41 00:01:55,360 --> 00:01:58,620 Kaya sa isang isa-isa-link na listahan, kami may halaga at ang Next pointer, 42 00:01:58,620 --> 00:02:02,850 kaya ang doble-link na listahan lamang ay isang paraan upang ilipat paurong rin. 43 00:02:02,850 --> 00:02:04,960 >> Ngayon sa isa-isa na naka-link listahan ng video, usapan natin 44 00:02:04,960 --> 00:02:07,210 tungkol sa mga ito ay limang ng pangunahing bagay na kailangan mo upang maging 45 00:02:07,210 --> 00:02:09,449 magawa sa trabaho na may mga listahan ng link. 46 00:02:09,449 --> 00:02:12,880 At para sa karamihan sa mga ito, ang katunayan na ito ay isang doble-link na listahan 47 00:02:12,880 --> 00:02:14,130 ay hindi tunay na isang malaking jump. 48 00:02:14,130 --> 00:02:17,936 Maaari pa rin kami sa paghahanap sa pamamagitan lamang sa pamamagitan ng paglipat ng pasulong mula simula hanggang katapusan. 49 00:02:17,936 --> 00:02:20,810 Maaari pa rin naming lumikha ng isang node sa labas ng manipis na hangin, medyo marami sa parehong paraan. 50 00:02:20,810 --> 00:02:23,591 Maaari naming tanggalin ang mga listahan pretty marami sa parehong paraan masyadong. 51 00:02:23,591 --> 00:02:25,340 Ang tanging bagay na ay subtly naiiba, 52 00:02:25,340 --> 00:02:28,970 talaga, ay pagpasok bagong nodes sa listahan, 53 00:02:28,970 --> 00:02:33,722 at kami ay sa wakas makipag-usap tungkol sa pagtanggal isang solong elemento mula sa listahan pati na rin. 54 00:02:33,722 --> 00:02:35,430 Muli, medyo marami ang iba pang mga tatlong, hindi namin 55 00:02:35,430 --> 00:02:37,888 hindi pagpunta sa makipag-usap tungkol sa mga ito sa ngayon dahil hindi lang nila 56 00:02:37,888 --> 00:02:43,920 very minor tweak sa mga ideya na tinalakay sa isa-isa-link na listahan ng video. 57 00:02:43,920 --> 00:02:46,292 >> Kaya hayaan ipasok ang isang bagong node sa isang doble-link na listahan. 58 00:02:46,292 --> 00:02:48,750 Usapan natin ang tungkol sa paggawa nito para sa isa-isa-link listahan pati na rin, 59 00:02:48,750 --> 00:02:52,020 ngunit may isang pares ng mga dagdag nakakakuha sa doble-link list. 60 00:02:52,020 --> 00:02:55,280 Humihingi kami [? pagpasa?] sa ulo ng listahan dito at ilang di-makatwirang halaga, 61 00:02:55,280 --> 00:02:58,600 at gusto naming makuha ang bagong ulo ng listahan ng mga function na ito. 62 00:02:58,600 --> 00:03:01,414 Iyon ang dahilan kung bakit ito ay nagbabalik ng isang dllnode star. 63 00:03:01,414 --> 00:03:02,330 Kaya ano ang mga hakbang na ito? 64 00:03:02,330 --> 00:03:04,496 Ang mga ito ay, muli, halos katulad upang isa-isa-listahan ng link 65 00:03:04,496 --> 00:03:05,670 may isang extrang karagdagan. 66 00:03:05,670 --> 00:03:08,900 Gusto naming naglalaan space para sa isang bagong node at suriin upang tiyakin na ito ay may-bisa. 67 00:03:08,900 --> 00:03:11,510 Gusto naming punan na node up sa kahit anong impormasyon ang aming 68 00:03:11,510 --> 00:03:12,564 gusto mong ilagay sa mga ito. 69 00:03:12,564 --> 00:03:15,480 Ang huling bagay na kailangan namin upang do-- ang dagdag na bagay na kailangan naming gawin, rather-- 70 00:03:15,480 --> 00:03:19,435 ay upang ayusin ang Previous pointer ng lumang ulo ng listahan. 71 00:03:19,435 --> 00:03:21,310 Tandaan na dahil ng doble-link na listahan, 72 00:03:21,310 --> 00:03:23,110 maaari naming sumulong at backwards-- saan 73 00:03:23,110 --> 00:03:27,080 ay nangangahulugan na ang bawat node aktwal na tumuturo sa dalawang iba pang mga nodes sa halip na isa lamang. 74 00:03:27,080 --> 00:03:29,110 At kaya kailangan namin upang ayusin ang lumang ulo ng listahan 75 00:03:29,110 --> 00:03:32,151 upang ituro paatras na ang bagong pinuno ng ang listahan ng mga link, na kung saan ay isang bagay na 76 00:03:32,151 --> 00:03:33,990 hindi namin ay may sa gawin bago. 77 00:03:33,990 --> 00:03:37,420 At tulad ng dati, bumalik kami lamang ng isang pointer sa bagong ulo ng listahan. 78 00:03:37,420 --> 00:03:38,220 >> Kaya narito ang isang listahan. 79 00:03:38,220 --> 00:03:40,144 Gusto naming ipasok 12 sa listahan na ito. 80 00:03:40,144 --> 00:03:42,060 Abiso na ang mga diagram ay bahagyang naiiba. 81 00:03:42,060 --> 00:03:47,710 Ang bawat node ay naglalaman ng tatlong fields-- data, at isang Next pointer sa pula, 82 00:03:47,710 --> 00:03:50,170 at isang Previous pointer sa asul. 83 00:03:50,170 --> 00:03:54,059 Walang dumating bago ang 15 node, kaya nito Nakaraan pointer ay null. 84 00:03:54,059 --> 00:03:55,350 Ito ang simula ng listahan. 85 00:03:55,350 --> 00:03:56,560 May walang bago ito. 86 00:03:56,560 --> 00:04:03,350 At walang dumating pagkatapos ng 10 node, at kaya Susunod pointer ay null rin. 87 00:04:03,350 --> 00:04:05,616 >> Kaya sabihin magdagdag ng 12 sa listahan na ito. 88 00:04:05,616 --> 00:04:08,070 Kailangan namin [hindi marinig] space para sa mga node. 89 00:04:08,070 --> 00:04:11,480 Inilalagay namin ang 12 sa loob ng mga ito. 90 00:04:11,480 --> 00:04:14,840 At pagkatapos ay muli, kailangan namin upang maging tunay maingat na hindi masira ang kadena. 91 00:04:14,840 --> 00:04:17,144 Gusto naming muling ayusin ang mga mga payo sa tamang pagkakasunod-sunod. 92 00:04:17,144 --> 00:04:19,519 At kung minsan na baka mean-- dahil kakailanganin namin makita lalo 93 00:04:19,519 --> 00:04:24,120 may delete-- na mayroon kaming ilang mga kalabisan ng mga payo, ngunit iyan ay OK. 94 00:04:24,120 --> 00:04:25,750 >> Kaya kung ano ang gusto naming gawin ang unang? 95 00:04:25,750 --> 00:04:28,290 Gusto ko inirerekomenda ang mga bagay na dapat mong malamang 96 00:04:28,290 --> 00:04:35,350 gawin ay upang punan ang mga payo ng 12 node bago mo pindutin ang kahit sinong tao. 97 00:04:35,350 --> 00:04:38,640 Kaya kung ano ang 12 pagpunta upang tumuro sa susunod? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 Ano ang dumating bago 12? 100 00:04:42,430 --> 00:04:43,640 Wala. 101 00:04:43,640 --> 00:04:46,280 Ngayon na napuno natin ang dagdag na impormasyon sa loob ng 12 102 00:04:46,280 --> 00:04:49,320 kaya ito ay may Nakaraang, Susunod, at halaga. 103 00:04:49,320 --> 00:04:53,505 >> Ngayon ay maaari naming magkaroon 15-- ito ng dagdag na step uusap kami about-- namin 104 00:04:53,505 --> 00:04:56,590 ay maaaring magkaroon ng 15 point bumalik sa 12. 105 00:04:56,590 --> 00:04:59,634 At ngayon maaari naming ilipat ang mga pinuno ng ang listahan ng mga link upang maging 12 din. 106 00:04:59,634 --> 00:05:02,550 Kaya ito ay medyo kapareho sa kung ano ang aming ginagawa sa isa-isa na naka-link na listahan, 107 00:05:02,550 --> 00:05:06,940 maliban para sa mga dagdag na hakbang ng pagkonekta sa lumang ulo ng listahan 108 00:05:06,940 --> 00:05:09,810 i-back sa bagong ulo ng listahan. 109 00:05:09,810 --> 00:05:12,170 >> Ngayon sabihin sa wakas tanggalin isang node mula sa isang listahan ng mga link. 110 00:05:12,170 --> 00:05:14,350 Kaya sabihin nating mayroon kaming sa ilang ibang mga pag-andar na 111 00:05:14,350 --> 00:05:18,080 ay paghahanap ng isang node gusto naming tanggalin at binigyan niya tayo ng isang pointer sa eksakto 112 00:05:18,080 --> 00:05:19,710 node na gusto naming tanggalin. 113 00:05:19,710 --> 00:05:22,360 Hindi namin kahit na need-- sabihin ang ulo ay pa rin globally ipinahayag. 114 00:05:22,360 --> 00:05:23,590 Hindi natin kailangan ang ulo dito. 115 00:05:23,590 --> 00:05:26,830 Lahat ng mga function na ito ay ginagawa ay hindi namin Natagpuan ang isang pointer sa eksakto ang node namin 116 00:05:26,830 --> 00:05:28,090 nais na makakuha ng alisan ng. 117 00:05:28,090 --> 00:05:28,940 Sabihin makakuha ng alisan ng ito. 118 00:05:28,940 --> 00:05:31,859 Ito ay isang pulutong mas madali sa doble-link list. 119 00:05:31,859 --> 00:05:33,650 First-- ito ay aktwal na lamang ng ilang mga bagay. 120 00:05:33,650 --> 00:05:38,760 Kailangan lang namin upang ayusin ang mga nakapalibot payo nodes 'upang laktawan ang mga ito sa paglipas ng 121 00:05:38,760 --> 00:05:40,240 node gusto naming tanggalin. 122 00:05:40,240 --> 00:05:43,484 At pagkatapos ay maaari naming tanggalin na node. 123 00:05:43,484 --> 00:05:45,150 Kaya muli, lang kami ng pagpunta sa pamamagitan dito. 124 00:05:45,150 --> 00:05:49,625 Malas Kami ay nagpasya na gusto naming tanggalin ang mga node X. 125 00:05:49,625 --> 00:05:51,500 At muli, kung ano Ako ginagawa here-- ng way-- 126 00:05:51,500 --> 00:05:54,580 ito ay isang pangkalahatang kaso para sa isang node na nasa gitna. 127 00:05:54,580 --> 00:05:56,547 Mayroong isang pares ng mga dagdag caveats na kayo 128 00:05:56,547 --> 00:05:59,380 kailangan mong isaalang-alang kapag nagtatanggal ka sa tunay simula ng listahan 129 00:05:59,380 --> 00:06:01,040 o sa dulo ng listahan. 130 00:06:01,040 --> 00:06:03,730 May isang pares ng mga espesyal na kaso sulok sa pakikitungo sa doon. 131 00:06:03,730 --> 00:06:07,960 >> Kaya ito ay gumagana para sa pagtanggal ng anumang node sa gitna ng isa list-- na 132 00:06:07,960 --> 00:06:11,550 ay isang lehitimong pointer forward at isang lehitimong pointer paatras, 133 00:06:11,550 --> 00:06:14,460 lehitimong Nakaraang at susunod na pointer. 134 00:06:14,460 --> 00:06:16,530 Muli, kung ikaw ay nagtatrabaho sa dulo, ikaw 135 00:06:16,530 --> 00:06:18,500 kailangan upang pangasiwaan ang mga bahagyang naiiba, 136 00:06:18,500 --> 00:06:19,570 at hindi namin ang pagpunta sa makipag-usap tungkol sa na ngayon. 137 00:06:19,570 --> 00:06:21,319 Ngunit maaari mong malamang malaman kung ano ang mga kailangan 138 00:06:21,319 --> 00:06:24,610 upang gawin lamang sa pamamagitan ng panonood ng video na ito. 139 00:06:24,610 --> 00:06:28,910 >> Kaya ko na ihiwalay namin X. X ay ang node gusto naming tanggalin mula sa listahan. 140 00:06:28,910 --> 00:06:30,140 Ano ang gagawin namin? 141 00:06:30,140 --> 00:06:32,800 Una, kailangan namin upang muling ayusin labas mga payo. 142 00:06:32,800 --> 00:06:35,815 Kailangan namin upang muling ayusin 9 sa tabi ng laktawan higit sa 13 143 00:06:35,815 --> 00:06:38,030 at punto sa 10-- saan ay kung ano lang ginawa namin. 144 00:06:38,030 --> 00:06:41,180 At kailangan din namin na muling ayusin ang 10 ni Nakaraan 145 00:06:41,180 --> 00:06:44,610 upang tumuro sa 9 sa halip na tumuturo sa 13. 146 00:06:44,610 --> 00:06:46,490 >> Kaya muli, ito ay ang diagram upang magsimula sa. 147 00:06:46,490 --> 00:06:47,730 Ito ay ang aming chain. 148 00:06:47,730 --> 00:06:51,027 Kailangan namin upang laktawan ang higit sa 13, ngunit kailangan namin upang mapanatili rin 149 00:06:51,027 --> 00:06:52,110 ang integridad ng mga listahan. 150 00:06:52,110 --> 00:06:54,680 Hindi namin nais na mawala ang anumang impormasyon sa alinmang direksyon. 151 00:06:54,680 --> 00:06:59,620 Kaya kailangan namin upang muling ayusin ang mga payo nang mabuti 152 00:06:59,620 --> 00:07:02,240 kaya hindi namin basagin ang kadena sa lahat. 153 00:07:02,240 --> 00:07:05,710 >> Kaya maaari naming sabihin 9 ni Next pointer puntos sa parehong lugar 154 00:07:05,710 --> 00:07:08,040 na Next labintatlo ni pointer points ngayon. 155 00:07:08,040 --> 00:07:10,331 Dahil kami sa huli pagpunta sa nais upang laktawan ang higit sa 13. 156 00:07:10,331 --> 00:07:13,750 Kaya kahit saan 13 puntos susunod, ikaw gusto siyam upang ituro doon sa halip. 157 00:07:13,750 --> 00:07:15,200 Kaya iyon na. 158 00:07:15,200 --> 00:07:20,370 At pagkatapos ay kung saan 13 puntos pabalik sa, anumang dumating bago 13, 159 00:07:20,370 --> 00:07:24,800 Gusto namin ng 10 upang ituro na na sa halip ng 13. 160 00:07:24,800 --> 00:07:29,290 Ngayon pansinin, kung susundin mo ang mga arrow, maaari naming i-drop 13 161 00:07:29,290 --> 00:07:32,380 walang tunay na pagkawala ng anumang impormasyon. 162 00:07:32,380 --> 00:07:36,002 Iningatan namin ang integridad ng mga listahan, paglipat ng parehong pasulong at paatras. 163 00:07:36,002 --> 00:07:38,210 At pagkatapos ay maaari naming uri lamang ng malinis na ito ng isang maliit na piraso 164 00:07:38,210 --> 00:07:40,930 sa pamamagitan ng paghila sa listahan ng sama-sama. 165 00:07:40,930 --> 00:07:43,270 Kaya rearranged namin ang mga payo sa magkabilang gilid. 166 00:07:43,270 --> 00:07:46,231 At pagkatapos ay napalaya namin X ang node na ang 13 na nilalaman, 167 00:07:46,231 --> 00:07:47,480 at hindi namin masira ang kadena. 168 00:07:47,480 --> 00:07:50,980 Kaya ginawa namin mabuti. 169 00:07:50,980 --> 00:07:53,000 >> Final note dito sa naka-link na mga listahan. 170 00:07:53,000 --> 00:07:55,990 Kaya parehong singly- at doble-link mga listahan, tulad ng nasaksihan namin, 171 00:07:55,990 --> 00:07:58,959 pag talagang mabisa insertion at pagtanggal ng mga sangkap. 172 00:07:58,959 --> 00:08:00,750 Maaari mong medyo marami gawin ito sa tapat na oras. 173 00:08:00,750 --> 00:08:03,333 Ano ang kailangan nating gawin upang tanggalin isang elemento lamang ng isang segundo na nakalipas? 174 00:08:03,333 --> 00:08:04,440 Lumipat kami sa isang pointer. 175 00:08:04,440 --> 00:08:05,920 Lumipat kami ng isa pang pointer. 176 00:08:05,920 --> 00:08:07,915 Napalaya namin X-- kinuha ng tatlong mga operasyon. 177 00:08:07,915 --> 00:08:14,500 Ito ay palaging tumatagal ng tatlong mga operasyon sa tanggalin na node-- upang magbakante ng isang node. 178 00:08:14,500 --> 00:08:15,280 >> Paano namin ipasok? 179 00:08:15,280 --> 00:08:17,280 Well, hindi namin palaging lamang tacking sa simula 180 00:08:17,280 --> 00:08:19,400 kung kami ay pagpasok ng mahusay. 181 00:08:19,400 --> 00:08:21,964 Kaya kailangan namin upang rearrange-- depende sa kung ito ay 182 00:08:21,964 --> 00:08:24,380 isang singly- o doble-link list, maaaring kailangan namin upang gawin ang tatlong 183 00:08:24,380 --> 00:08:26,824 o apat na mga operasyon max. 184 00:08:26,824 --> 00:08:28,365 Ngunit muli, ito ay palaging tatlo o apat. 185 00:08:28,365 --> 00:08:30,531 Hindi mahalaga kung gaano karaming sangkap na ito ay sa aming listahan, 186 00:08:30,531 --> 00:08:33,549 ito ay palaging tatlo o apat na operations-- tulad ng pagtanggal ay palaging 187 00:08:33,549 --> 00:08:35,320 tatlo o apat na mga operasyon. 188 00:08:35,320 --> 00:08:36,919 Ito ay pare-pareho ang panahon. 189 00:08:36,919 --> 00:08:38,169 Kaya na talagang mahusay. 190 00:08:38,169 --> 00:08:40,620 >> Sa array, kami ay gumagawa ng isang bagay tulad ng uri pagpapasok. 191 00:08:40,620 --> 00:08:44,739 Ikaw ay malamang na isipin ang insertion na uri ay hindi isang constant time algorithm. 192 00:08:44,739 --> 00:08:46,030 Ito ay talagang medyo mahal. 193 00:08:46,030 --> 00:08:48,840 Kaya ito ay isang pulutong mas mahusay para sa pagpasok. 194 00:08:48,840 --> 00:08:51,840 Ngunit tulad ng nabanggit ko sa isa-isa-link na listahan ng video, 195 00:08:51,840 --> 00:08:54,030 Mayroon kami ng downside dito rin, di ba? 196 00:08:54,030 --> 00:08:57,580 Nawala namin ang kakayahan na random access ang mga elemento. 197 00:08:57,580 --> 00:09:02,310 Hindi namin maaaring sabihin, gusto kong element bilang apat o elemento number 10 ng isang listahan ng mga link 198 00:09:02,310 --> 00:09:04,990 sa parehong paraan na aming makakaya gawin iyon sa isang array 199 00:09:04,990 --> 00:09:08,630 o maaari naming lamang direkta index sa element aming array ni. 200 00:09:08,630 --> 00:09:10,930 >> At kaya sinusubukan upang makahanap ng isang sangkap sa isang naka-link list-- 201 00:09:10,930 --> 00:09:15,880 kung naghahanap ay important-- Maaari na ngayong kumuha ng linear oras. 202 00:09:15,880 --> 00:09:18,330 Bilang makakakuha listahan na, ito maaaring tumagal ng isang karagdagang hakbang 203 00:09:18,330 --> 00:09:22,644 para sa bawat solong elemento sa listahan sa Upang makita kung ano ang aming hinahanap. 204 00:09:22,644 --> 00:09:23,560 Kaya may trade off. 205 00:09:23,560 --> 00:09:25,780 May isang piraso ng isang pro at con elemento dito. 206 00:09:25,780 --> 00:09:29,110 >> At doble-link na listahan ay hindi ang huling uri ng kumbinasyon na istraktura ng data 207 00:09:29,110 --> 00:09:32,840 na namin makipag-usap tungkol sa, pagkuha ng lahat ng mga pangunahing gusali 208 00:09:32,840 --> 00:09:34,865 bloke ng C isang paglalagay ng magkasama. 209 00:09:34,865 --> 00:09:37,900 Dahil sa katunayan, maaari naming kahit na mas mahusay kaysa sa na ito gawin 210 00:09:37,900 --> 00:09:41,970 upang lumikha ng isang istraktura ng data na maaaring ikaw ay maaaring sa paghahanap sa pamamagitan 211 00:09:41,970 --> 00:09:43,360 nasa tapat na panahon masyadong. 212 00:09:43,360 --> 00:09:46,080 Ngunit higit pa sa na sa isa pang video. 213 00:09:46,080 --> 00:09:47,150 >> Ako Doug Lloyd. 214 00:09:47,150 --> 00:09:49,050 Ito ay CS50. 215 00:09:49,050 --> 00:09:50,877