[MUSIC nagpe-play] DOUG LLOYD: Lahat ng karapatan. Kaya't kung ikaw lang tapos na video sa isa-isa-link listahan ng paumanhin Iniwan ko sa iyo off sa isang piraso ng isang cliffhanger. Ngunit Natutuwa akong nandito ka upang matapos ang kuwento ng doble-link list. 

Kaya kung ang pagpapabalik sa iyo mula sa video na, usapan natin tungkol sa kung paano isa-isa na naka-link mga listahan ng gagawin dumalo sa aming kakayahan sa pakikitungo sa mga impormasyon kung saan ang bilang ng mga elemento o ang bilang ng mga item sa isang listahan ay maaaring lumaki o pag-urong. Maaari naming ngayon makikitungo sa isang bagay tulad na, kung saan hindi namin ma haharapin ang mga ito sa array. 

Subalit sila magtiis sa isa kritikal na limitasyon na ay na may isang isa-isa na naka-link listahan, maaari naming lamang kailanman ilipat sa isang solong direksyon sa pamamagitan ng mga listahan. At ang tanging tunay na sitwasyon saan na maaaring maging isang problema ay kapag kami ay nagsisikap na tanggalin ang isang elemento. At hindi namin kahit na pag-usapan kung paano ito gawin sa isang isa-isa-link na listahan sa pseudocode. Ito ay tiyak na maaaring gawin, ngunit maaaring ito ay isang bit ng isang problema. Kaya kung nakita mo ang iyong sarili sa isang sitwasyon na kung saan ang sinusubukan mong tanggalin ang single elemento mula sa listahan o ito ay pagpunta sa kinakailangan na kayo ay pagbubura single elemento mula sa listahan, maaari mong isaalang isaalang-alang ang paggamit ng isang doble-link ilista sa halip ng isang isa-isa-link na listahan. Dahil magpapahintulot sa inyo doble-link na listahan upang ilipat ang parehong pasulong at pabalik sa pamamagitan ng mga listahan sa halip ng lamang pasulong sa pamamagitan ng list-- sa pamamagitan lamang ng pagdaragdag ng isa dagdag na elemento sa aming mga kahulugan ng istraktura para sa mga doble-link listahan node. 

Muli, kung hindi ka pagpunta sa ay pagtanggal single elemento mula sa list-- dahil kami ay nagdadagdag ng ng dagdag na field sa aming istraktura kahulugan, ang nodes sa kanilang sarili para sa doble-link na listahan ay magiging mas malaki. Sila ay pagpunta sa tumagal up pa bytes ng memorya. At kaya kung hindi ito ay isang bagay ikaw ay pagpunta sa kailangan upang gawin, maaari kang magpasya ito ay Hindi karapat-dapat ang off kalakalan na magkaroon ng gastusin sa dagdag na bytes ng memory kinakailangan para sa isang doble-link na listahan kung hindi ka pagpunta sa pagtanggal ng nag-iisang sangkap. Ngunit ang mga ito rin ay cool na para sa masyadong iba pang mga bagay. 

Kaya tulad ng sinabi ko, kami na lang si isang single field sa aming istraktura definition-- ito paniwala ng isang Previous pointer. Kaya sa isang isa-isa-link na listahan, kami may halaga at ang Next pointer, kaya ang doble-link na listahan lamang ay isang paraan upang ilipat paurong rin. 

