[REPRODUCCIÓ DE MÚSICA] DOUG LLOYD: D'acord. Així que si vostè acaba d'acabar que de vídeo a les llistes per separat vinculats sorry Et vaig deixar en un mica d'un cliffhanger. Però m'alegro que estiguis aquí per acabar la història de les llistes doblement enllaçades. 

Així que si vostè recorda de aquest vídeo, parlem sobre com lligat individualment- llistes fan assistir a la nostra capacitat per fer front a la informació on el nombre d'elements o el nombre d'articles en una llista pot créixer o encongir-se. Ara podem fer front a alguna cosa així com que, quan no podíem tractar amb ell amb matrius. 

Però ells pateixen d'un limitació crítica que és que amb vinculats per separat, un llista, podem només sempre moure en una sola direcció a través de la llista. I l'única situació real on això pot esdevenir un problema va ser quan estàvem tractant de suprimir un sol element. I ni tan sols discutim com fer-ho en una llista simplement enllaçada en pseudocodi. Sens dubte, és factible, però que pot ser una mica complicat. Així que si vostè es troba en una situació on vostè està tractant d'eliminar elements individuals de la llista o que serà necessari que se li esborrant elements individuals de la llista, és possible que vulgueu considerar l'ús lligada doblement 01:00 llista en lloc d'una llista simplement enllaçada. Perquè les llistes doblement enllaçades, que permeten per moure cap endavant i cap enrere a través de la llista en lloc de just davant a través de la pel·lícules-- només mitjançant l'addició d'un element extra a la nostra definició de l'estructura per al node de la llista doblement enllaçada. 

Un cop més, si no vas a ser esborrat d'elements individuals Del pel·lícules-- perquè estem afegint un camp addicional a la nostra estructura definició, els propis nodes per a les llistes doblement enlazadas- van a ser més gran. Ells van a tenir fins a més bytes de memòria. I pel que si això no és una cosa vostè va a haver de fer, vostè pot decidir que és No val la pena el trade off a haver de passar l'extra bytes de memòria necessaris per obtenir una llista doblement enllaçada si no estàs va a ser esborrat d'elements individuals. Però també són fresc per a altres coses també. 

Així com he dit, només hem d'afegir un sol camp per a la nostra estructura definition-- aquesta noció d'un punter anterior. Així que amb una llista simplement enllaçada, ens tenir el valor i el punter següent, de manera que la llista doblement enllaçada només té una manera de moure cap enrere també. 

Ara a lligades individualment-la llista de vídeos, parlem sobre aquests estan cinc de la coses principals que necessita per ser capaç de fer per treballar amb llistes enllaçades. I per a la majoria d'ells, el fet de que es tracta d'una llista doblement enllaçada no és realment un gran salt. Podem encara buscar a través de tot just avançant des del principi fins al final. Encara podem crear un node de res, més o menys la mateixa manera. Podem eliminar llistes bastant de la mateixa manera també. Les úniques coses que són subtilment diferents, Realment, s'insereix nous nodes a la llista, i finalment parlarem sobre l'eliminació un sol element de la llista també. Un cop més, més o menys els altres tres, que estem no vaig a parlar d'ells en aquest moment perquè són just ajustos molt de menor importància en les idees discutides en la llista de vídeo simplement enllaçada. 

Així que anem a inserir un nou node en una llista doblement enllaçada. Parlem sobre fer això per llistes simplement enllaçada, així, però hi ha un parell de addicional les captures amb les llistes doblement enllaçades. Estem [? passant?] al cap de la enumerar aquí i una mica de valor arbitrari, i volem que el nou cap de la llista d'aquesta funció. És per això que torna un estel dllnode. Quins són els passos? Ells són, de nou, molt similar a les llistes lligades individualment- amb una addició extra. Volem assigna espai per a un nou node i de verificació per assegurar-se que és vàlid. Volem omplir aquest node fins amb qualsevol informació que vol posar en ell. L'última cosa que necessitem fer-- el cosa extra que hem de fer, rather-- és fixar el punter Anterior de l'antic cap de la llista. Recordeu que a causa llistes d'enllaços doblement, podem avançar i backwards-- que vol dir que cada node assenyala en realitat a altres dos nodes en lloc d'un de sol. I així hem d'arreglar l'antic cap de la llista apuntar cap enrere per al nou cap de la llista enllaçada, que era una cosa que no havíem de fer abans. I com abans, només tornem una punter a la nova cap de la llista. 

Així que aquí està una llista. Volem inserir 12 en aquesta llista. Tingueu present que el diagrama és lleugerament diferent. Cada node conté tres fields-- dades i un punter Següent a vermell, i un punter anterior en blau. Res ve abans que el node 15, pel que la seva punter anterior és nul. És el principi de la llista. No hi ha res abans. I res ve després que el node 10 i per la qual cosa és Següent punter és nul també. 

Així que anem a afegir 12 a aquesta llista. Necessitem [inaudible] espai per al node. Posem 12 a l'interior de la mateixa. I, de nou, hem de ser molt compte de no trencar la cadena. Volem canviar el punters en l'ordre correcte. I a vegades això pot dir-- com veurem en particular amb delete-- que tenim alguns punters redundants, però això està bé. 

Llavors, què és el que volem fer primer? Jo recomanaria el Coses que vostè ha, probablement, fer són per omplir els punters del 12 node abans de tocar a ningú més. Llavors, què està passant 12 per assenyalar a continuació? 15. Què ve abans dels 12? Res. Ara hem omplert el Informació addicional en 12 pel que té Anterior, Següent, i valor. 

