[Powered by Google Translate] En la programación, a menudo necesitamos para representar listas de valores, tales como los nombres de los estudiantes de una sección o sus puntuaciones en la última prueba. 

En el lenguaje C, declaró matrices pueden utilizarse para almacenar listas. Es fácil enumerar los elementos de una lista almacenados en una matriz, y si usted necesita para acceder a o modificar el elemento de la lista ith por algún índice arbitrario I, que se puede hacer en un tiempo constante, pero las matrices tienen desventajas, también. 

Cuando les declaro, estamos obligados a decir desde el principio lo grandes que son, es decir, cuántos elementos se pueden almacenar y lo grande que estos elementos son, que se determina por su tipo. Por ejemplo, arreglo de int (10) Puede almacenar 10 elementos que tienen el tamaño de un int. 

No podemos cambiar el tamaño de una matriz después de la declaración. Tenemos que hacer una nueva matriz si queremos almacenar más elementos. La razón de esta limitación que existe es que nuestro programa almacena toda la matriz como un trozo contiguo de memoria. Decir esto es el buffer donde se almacena en nuestra matriz. Puede haber otras variables situado justo al lado de la matriz en la memoria, por lo que no puede sólo que la matriz más grande. 

A veces nos gustaría que el comercio de la matriz rápida velocidad de acceso a datos para un poco más de flexibilidad. Introduzca la lista enlazada, otra estructura de datos básicos usted podría no ser tan familiarizados. En un nivel alto, una lista enlazada almacena los datos en una secuencia de nodos que están conectados entre sí con enlaces, por lo tanto "lista enlazada. 'el nombre Como veremos, esta diferencia en el diseño conduce a distintas ventajas y desventajas de una matriz. 

Aquí hay un código C para una lista muy simple enlazada de números enteros. Se puede ver que hemos representado a cada nodo en la lista como una estructura que contiene dos cosas, un entero para almacenar llamado 'val' y un enlace para el nodo siguiente en la lista que representamos como un puntero llamado 'next'. De esta manera, podemos seguir la lista entera con sólo un único puntero al nodo primero, y luego podemos seguir los siguientes consejos para el segundo nodo, al nodo tercero, para el cuarto nodo, y así sucesivamente, hasta llegar a la final de la lista. 

Usted puede ser capaz de ver una ventaja que esto tiene sobre la estructura matriz estática - con una lista enlazada, no necesitamos una gran parte de la memoria por completo. El nodo 1 de la lista podría vivir en este lugar en la memoria, y el segundo nodo podría ser todo el camino hasta aquí. Podemos llegar a todos los nodos no importa donde en la memoria son, porque a partir de la primera nodo, el puntero siguiente de cada nodo nos dice exactamente dónde ir después. 

Además, no tienes que decir por adelantado lo grande que una lista enlazada será el camino que hacemos con arrays estáticos, ya que podemos seguir añadiendo nodos a una lista siempre y cuando no hay espacio en algún lugar de la memoria de los nuevos nodos. Por lo tanto, las listas enlazadas son fáciles de cambiar el tamaño de forma dinámica. Digamos, más tarde en el programa tenemos que añadir más nodos a nuestra lista. Para insertar un nuevo nodo en la lista sobre la marcha, todo lo que tenemos que hacer es asignar memoria para ese nodo, plop en el valor de los datos, y luego colocarlo donde queramos mediante el ajuste de los indicadores apropiados. 

Por ejemplo, si quisiéramos poner un nodo en el medio los nodos 2 y 3 de la lista,  no tendríamos que mover los nodos segundo o tercero en absoluto. Digamos que vas a insertar este nodo rojo. Todo lo que tendría que hacer es configurar puntero siguiente del nuevo nodo para que apunte al nodo tercera y luego volver a colocar el puntero siguiente nodo de segundo para que apunte a nuestro nuevo nodo. Por lo tanto, podemos cambiar el tamaño de nuestras listas sobre la marcha ya que nuestro equipo no depende de la indexación, sino más bien en vincular el uso de punteros para almacenarlos. 

Listas Sin embargo, una desventaja de vinculados es que, a diferencia de una matriz estática, el ordenador no sólo puede saltar a la mitad de la lista. Dado que el equipo tiene que visitar cada nodo en la lista enlazada para llegar a la siguiente, que va a tomar más tiempo para encontrar un nodo particular lo que lo haría en una matriz. Para recorrer toda la lista toma tiempo proporcional a la longitud de la lista, o O (n) en notación asintótica. En promedio, alcanzando cualquier nodo También se necesita tiempo proporcional a n. 