Ngayon sa isa-isa na naka-link listahan ng video, usapan natin tungkol sa mga ito ay limang ng pangunahing bagay na kailangan mo upang maging magawa sa trabaho na may mga listahan ng link. At para sa karamihan sa mga ito, ang katunayan na ito ay isang doble-link na listahan ay hindi tunay na isang malaking jump. Maaari pa rin kami sa paghahanap sa pamamagitan lamang sa pamamagitan ng paglipat ng pasulong mula simula hanggang katapusan. Maaari pa rin naming lumikha ng isang node sa labas ng manipis na hangin, medyo marami sa parehong paraan. Maaari naming tanggalin ang mga listahan pretty marami sa parehong paraan masyadong. Ang tanging bagay na ay subtly naiiba, talaga, ay pagpasok bagong nodes sa listahan, at kami ay sa wakas makipag-usap tungkol sa pagtanggal isang solong elemento mula sa listahan pati na rin. Muli, medyo marami ang iba pang mga tatlong, hindi namin hindi pagpunta sa makipag-usap tungkol sa mga ito sa ngayon dahil hindi lang nila very minor tweak sa mga ideya na tinalakay sa isa-isa-link na listahan ng video. 

Kaya hayaan ipasok ang isang bagong node sa isang doble-link na listahan. Usapan natin ang tungkol sa paggawa nito para sa isa-isa-link listahan pati na rin, ngunit may isang pares ng mga dagdag nakakakuha sa doble-link list. Humihingi kami [? pagpasa?] sa ulo ng listahan dito at ilang di-makatwirang halaga, at gusto naming makuha ang bagong ulo ng listahan ng mga function na ito. Iyon ang dahilan kung bakit ito ay nagbabalik ng isang dllnode star. Kaya ano ang mga hakbang na ito? Ang mga ito ay, muli, halos katulad upang isa-isa-listahan ng link may isang extrang karagdagan. Gusto naming naglalaan space para sa isang bagong node at suriin upang tiyakin na ito ay may-bisa. Gusto naming punan na node up sa kahit anong impormasyon ang aming gusto mong ilagay sa mga ito. Ang huling bagay na kailangan namin upang do-- ang dagdag na bagay na kailangan naming gawin, rather-- ay upang ayusin ang Previous pointer ng lumang ulo ng listahan. Tandaan na dahil ng doble-link na listahan, maaari naming sumulong at backwards-- saan ay nangangahulugan na ang bawat node aktwal na tumuturo sa dalawang iba pang mga nodes sa halip na isa lamang. At kaya kailangan namin upang ayusin ang lumang ulo ng listahan upang ituro paatras na ang bagong pinuno ng ang listahan ng mga link, na kung saan ay isang bagay na hindi namin ay may sa gawin bago. At tulad ng dati, bumalik kami lamang ng isang pointer sa bagong ulo ng listahan. 

Kaya narito ang isang listahan. Gusto naming ipasok 12 sa listahan na ito. Abiso na ang mga diagram ay bahagyang naiiba. Ang bawat node ay naglalaman ng tatlong fields-- data, at isang Next pointer sa pula, at isang Previous pointer sa asul. Walang dumating bago ang 15 node, kaya nito Nakaraan pointer ay null. Ito ang simula ng listahan. May walang bago ito. At walang dumating pagkatapos ng 10 node, at kaya Susunod pointer ay null rin. 

Kaya sabihin magdagdag ng 12 sa listahan na ito. Kailangan namin [hindi marinig] space para sa mga node. Inilalagay namin ang 12 sa loob ng mga ito. At pagkatapos ay muli, kailangan namin upang maging tunay maingat na hindi masira ang kadena. Gusto naming muling ayusin ang mga mga payo sa tamang pagkakasunod-sunod. At kung minsan na baka mean-- dahil kakailanganin namin makita lalo may delete-- na mayroon kaming ilang mga kalabisan ng mga payo, ngunit iyan ay OK. 

Kaya kung ano ang gusto naming gawin ang unang? Gusto ko inirerekomenda ang mga bagay na dapat mong malamang gawin ay upang punan ang mga payo ng 12 node bago mo pindutin ang kahit sinong tao. Kaya kung ano ang 12 pagpunta upang tumuro sa susunod? 15. Ano ang dumating bago 12? Wala. Ngayon na napuno natin ang dagdag na impormasyon sa loob ng 12 kaya ito ay may Nakaraang, Susunod, at halaga. 

