[Powered by Google Translate] A la programació, sovint necessitem per representar llistes de valors, com ara els noms dels estudiants d'una secció o classificacions en l'última prova. 

En el llenguatge C, va declarar matrius poden utilitzar per emmagatzemar llistes. És fàcil enumerar els elements d'una llista emmagatzemats en una matriu, i si vostè necessita per accedir a o modificar l'element de la llista ITH per algun índex arbitrari I, que es pot fer en un temps constant, però les matrius tenen desavantatges, també. 

Quan els declare, estem obligats a dir des del principi el grans que són, és a dir, quants elements es poden emmagatzemar i el gran que aquests elements són, que es determina pel seu tipus. Per exemple, arranjament de int (10) Pot emmagatzemar 10 elements que tenen la mida d'un int. 

No podem canviar la mida d'una matriu després de la declaració. Hem de fer una nova matriu si volem emmagatzemar més elements. La raó d'aquesta limitació que existeix és que el nostre programa emmagatzema tota la matriu com un tros contigu de memòria. Dir això és el buffer on s'emmagatzema en la nostra matriu. Hi pot haver altres variables situat just al costat de la matriu a la memòria, de manera que no pot només que la matriu més gran. 

De vegades ens agradaria que el comerç de la matriu ràpida velocitat d'accés a dades per una mica més de flexibilitat. Introduïu la llista enllaçada, una altra estructura de dades bàsiques vostè podria no ser tan familiaritzats. En un nivell alt, una llista enllaçada emmagatzema les dades en una seqüència de nodes que estan connectats entre si amb enllaços, per tant "llista enllaçada. 'el nom Com veurem, aquesta diferència en el disseny condueix a diferents avantatges i desavantatges d'una matriu. 

Aquí hi ha un codi C per a una llista molt simple enllaçada de nombres enters. Es pot veure que hem representat a cada node a la llista com una estructura que conté dues coses, un enter per emmagatzemar anomenat 'val' i un enllaç per al node següent a la llista que representem com un punter anomenat 'next'. D'aquesta manera, podem seguir la llista sencera amb només un únic punter al node primer, i després podem seguir els següents consells per al segon node, al node tercer, per al quart node, i així successivament, fins arribar a la final de la llista. 

Vostè pot ser capaç de veure un avantatge que això té sobre l'estructura matriu estàtica - amb una llista enllaçada, no necessitem una gran part de la memòria del tot. El node 1 de la llista podria viure en aquest lloc en la memòria, i el segon node podria ser tot el camí fins aquí. Podem arribar a tots els nodes no importa on en la memòria són, perquè a partir de la primera node, el punter següent de cada node ens diu exactament on anar després. 

A més, no has de dir per avançat el gran que una llista enllaçada és el camí que fem amb arrays estàtics, ja que podem seguir afegint nodes a una llista sempre que no hi ha espai en algun lloc de la memòria dels nous nodes. Per tant, les llistes enllaçades són fàcils de canviar la mida de forma dinàmica. Diguem, més tard en el programa hem d'afegir més nodes a la nostra llista. Per inserir un nou node a la llista sobre la marxa, tot el que hem de fer és assignar memòria per a aquest node, plop en el valor de les dades, i després col · locar on vulguem amb la configuració dels indicadors apropiats. 

Per exemple, si volguéssim posar un node en el medi els nodes 2 i 3 de la llista,  no hauríem de moure els nodes segon o tercer en absolut. Diguem que vas a inserir aquest node vermell. Tot el que hauria de fer és configurar punter següent del nou node perquè apunti al node 3 i després tornar a col · locar el punter següent node de segon perquè apunti al nostre nou node. Per tant, podem canviar la mida de les nostres llistes sobre la marxa ja que el nostre equip no depèn de la indexació, sinó més aviat en vincular l'ús de punters per emmagatzemar-los. 

Llistes Però un desavantatge de vinculats és que, a diferència d'una matriu estàtica, l'ordinador no només pot saltar a la meitat de la llista. Atès que l'equip ha de visitar cada node en la llista enllaçada per arribar a la següent, que prendrà més temps per trobar un node particular el que ho faria en una matriu. Per recórrer tota la llista pren temps proporcional a la longitud de la llista, o O (n) en notació asimptòtica. De mitjana, arribant qualsevol node També es necessita temps proporcional a n. 