Ahora, vamos a realmente escribir código que trabaja con listas enlazadas. Digamos que queremos una lista enlazada de enteros. Podemos representar un nodo en la lista de nuevo como una estructura con dos campos, un valor entero llamado 'val' y un puntero próximo al siguiente nodo de la lista. Bueno, parece bastante simple. 

Supongamos que queremos escribir una función que recorre la lista e imprime el valor almacenado en el último nodo de la lista. Bueno, eso significa que tendremos que recorrer todos los nodos de la lista para encontrar la última, pero ya no estamos añadiendo o borrar nada, no queremos cambiar la estructura interna de los punteros siguientes en la lista. 

Por lo tanto, vamos a necesitar un puntero específicamente para traversal que llamaremos "crawler". Se arrastran a través de todos los elementos de la lista siguiendo la cadena de punteros próximos. Todos hemos almacenado es un puntero al nodo primero, o "cabeza" de la lista. Puntos de la cabeza a la primera nodo. Es de tipo puntero a nodo. 

Para obtener la actual primera nodo en la lista, tenemos que eliminar la referencia este indicador, pero antes de que podamos deferenciarlo, tenemos que comprobar si el puntero es nulo en primer lugar. Si es nulo, la lista está vacía, y debemos imprimir un mensaje que, debido a que la lista está vacía, no hay último nodo. Pero, supongamos que la lista no está vacía. Si no es así, entonces tenemos que gatear por toda la lista hasta llegar al último nodo de la lista, y ¿cómo podemos saber si estamos ante el último nodo en la lista? 

Bueno, si el puntero siguiente de un nodo es nulo, sabemos que estamos en el final desde el siguiente puntero última no tendría ningún nodo siguiente en la lista para apuntar. Es una buena práctica para mantener siempre puntero siguiente del último nodo de inicializan a null tener una propiedad estándar que nos avisa cuando hemos llegado al final de la lista. 

Por lo tanto, si crawler → siguiente es nulo, recordar que la sintaxis de flecha es un acceso directo para eliminar la referencia un puntero a una estructura, a continuación, acceder a su siguiente campo equivalente al torpe: (* Crawler). Siguiente. Una vez que hayas encontrado el último nodo, queremos imprimir crawler → val, el valor en el nodo actual que sabemos que es la última. De lo contrario, si no estamos todavía en el último nodo de la lista, tenemos que pasar a la siguiente nodo en la lista y comprobar si ese es el último. Para ello, se acaba de establecer nuestro puntero sobre orugas para apuntar al siguiente valor del nodo actual, es decir, el nodo siguiente en la lista. Esto se hace mediante el establecimiento crawler = crawler → siguiente. Luego repetimos este proceso, con un lazo por ejemplo, hasta encontrar el último nodo. Así, por ejemplo, si rastreador estaba apuntando a la cabeza, nos propusimos rastreador para que apunte a orugas → siguiente, que es el mismo que el campo próximo de la primera nodo. Así que, ahora que nuestro rastreador está apuntando al nodo 2, y, de nuevo, se repite esto con un bucle, hasta que hayamos encontrado el último nodo, es decir, donde puntero siguiente del nodo apunta a null. Y ahí lo tenemos, hemos encontrado el último nodo de la lista, y la impresión de su valor, sólo tiene que utilizar crawler → val. 

Atravesando no es tan malo, pero ¿qué pasa con la inserción? Digamos que queremos insertar un número entero en la 4 ª posición en una lista de números enteros. Que está entre los nodos actuales tercero y cuarto. Una vez más, tenemos que recorrer la lista sólo para llegar a la tercera parte, la que estamos insertando después. Así, creamos un puntero rastreador de nuevo para recorrer la lista, comprobar si nuestra cabeza puntero es nulo, y si no lo es, apuntar con el puntero sobre orugas en el nodo principal. Por lo tanto, estamos en el elemento primero. Tenemos que ir hacia adelante 2 elementos más antes de que podamos insertar, por lo que podemos utilizar un bucle for int i = 1; i <3; i + + y en cada iteración del bucle, avanzar en el puntero sobre orugas presentadas por un nodo comprobando si el campo próximo del nodo actual es nula, y si no es así, mover nuestro rastreador puntero al siguiente nodo fijándolo igual al siguiente puntero del nodo actual. Por lo tanto, desde nuestro bucle para hacer eso, dice dos veces, hemos llegado al nodo 3, y una vez que nuestro puntero rastreador ha alcanzado el nodo después de que queremos insertar nuestro nuevo entero, ¿cómo es en realidad la inserción? 

