Sin duda una de las partes mas emocionantes cuando programamos es la parte de la algoritmia donde tenemos que usar la mente para resolver problemas que se escuchan fácil pero a la hora de programarlas es otra cosa.
En esta ocasión hablare un poco de las Listas ligadas y de las variantes que existen entre ellas.
Podríamos definir a una lista ligada como un colección de elementos que están enlazados entre si y que cada nodo contiene un valor y las hacia otros nodos.
Lista Ligada
Lista ligada como tal es la variante mas simple que existe pues en esta estructura de datos tenemos un conjunto de nodos que están enlazados solo con el nodo siguiente de tal forma que si queremos recorrer la colección lo haremos del primero hasta el último pero no podremos regresar.
Como podemos apreciar una lista es un conjunto de nodos que tiene un Objeto de valor para nosotros pero ademas tiene una referencia hacia el siguiente nodo.
Lista Ligada Circular
Esta es una variante de la lista ligada la cual se comporta igual que la lista ligada normal pero a demas el último nodo esta ligado al primero por lo cual una vez que llegamos al último nodo podemos seguir avanzado en la estructura volviendo a empezar.
En la imagen podemos observar que todos los nodos están conectados con el nodo siguiente pero a demas el último nodo esta conectado con el primero.
Lista Doblemente Ligada
Esta es una variante de la lista ligada que nos permite que los nodos tengan una referencia hacia el nodo siguiente como el anterior pero a demas tenga un referencia hacia el nodo anterior, de esta forma cuando recorremos la estructura podemos ir hacia a delante pero también podemos regresar si lo decaemos.
Como vemos cada nodo tiene dos referencias de las cuales una apunta al nodo anterior y la segunda al nodo siguiente a excepción del primer y último nodo, puesto no existen mas nodos hacia donde referencia.
Lista Doblemente Ligada Circular
Esta estructura es similar a la Lista Doblemente Ligada, sin embargo el último nodo esta ligado con el primero.
En esta imagen podemos apreciar que cada nodo tiene una referencia hacia el nodo anterior y el nodo siguiente pero a demas podemos observar que el último nodo de la estructura esta conectado con el primero y el primero con el último.
Por ultimo explico de forma general como se debe agregar un nuevo elemento a la estructura:
Como podemos observar en la imagen, cuando un nuevo nodo(Nodo 3) entra en la estructura el elemento anterior(Nodo2) cambia si referencia del nodo siguiente al nuevo nodo, y el nuevo nodo hace referencia al nodo siguiente(Nodo 4) de esta forma la lista sigue siendo ligada pero a demas respeta el orden en el cual fue diseñada.
En el caso de eliminar un nodo el procedimiento es muy similar, ya que en vez de agregar un nodo lo quitamos pero antes de quitarlo tenemos que rescatar el nodo siguiente del nodo a eliminar y asignárselo al nodo anterior.
Por ultimo les comparto un fragmento de código que ilustra mejor la estructura de cada nodo:
Para las listas ligadas tendríamos un nodo de la siguiente manera:
Como vemos tiene un atributo para guardar el valor y un Objeto Nodo que apunta al siguiente nodo.
Y para las listas doblemente ligadas tendríamos la siguiente clase.
Esta es muy similar a la anterior sin embargo esta tiene una referencia al nodo anterior lo que le permite navegar hacia adelante y atrás.
Con esto finalizo y espero que esta explicación le aya servido de utilidad.
*Recuerda que si te gusto este artículo, compartelo y suscribete al blog para que recibas todas las actualizaciones directamente sobre tu correo electrónico.
Cual es la ventaja / desventaja de usar una lista ligada sobre un arreglo convencional (consumo de memoria, velocidad de acceso, uso de cache del cpu? Que clases proporciona proporciona el api std de java para no reinventar la rueda?
En realidad usar un arreglo siempre es mucho mas efectivo ya que son estructuras nativas de java y el acceso es sumamente rápido, sin embargo las listas ligadas tiene una aplicación diferente a los arreglos ya que son estructuras dinámicas las cuales pueden crecer de tamaño a diferencia de los arreglos.
Es importante identificar para que las vas a utilizar. En lo general siempre es mas recomendable utilizar Arreglo donde sea posible.
Java tiene la clase LinkedList y te comparto su documentación para que le des una revisada y si tienes mas dudas con gusto las resolvemos.
http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
Tampoco hay que olvidar la finalidad y para que quieres usar la collecion.. Si tenemos que hacer muchas inserciones en la lista o muchos borrados, una lista (LinkedList) siempre sera mucho mas efectiva, porque nos olvidamos de desplazar los elementos (como seria el caso de un ArrayList). En cambio, si la lista se usa para consultas, y se hacen muchas consultas, es mucho mas rapido el acceso al array.
En que casos conviene usar o no listas ligadas?
Las listas ligadas son muy buena cuando requieres una colección ordenada, donde necesites borrar y agregar nuevos nodos en tiempo de ejecución.
Imagina el escenario en el que tienes un Arrar[10] y en cada posición tiene un valor, si quitas por ejemplo el valor de la posición 2 tendrás que recorrer el resto de lo valores una posición para que sigan ordenados, luego si agregar uno mas a los 10 que hay tendrás que crear un nuevo array pero esta vez de 11 posiciones lo que sera mas costoso que hacer una lista ligada la cual es dinámica y permite el crecimiento, eliminación y agregación de nuevos nodos sin ningún problema.
Saludos.
Hola, he estado revisando algunos de tus artículos y la verdad que están muy buenos, explicas de una manera muy sencilla los temas y lo haces de forma agradable, que dan ganas de continuar con la lectura, sin embargo, veo que tienes algunos errores ortográficos, no me lo tomes a mal, pero sería bueno que tengas un poco más de cuidado en eso, saludos.
Gracias por tu comentario, la verdad es que este articulo fue uno de mis primeros en redactar en el blog y desde entonces he mejorado gradualmente, todavía tengo errores, pero creo que he logrado mitigar los más grabes, te invito a que leas mis último artículo y me digas que opinas. saludos.
Buen artículo, muy ilustrativo y bien explicado, pero persisten los errores de ortografía, por ejemplo, en tu última respuesta empleas la palabra grave con B. Aún así muchas gracias por tu interés en compartir el conocimiento.
Juan
Si, es verdad, es un problema que he estado trabajando, para mejorado, pero aún me falta un largo camino, además, ese artículo es de los primeros, así que pues ya te darás una idea… 😭