Ara, anem a realment escriure codi que treballa amb llistes enllaçades. Diguem que volem una llista enllaçada d'enters. Podem representar un node en la llista de nou com una estructura amb dos camps, un valor enter anomenat 'val' i un punter proper al següent node de la llista. Bé, sembla bastant simple. 

Suposem que volem escriure una funció que recorre la llista i imprimeix el valor emmagatzemat en l'últim node de la llista. Bé, això vol dir que haurem de recórrer tots els nodes de la llista per trobar l'última, però ja no estem afegint o esborrar res, no volem canviar l'estructura interna dels punters següents a la llista. 

Per tant, anem a necessitar un punter específicament per traversal que anomenarem "crawler". Es arrosseguen a través de tots els elements de la llista seguint la cadena de punters propers. Tots hem emmagatzemat és un punter al node primer, o "cap" de la llista. Punts del cap a la primera node. És de tipus punter a node. 

Per obtenir l'actual primera node a la llista, hem d'eliminar la referència aquest indicador, però abans de poder deferenciarlo, hem de comprovar si el punter és nul en primer lloc. Si és nul, la llista és buida, i hem imprimir un missatge que, pel fet que la llista és buida, no hi ha últim node. Però, suposem que la llista no és buida. Si no és així, llavors hem de gatejar per tota la llista fins arribar a l'últim node de la llista, i com podem saber si estem davant l'últim node a la llista? 

Bé, si el punter següent d'un node és nul, sabem que estem al final des del següent punter darrera no tindria cap node següent a la llista per apuntar. És una bona pràctica per mantenir sempre punter següent de l'últim node de s'inicialitzen a null tenir una propietat estàndard que ens avisa quan hem arribat al final de la llista. 

Per tant, si crawler → següent és nul, recordar que la sintaxi de fletxa és un accés directe per eliminar la referència un punter a una estructura, a continuació, accedir a seu següent camp equivalent al maldestre: (* Crawler). Següent. Una vegada que hagis trobat l'últim node, volem imprimir crawler → val, el valor en el node actual que sabem que és l'última. En cas contrari, si no estem encara en l'últim node de la llista, hem de passar a la següent node a la llista i comprovar si aquest és l'últim. Per això, s'acaba d'establir nostre punter sobre erugues per apuntar al següent valor del node actual, és a dir, el node següent a la llista. Això es fa mitjançant l'establiment crawler = crawler → següent. Després repetim aquest procés, amb un llaç per exemple, fins a trobar l'últim node. Així, per exemple, si rastrejador estava apuntant al capdavant, ens vam proposar rastrejador perquè apunti a erugues → següent, que és el mateix que el camp proper de la primera node. Així que, ara que el nostre rastrejador està apuntant al node 2, i, de nou, es repeteix això amb un bucle, fins que hàgim trobat l'últim node, és a dir, on punter següent del node apunta null. I aquí el tenim, hem trobat l'últim node de la llista, i la impressió del seu valor, només ha d'utilitzar crawler → val. 

Travessant no és tan dolent, però què passa amb la inserció? Diguem que volem inserir un nombre sencer en la 4 ª posició en una llista de nombres enters. Que està entre els nodes actuals tercer i quart. Un cop més, hem de recórrer la llista només per arribar a la tercera part, la qual estem inserint després. Així, vam crear un punter rastrejador de nou per recórrer la llista, comprovar si el nostre cap punter és nul, i si no ho és, apuntar amb el punter sobre erugues en el node principal. Per tant, estem en l'element primer. Hem d'anar cap endavant 2 elements més abans de poder inserir, pel que podem utilitzar un bucle for int i = 1; i <3; i + + i en cada iteració del bucle, avançar en el punter sobre erugues presentades per un node comprovant si el camp proper del node actual és nul · la, i si no és així, moure el nostre rastrejador punter al següent node fixant igual al següent punter del node actual. Per tant, des del nostre bucle per fer això, diu dues vegades, hem arribat al node 3, i una vegada que el nostre punter rastrejador ha arribat al node després de que volem inserir el nostre nou sencer, Com és en realitat la inserció? 