Ara podem tenir 15-- aquest accessori pas que estàvem parlant sobre-- ens pot tenir 15 punts de nou a 12. I ara podem moure el cap de la llista enllaçada a ser també 12. Així que és bastant similar al que estaven fent amb les llistes simplement enllaçada, excepte pel pas addicional de que connecta l'antic cap de la llista donar suport a la nova cap de la llista. 

Ara anem a per fi eliminar un node d'una llista enllaçada. Així que anem a dir que tenim alguna altra funció que és trobar un node que volem eliminar i ens ha donat un punter a exactament el node que volem eliminar. Ni tan sols need-- diem la cap està encara a nivell mundial ha declarat. No necessitem el cap aquí. Tota aquesta funció està fent és que hem trobat un punter a exactament el que el node vol desfer. Anem a desfer-se'n. És molt més fàcil amb llistes doblement enllaçada. Primer-- en realitat només un parell de coses. Només hem de fixar l'envolta punters nodes 'perquè se salten més el node que voleu eliminar. I llavors podem eliminar aquest node. Així que de nou, només anem per aquí. Aparentment Hem decidit que volem eliminar el node X. I de nou, el que estic fent aquí-- pel manera- és un cas general d'una node que es troba en el medi. Hi ha un parell de advertiments addicionals que vostè considerar quan s'està esborrant el principi de la llista o el final de la llista. Hi ha un parell d'especials casos de cantonada per fer front a allà. 

Així que això funciona per esborrar qualsevol node en el medi de la qual pel·lícules-- té un punter legítima cap endavant i un punter legítima cap enrere, legítim punter anterior i següent. Un cop més, si vostè està treballant amb els extrems, que necessari per manejar els lleugerament diferent, i nosaltres no anem a parlar d'això ara. Però vostè pot probablement esbrinar el que necessita de fer amb només mirar aquest vídeo. 

Així que ens hem aïllat X. X és el node volem eliminar de la llista. Què fem? En primer lloc, hem de reorganitzar els punters fora. Hem de reorganitzar 9 del proper per saltar més de 13 i apunten a 10-- que és el que acabem de fer. I també hem de reorganitzar 10 Anterior per assenyalar a 9 en lloc d'apuntar a 13. 

Així que de nou, aquesta va ser la diagrama per començar. Aquesta va ser la nostra cadena. Hem de saltar sobre 13, però necessitem també preservar la integritat de la llista. No volem perdre cap informació en qualsevol direcció. Així que hem de reordenar els punters acuradament pel que no trenquem la cadena en absolut. 

Així que podem dir de 9 Següent punter apunta al mateix lloc que dels tretze Següent punter apunta ara. Perquè som el temps voldrà saltar sobre 13. Així que allà on 13 punts següent, volen nou a punt no lloc. Així que això és tot. I a continuació, sempre que sigui 13 punts enrere a, el que ve abans dels 13, volem assenyalar 10 perquè en lloc de 13. Ara noti, si vostè segueix les fletxes, que poden caure 13 sense arribar a perdre la informació. Hem mantingut la integritat de la llista, movent-se cap endavant i cap enrere. I llavors podem només una espècie de netejar-una mica tirant de la llista junts. Així que va reorganitzar la punters a cada costat. I llavors ens alliberem X el node que contenia 13, i no ens trenquem la cadena. Així ho vam fer bé. 

Nota final aquí a llistes enllaçades. Així doncs, tant singly- i doblement enllaçada llistes, com hem vist, suport inserció realment eficient i cancel·lació de les seves elements. Vostè pot gairebé fer a temps constant. Què havíem de fer per eliminar un element només un segon enrere? Ens mudem d'un punter. Ens mudem altre punter. Ens alliberem X-- prendre tres operacions. Sempre porta tres operacions a eliminar aquesta node-- per alliberar un node. 

Com ens inserim? Bé, estem simplement sempre virades al començament si estem inserint de manera eficient. Així que hem de rearrange-- depenent de si es tracta de 1 singly- o doblement enllaçada llista, pot ser que hagi de fer de tres o max quatre operacions. Però, de nou, sempre és tres o quatre. No importa quants elements estan en la nostra llista, sempre tres o quatre operations-- de la mateixa manera que l'eliminació és sempre tres o quatre operacions. És temps constant. Així que això és realment genial. 

Amb els arranjaments, que estàvem fent alguna cosa així com l'ordenació per inserció. Vostè probablement recordarà que la inserció espècie no és un algoritme de temps constant. En realitat és bastant car. Així que això és molt millor per a la inserció. Però com he esmentat en el individualment lligada llista de vídeos, tenim un desavantatge aquí també, oi? Hem perdut la capacitat de accedir aleatòriament elements. No podem dir, vull element número quatre o l'element número 10 d'una llista enllaçada de la mateixa manera que podem fer això amb una matriu o podem simplement directament índex en l'element de la nostra matriu. 

I així, tractant de trobar una element d'una pel·lícules-- vinculats si la recerca és important-- Ara pot prendre temps lineal. Com la llista s'allarga, es podria donar un pas addicional per a cada element en la llista de Per trobar el que estem buscant. Així que no hi ha compensacions. Hi ha una mica d'un professional i l'element aire aquí. 

I les llistes doblement enllaçades, no n'hi ha últim tipus d'estructura de dades de combinació que parlarem, tenint tot l'edifici bàsic blocs de C 1 armant. Perquè, de fet, podem fins i tot una mica millor que això per crear una estructura de dades que vostè podria ser capaç de buscar a través de en temps constant també. Però més sobre això en un altre vídeo. 

Sóc Doug Lloyd. Això és CS50.