Ngayon ay maaari naming magkaroon 15-- ito ng dagdag na step uusap kami about-- namin ay maaaring magkaroon ng 15 point bumalik sa 12. At ngayon maaari naming ilipat ang mga pinuno ng ang listahan ng mga link upang maging 12 din. Kaya ito ay medyo kapareho sa kung ano ang aming ginagawa sa isa-isa na naka-link na listahan, maliban para sa mga dagdag na hakbang ng pagkonekta sa lumang ulo ng listahan i-back sa bagong ulo ng listahan. 

Ngayon sabihin sa wakas tanggalin isang node mula sa isang listahan ng mga link. Kaya sabihin nating mayroon kaming sa ilang ibang mga pag-andar na ay paghahanap ng isang node gusto naming tanggalin at binigyan niya tayo ng isang pointer sa eksakto node na gusto naming tanggalin. Hindi namin kahit na need-- sabihin ang ulo ay pa rin globally ipinahayag. Hindi natin kailangan ang ulo dito. Lahat ng mga function na ito ay ginagawa ay hindi namin Natagpuan ang isang pointer sa eksakto ang node namin nais na makakuha ng alisan ng. Sabihin makakuha ng alisan ng ito. Ito ay isang pulutong mas madali sa doble-link list. First-- ito ay aktwal na lamang ng ilang mga bagay. Kailangan lang namin upang ayusin ang mga nakapalibot payo nodes 'upang laktawan ang mga ito sa paglipas ng node gusto naming tanggalin. At pagkatapos ay maaari naming tanggalin na node. Kaya muli, lang kami ng pagpunta sa pamamagitan dito. Malas Kami ay nagpasya na gusto naming tanggalin ang mga node X. At muli, kung ano Ako ginagawa here-- ng way-- ito ay isang pangkalahatang kaso para sa isang node na nasa gitna. Mayroong isang pares ng mga dagdag caveats na kayo kailangan mong isaalang-alang kapag nagtatanggal ka sa tunay simula ng listahan o sa dulo ng listahan. May isang pares ng mga espesyal na kaso sulok sa pakikitungo sa doon. 

Kaya ito ay gumagana para sa pagtanggal ng anumang node sa gitna ng isa list-- na ay isang lehitimong pointer forward at isang lehitimong pointer paatras, lehitimong Nakaraang at susunod na pointer. Muli, kung ikaw ay nagtatrabaho sa dulo, ikaw kailangan upang pangasiwaan ang mga bahagyang naiiba, at hindi namin ang pagpunta sa makipag-usap tungkol sa na ngayon. Ngunit maaari mong malamang malaman kung ano ang mga kailangan upang gawin lamang sa pamamagitan ng panonood ng video na ito. 

Kaya ko na ihiwalay namin X. X ay ang node gusto naming tanggalin mula sa listahan. Ano ang gagawin namin? Una, kailangan namin upang muling ayusin labas mga payo. Kailangan namin upang muling ayusin 9 sa tabi ng laktawan higit sa 13 at punto sa 10-- saan ay kung ano lang ginawa namin. At kailangan din namin na muling ayusin ang 10 ni Nakaraan upang tumuro sa 9 sa halip na tumuturo sa 13. 

Kaya muli, ito ay ang diagram upang magsimula sa. Ito ay ang aming chain. Kailangan namin upang laktawan ang higit sa 13, ngunit kailangan namin upang mapanatili rin ang integridad ng mga listahan. Hindi namin nais na mawala ang anumang impormasyon sa alinmang direksyon. Kaya kailangan namin upang muling ayusin ang mga payo nang mabuti kaya hindi namin basagin ang kadena sa lahat. 

