[Powered by Google Translate] Na programación, moitas veces necesitamos representar listas de valores, como os nomes dos alumnos nunha sección ou os seus resultados no último exame. 

Na linguaxe C, declarado matrices poden ser utilizadas para almacenar listas. É doado enumerar os elementos dunha lista almacenados nunha matriz, e se precisa acceder ou modificar o elemento da lista om por algún índice arbitrario I, que se pode facer en tempo constante, pero as matrices presentan desvantaxes, tamén. 

Cando declaralo los, somos obrigados a dicir na fronte como son grandes, é dicir, cantos elementos que poden almacenar e que o tamaño destes elementos son, que é determinada polo tipo. Por exemplo, int arr (10) pode almacenar 10 elementos que son do tamaño dun int. 

Non podemos cambiar o tamaño dunha matriz tras a declaración. Temos que facer unha nova matriz se desexa almacenar máis elementos. A razón desa limitación existe é que o noso programa almacena todo o conxunto como unha peza contiguo de memoria. Dicir que este é o buffer onde se almacenan na nosa matriz. Pode haber outras variables situado ao lado da matriz na memoria, por iso non podemos só facer a matriz maior. 

Ás veces, nós queremos cambiar de velocidade a matriz de acceso rápido de datos para un pouco máis de flexibilidade. Escriba unha lista ligada, outra estrutura de datos básica non pode ser tan familiarizado. A un nivel elevado, unha lista ligada almacena os datos nunha secuencia de nodos que están ligados uns ós outros con ligazóns, polo tanto, "lista ligada." nome Como veremos, esta diferencia no proxecto conduce a diferentes vantaxes e desvantaxes dunha matriz. 

Aquí está o código C para unha lista moi sinxelo ligada de enteiros. Podes ver que temos representado cada nodo na lista como unha estrutura que contén dúas cousas, un enteiro para almacenar chamado 'Val' e un enlace ao seguinte nodo na lista que representamos como un punteiro chamado 'Seguinte'. Desta forma, é posible seguir toda a lista con só un único punteiro para o apartado 1, e entón podemos seguir os punteiros próximos para o apartado 2, para o apartado 3, ao apartado 4, e así por diante, ata chegar ao final da lista. 

Pode ser capaz de ver unha vantaxe que ten sobre a estrutura array estático - con unha lista ligada, non necesitamos un gran anaco de memoria completamente. O apartado 1 da lista podería vivir neste lugar na memoria, eo apartado 2 podería ser todo o camiño ata aquí. Podemos chegar a todos os nós, non importa onde eles están na memoria, porque dende o apartado 1, o punteiro preto de cada nodo nos di exactamente onde ir. 

Ademais, non hai que dicir na fronte como unha grande lista encadeada será a nosa forma de facer arrays estáticos, unha vez que podemos continuar a engadir nós a unha lista mentres non hai espazo en algún lugar na memoria para novos nós. Polo tanto, listas ligadas son fáciles de cambiar o tamaño dinamicamente. Dicir, máis tarde no programa, cómpre engadir máis nós na nosa lista. Para inserir un novo nodo na nosa lista en tempo real, todo o que temos que facer é reservar memoria para ese nodo, plop por valor de datos, e despois poñelas onde quere, axustando os punteiros apropiados. 

Por exemplo, se quixésemos poñer un nó no medio os nós 2 e 3 da lista,  non teriamos para mover os nós de 2 ou 3 en todo. Dicir que estamos introducindo este nodo vermello. Todo o que temos que facer é definir punteiro próximo ao novo nodo para apuntar para o apartado 3 e, a continuación, religar punteiro próximo apartado 2 do para apuntar para o novo nodo. Así, podemos cambiar o tamaño nosas listas na Moscova desde o noso ordenador non dependen de indexación, pero si na conexión entre o uso de punteiros para almacena-los. 

Listas No entanto, unha desvantaxe do ligadas é que, ao contrario dunha matriz estática, o ordenador non pode simplemente saltar para o medio da lista. Dende que o ordenador ten que visitar cada nó na lista ligada para chegar ó seguinte, que vai levar máis tempo para atopar un nodo específico do que sería nun array. Para percorrer a lista enteira leva un tempo proporcional a lonxitude da lista, ou O (n) en notación asintótica. En media, alcanzando calquera nodo tamén leva un tempo proporcional a n. 