Pues bien, nuestro nuevo entero tiene que ser insertado en la lista como parte de su propia estructura de nodo, ya que esto es realmente una secuencia de nodos. Por lo tanto, vamos a hacer un nuevo puntero al nodo llamado 'new_node,' y configurarlo para que apunte a la memoria que ahora asignar en el montón para el nodo en sí, y la cantidad de memoria tenemos que asignar? Pues bien, el tamaño de un nodo, y queremos establecer su campo val al entero que queremos insertar. Digamos, 6. Ahora, el nodo contiene nuestro valor entero. También es una buena práctica para inicializar campo próximo del nuevo nodo para apuntar a null, pero ¿ahora qué? 

Hay que cambiar la estructura interna de la lista y los indicadores contenidos en los siguientes de la lista Los nodos 3 y 4. Dado que los punteros próximos determinar el orden de la lista, y ya que estamos introduciendo nuestro nuevo nodo a la derecha en el medio de la lista, que puede ser un poco complicado. Esto es porque, recuerde, nuestro equipo sólo conoce la ubicación de los nodos en la lista porque de los punteros próximos almacenados en los nodos anteriores. Por lo tanto, si alguna vez perdido el rastro de ninguno de estos lugares, dicen que al cambiar uno de los punteros siguientes en la lista, Por ejemplo, digamos que cambiamos campo siguiente nodo de la tercera de para que apunte a algún nodo por aquí. Nos gustaría estar fuera de suerte, ya que no lo haría Tiene alguna idea de dónde encontrar el resto de la lista, y eso es, obviamente, muy mal. Por lo tanto, tenemos que tener mucho cuidado con el fin de en el que manipulamos nuestros punteros próximos durante la inserción. 

Así que, para simplificar esto, vamos a decir que nuestros primeros 4 nodos se denominan A, B, C, y D, con las flechas que representan la cadena de punteros que conectan los nodos. Por lo tanto, tenemos que insertar nuestro nuevo nodo entre los nodos C y D. Es muy importante hacerlo en el orden correcto, y yo te mostraré por qué. 

Echemos un vistazo a la forma incorrecta de hacerlo en primer lugar. Hey, sabemos que el nuevo nodo tiene que venir a la derecha después de C, así que vamos a establecer el puntero próximo C para que apunte a new_node. De acuerdo, parece estar bien, sólo tenemos que terminar ahora por hacer punto del nuevo nodo puntero próximo a D, pero espera, ¿cómo podemos hacer esto? Lo único que nos puede decir donde D es, fue el siguiente puntero almacenado previamente en C, pero nos volvió a escribir ese puntero para que apunte al nuevo nodo, por lo que ya no tenemos ni idea de donde D es en la memoria, y hemos perdido el resto de la lista. No es bueno en absoluto. 

Así que, ¿cómo podemos hacer esto bien? En primer lugar, señalar puntero siguiente del nuevo nodo a D. Ahora, tanto el nuevo nodo y la de C próximos punteros apuntan hacia el mismo nodo, D, pero eso está bien. Ahora podemos señalar siguiente puntero de C en el nuevo nodo. Por lo tanto, hemos hecho esto sin perder ningún dato. En el código, C es el nodo actual que el recorrido puntero rastreador hace referencia, y D está representado por el nodo al que apunta el campo siguiente nodo actual, o rastreador → siguiente. Así, en primer lugar establecer el puntero siguiente del nuevo nodo para que apunte a orugas → siguiente, de la misma manera que dijimos puntero próximo new_node deben tener por apuntar a D en la ilustración. Entonces, podemos establecer el puntero siguiente del nodo actual a nuestro nuevo nodo, del mismo modo que tuvo que esperar al punto C new_node en el dibujo. Ahora todo está en orden, y no perdió realizar un seguimiento de los datos, y fuimos capaces de simplemente pegarse nuestro nuevo nodo en el medio de la lista sin reconstruir toda la cosa, o incluso cambiando los elementos la forma en que se han tenido que con una matriz de longitud fija. 

Por lo tanto, las listas enlazadas son un básico, pero importante, la estructura de datos dinámica que tienen ventajas y desventajas en comparación con las matrices y otras estructuras de datos, y como es a menudo el caso en informática, es importante saber cuando usar cada herramienta, para que pueda elegir la herramienta adecuada para el trabajo correcto. 

Si desea practicar más, intente escribir funciones para eliminar nodos de una lista enlazada - recuerde tener cuidado con el orden en el que se reorganizan los punteros siguientes para asegurarse de que no pierda una buena parte de su lista - o una función para contar los nodos en una lista enlazada, o una diversión, para invertir el orden de todos los nodos de una lista enlazada. 

Mi nombre es Jackson Steinkamp, ​​esto es CS50.