Kaya maaari naming sabihin 9 ni Next pointer puntos sa parehong lugar na Next labintatlo ni pointer points ngayon. Dahil kami sa huli pagpunta sa nais upang laktawan ang higit sa 13. Kaya kahit saan 13 puntos susunod, ikaw gusto siyam upang ituro doon sa halip. Kaya iyon na. At pagkatapos ay kung saan 13 puntos pabalik sa, anumang dumating bago 13, Gusto namin ng 10 upang ituro na na sa halip ng 13. Ngayon pansinin, kung susundin mo ang mga arrow, maaari naming i-drop 13 walang tunay na pagkawala ng anumang impormasyon. Iningatan namin ang integridad ng mga listahan, paglipat ng parehong pasulong at paatras. At pagkatapos ay maaari naming uri lamang ng malinis na ito ng isang maliit na piraso sa pamamagitan ng paghila sa listahan ng sama-sama. Kaya rearranged namin ang mga payo sa magkabilang gilid. At pagkatapos ay napalaya namin X ang node na ang 13 na nilalaman, at hindi namin masira ang kadena. Kaya ginawa namin mabuti. 

Final note dito sa naka-link na mga listahan. Kaya parehong singly- at doble-link mga listahan, tulad ng nasaksihan namin, pag talagang mabisa insertion at pagtanggal ng mga sangkap. Maaari mong medyo marami gawin ito sa tapat na oras. Ano ang kailangan nating gawin upang tanggalin isang elemento lamang ng isang segundo na nakalipas? Lumipat kami sa isang pointer. Lumipat kami ng isa pang pointer. Napalaya namin X-- kinuha ng tatlong mga operasyon. Ito ay palaging tumatagal ng tatlong mga operasyon sa tanggalin na node-- upang magbakante ng isang node. 

Paano namin ipasok? Well, hindi namin palaging lamang tacking sa simula kung kami ay pagpasok ng mahusay. Kaya kailangan namin upang rearrange-- depende sa kung ito ay isang singly- o doble-link list, maaaring kailangan namin upang gawin ang tatlong o apat na mga operasyon max. Ngunit muli, ito ay palaging tatlo o apat. Hindi mahalaga kung gaano karaming sangkap na ito ay sa aming listahan, ito ay palaging tatlo o apat na operations-- tulad ng pagtanggal ay palaging tatlo o apat na mga operasyon. Ito ay pare-pareho ang panahon. Kaya na talagang mahusay. 

Sa array, kami ay gumagawa ng isang bagay tulad ng uri pagpapasok. Ikaw ay malamang na isipin ang insertion na uri ay hindi isang constant time algorithm. Ito ay talagang medyo mahal. Kaya ito ay isang pulutong mas mahusay para sa pagpasok. Ngunit tulad ng nabanggit ko sa isa-isa-link na listahan ng video, Mayroon kami ng downside dito rin, di ba? Nawala namin ang kakayahan na random access ang mga elemento. Hindi namin maaaring sabihin, gusto kong element bilang apat o elemento number 10 ng isang listahan ng mga link sa parehong paraan na aming makakaya gawin iyon sa isang array o maaari naming lamang direkta index sa element aming array ni. 

At kaya sinusubukan upang makahanap ng isang sangkap sa isang naka-link list-- kung naghahanap ay important-- Maaari na ngayong kumuha ng linear oras. Bilang makakakuha listahan na, ito maaaring tumagal ng isang karagdagang hakbang para sa bawat solong elemento sa listahan sa Upang makita kung ano ang aming hinahanap. Kaya may trade off. May isang piraso ng isang pro at con elemento dito. 

At doble-link na listahan ay hindi ang huling uri ng kumbinasyon na istraktura ng data na namin makipag-usap tungkol sa, pagkuha ng lahat ng mga pangunahing gusali bloke ng C isang paglalagay ng magkasama. Dahil sa katunayan, maaari naming kahit na mas mahusay kaysa sa na ito gawin upang lumikha ng isang istraktura ng data na maaaring ikaw ay maaaring sa paghahanap sa pamamagitan nasa tapat na panahon masyadong. Ngunit higit pa sa na sa isa pang video. 

Ako Doug Lloyd. Ito ay CS50.