Agora, imos realmente escribir un código que traballa con listas ligadas. Imos dicir que queremos unha lista ligada de enteiros. Podemos representar un nó na nosa lista de novo como unha estrutura con dous campos, un valor enteiro chamado 'Val' e un punteiro próximo ao seguinte nodo da lista. Ben, parece bastante simple. 

Imos dicir que queremos escribir unha función que percorre a lista e imprime o valor almacenado no último nó da lista. Ben, iso significa que temos que percorrer todos os nodos da lista para atopar a última, pero a condición de que non está engadindo ou borrar nada, non queremos cambiar a estructura interna dos punteiros seguintes na lista. 

Entón, imos ter un punteiro especificamente para paso que chamaremos de "rastreador". Vai rastexaren a través de todos os elementos da lista seguindo a cadea de punteiros próximos. Todo o que temos almacenado é un punteiro para o apartado 1, ou "cabeza" da lista. Puntos de cabeza para o apartado 1. É o tipo de punteiro a nó. 

Para obter o apartado 1 real na lista, temos que dereference ese punteiro, pero antes de que poidamos cancelar a referencia de que é preciso comprobar o punteiro é nulo primeiro. Se é nulo, a lista está baleira, e debemos imprimir unha mensaxe que, porque a lista é baleira, non hai último nodo. Pero, imos dicir que a lista non é baleira. Se non é, entón debemos rastrexar toda a lista ata chegar ao último nodo da lista, e como podemos saber se nós estamos mirando para o último nó na lista? 

Ben, se punteiro próxima dun nodo é nulo, sabemos que estamos no final desde o último punteiro seguinte tería ningún no seguinte na lista para apuntar. É unha boa práctica para manter sempre punteiro preto do no pasado inicializar como nulo ter unha propiedade estandarizada que nos alerta cando chegamos ao fin da lista. 

Entón, se rastreador → seguinte é nulo, Lembre que a sintaxe frecha é un atallo para dereferencing un punteiro para unha estrutura, a continuación, acceder seu próximo campo equivalente ao incómodo: (* Rexistro). Seguinte. Unha vez que teñamos atopado o último nó, queremos imprimir rastreador → val, o valor do nodo actual que sabemos que é a última. En caso contrario, se non estamos aínda no último nodo na lista, temos que seguir adiante para o próximo nó na lista e comprobar que este é o último. Para iso, basta con facer o noso punteiro rastreador para apuntar para o próximo valor do nodo actual, é dicir, o no seguinte na lista. Isto faise axustar rastreador = rastreador → seguinte. A continuación, repetimos este proceso, con un lazo, por exemplo, ata atopar o último nodo. Así, por exemplo, se rastreador estaba apuntando á cabeza, imos definir rastreador para apuntar para rastreador → seguinte, que é o mesmo que o seguinte campo da alínea 1. Entón, agora o noso rastreador está a apuntar cara o apartado 2, e, de novo, repetir este con un ciclo, ata que teñamos atopado o último nó, isto é, onde punteiro preto do nodo está a apuntar cara null. E aí temos que, atopamos o último nó na lista, e para imprimir o seu valor, é só usar rastreador → val. 

O desprazamento non é tan malo, pero o que sobre a inserción? Imos dicir que queremos inserir un enteiro na posición 4 nunha lista de enteiros. Que se atopa entre os nodos de corrente 3 e 4. Unha vez máis, temos que percorrer a lista só para chegar ao elemento terceiro, aquel que está inserindo despois. Entón, creamos un punteiro rastreador de novo para percorrer a lista, comprobar que o noso punteiro cabeza é nulo, e se non é, apunta noso punteiro rastreador no nó de cabeza. Entón, estamos no primeiro elemento. Temos que ir para adiante dous elementos máis antes de que poidamos introducir, polo que podemos usar un loop int i = 1; i <3, i + + e en cada iteração do loop, avanzar noso punteiro rastreador fronte por un nodo comprobando o campo preto do nodo actual é nulo, e se non é, mover noso punteiro rastreador para o próximo nodo definíndose o igual ao punteiro preto do nodo actual. Así, desde que o noso circuíto para facelo, di dúas veces, chegamos ao apartado 3, e unha vez que o noso punteiro rastreador alcanzou o nó despois que queremos introducir o noso enteiro novo, como é que nós realmente a inserción? 