Doncs bé, el nostre nou sencer ha de ser inserit en la llista com a part de la seva pròpia estructura de node, ja que això és realment una seqüència de nodes. Per tant, farem un nou punter al node anomenat 'new_node,' i configurar-lo perquè apunti a la memòria que ara assignar a la pila per al node en si, i la quantitat de memòria hem d'assignar? Doncs bé, la mida d'un node, i volem establir el seu camp val l'enter que volem inserir. Diguem, 6. Ara, el node conté el nostre valor sencer. També és una bona pràctica per inicialitzar camp proper del nou node per apuntar a null, però ara què? 

Cal canviar l'estructura interna de la llista i els indicadors continguts en els següents de la llista Els nodes 3 i 4. Atès que els punters propers determinar l'ordre de la llista, i ja que estem introduint el nostre nou node a la dreta en el mitjà de la llista, que pot ser una mica complicat. Això és perquè, recordi, el nostre equip només coneix la ubicació dels nodes a la llista perquè dels punters propers emmagatzemats en els nodes anteriors. Per tant, si mai perdut el rastre de cap d'aquests llocs, diuen que en canviar un dels punters següents a la llista, Per exemple, diguem que canviem camp següent node de la tercera de perquè apunti a algun node per aquí. Ens agradaria estar fora de sort, ja que no ho faria Té alguna idea d'on trobar la resta de la llista, i això és, òbviament, molt malament. Per tant, hem de tenir molta cura per tal de en el qual manipulem nostres punters propers durant la inserció. 

Així que, per simplificar això, direm que nostres primers 4 nodes es denominen A, B, C, i D, amb les fletxes que representen la cadena de punters que connecten els nodes. Per tant, hem d'inserir el nostre nou node entre els nodes C i D. És molt important fer-ho en l'ordre correcte, i jo et mostraré per què. 

Fem una ullada a la forma incorrecta de fer-ho en primer lloc. Hey, sabem que el nou node ha de venir a la dreta després de C, així que anem a establir el punter pròxim C perquè apunti a new_node. D'acord, sembla estar bé, només hem d'acabar ara per fer punt del nou node punter prop de D, però espera, com podem fer això? L'única cosa que ens pot dir on D és, va ser el següent punter emmagatzemat prèviament en C, però ens va tornar a escriure aquest punter perquè apunti al nou node, de manera que ja no tenim ni idea d'on D és en la memòria, i hem perdut la resta de la llista. No és bo en absolut. 

Així que, com podem fer això bé? En primer lloc, assenyalar punter següent del nou node al Sr Ara, tant el nou node i la de C pròxims punters apunten cap al mateix node, D, però això està bé. Ara podem assenyalar següent punter de C en el nou node. Per tant, hem fet això sense perdre cap dada. En el codi, C és el node actual que el recorregut punter rastrejador fa referència, i D està representat pel node al qual apunta el camp següent node actual, o rastrejador → següent. Així, en primer lloc establir el punter següent del nou node perquè apunti a erugues → següent, de la mateixa manera que vam dir punter proper new_node han de tenir per apuntar a D a la il · lustració. Llavors, podem establir el punter següent del node actual al nostre nou node, la mateixa manera que va haver d'esperar al punt C new_node en el dibuix. Ara tot està en ordre, i no va perdre fer un seguiment de les dades, i vam ser capaços de simplement enganxar nostre nou node al mig de la llista sense reconstruir tota la cosa, o fins i tot canviant els elements la forma en què s'han hagut de amb una matriu de longitud fixa. 

Per tant, les llistes enllaçades són un bàsic, però important, l'estructura de dades dinàmica que tenen avantatges i desavantatges en comparació amb les matrius i altres estructures de dades, i com és sovint el cas en informàtica, és important saber quan utilitzar cada eina, perquè pugui triar l'eina adequada per al treball correcte. 

Per practicar més, intenti escriure funcions per eliminar nodes d'una llista enllaçada - recordi anar amb compte amb l'ordre en què es reorganitzen els punters següents per assegurar-se que no perdi una bona part de la seva llista - o una funció per comptar els nodes en una llista enllaçada, o una diversió, per invertir l'ordre de tots els nodes d'una llista enllaçada. 

El meu nom és Jackson Steinkamp, ​​això és CS50.