Ben, o noso novo enteiro debe ser inserida na lista como parte da súa estrutura propio no, unha vez que esta é realmente unha secuencia de nós. Entón, imos facer un novo punteiro para o nodo chamado "new_node ' e configure-lo para apuntar para a memoria que agora reservar sobre a pila para o propio nodo, ea cantidade de memoria que necesitamos reservar? Así, o tamaño dun nodo, e queremos establecer o seu campo val para o número enteiro que desexa inserir. Imos dicir, 6. Agora, o nodo contén o seu valor enteiro. É tamén unha boa práctica para iniciar seguinte campo novo nodo para apuntar para null, pero e agora? 

Temos que cambiar a estrutura interna da lista e os punteiros próximos contida existente da lista Nós 3 e 4. Unha vez que os punteiros próximos determinar a orde da lista, E xa que estamos introducindo o noso novo no a dereita no medio da lista, pode ser un pouco complicado. Isto porque, lembre, o noso ordenador só sabe a localización de nós na lista por mor dos punteiros próximos almacenados nos nos anteriores. Entón, se algunha vez perdeu a noción de calquera destes lugares, dicir cambiando un dos punteiros próximos na nosa lista, por exemplo, dicir que cambiou campo seguinte o apartado 3 é para apuntar a algún nó aquí. Nós estariamos fóra de sorte, porque non faría Ten algunha idea de onde atopar o resto da lista, e iso é, obviamente, moi malo. Entón, nós temos que ter moito coidado sobre a orde en que manipular os punteiros próximas durante a inserción. 

Entón, para simplificar, imos dicir que nosos primeiros catro nós son denominados A, B, C, e D, as frechas que representan a cadea de punteiros que conectan os nodos. Entón, necesitamos introducir noso novo nodo entre os nós C e D. É fundamental facelo na orde correcta, e eu vou amosar-lle por que. 

Imos ollar para a forma incorrecta de facelo primeiro. Ola, sabemos que o novo nó ten que vir despois C, entón imos definir punteiro preto do C para apuntar para new_node. Todo ben, parece todo ben, só temos que rematar agora por facendo punto o novo nó do punteiro ao lado D, pero espera, como podemos facer iso? O único que podería dicir onde era D, o punteiro próximo foi previamente almacenado en C, pero nós só reescreveu o punteiro para apuntar para o novo nodo, así xa non temos ningún pista onde D é na memoria, e nós perdemos o resto da lista. Non é bo en todo. 

Entón, como imos facelo certo? En primeiro lugar, apuntar punteiro seguinte, o novo nó no D. Agora, os punteiros tanto o novo nó e C do próximo están apuntando para o mesmo nodo, D, pero iso é bo. Agora podemos apuntar punteiro próximo ao C o novo nodo. Entón, nós fixemos iso sen perder os datos. No código, C é o nó actual que a travesía punteiro rastreador está a apuntar, e D é representada polo nodo apuntado polo campo seguinte do nodo actual, ou rastreador → seguinte. Entón, primeiro definir punteiro seguinte, o novo nodo para apuntar para rastreador → seguinte, do mesmo xeito que dixo punteiro próxima new_node debería apuntar D na figura. Entón, podemos definir punteiro preto do nodo actual para o noso novo nodo, así como nós tivo que esperar ata o punto C para new_node no deseño. Agora todo está en orde, e non perdemos o control de todos os datos, e fomos capaces de só furar o noso novo nó no medio da lista sen reconstruír a cousa toda ou incluso desprazando todos os elementos do xeito que tería que ter unha matriz de lonxitude fixa. 

Entón, listas ligadas son un básico, pero importante, estrutura de datos dinámica que teñen vantaxes e inconvenientes en comparación coas matrices e outras estruturas de datos, e, como é frecuentemente o caso en ciencia da computación, é importante saber cando usar cada ferramenta, para que poida elixir a ferramenta certa para o traballo correcto. 

Para máis práctica, proba escribir funcións para eliminar nós unha lista ligada - Lembre-se de ter coidado coa orde en que reorganizar os punteiros próximos para garantir que non perda unha peza da súa lista - ou unha función para contar os nós nunha lista ligada, ou un divertimento, para inverter a orde de todos os nós nunha lista ligada. 

O meu nome é Jackson Steinkamp, ​​este é CS50.