Estructuras de datos – Listas ligadas

ListaLigadaAgregarSin 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.

Listas LigadasComo 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.

Listas Ligadas Circulares

 

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.

Listas Doblemente Ligadas

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.

Listas Doblemente Ligadas CircularesEn 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:

Listas Ligadas Agregar

 

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:

Listas Ligadas Node

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.

Listas Ligadas Nodo Doble

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.

 

Artículos relacionados

JPA – Resource Local transaction Resource Local es un tipo de transaccionalidad que soporta JPA que delegar la responsabilidad de las transacciones al programador, de esta manera, el ...
Patrón de Diseño Factory Esta entrada formara parte de un conjunto de entradas dedica específicamente a explicar los diferentes patrones de diseño que existe. El patrón de di...
Web Services con Java (JAX-WS) Los Web Services cada vez son más indispensable a la hora de construir aplicaciones, debido a que ya casi cualquier aplicación empresarial, requiere i...

Oscar Blancarte

Ideológico, Innovador y emprendedor, Padre, Tecnólogo y Autor, amante de la ciencia y la tecnología en todos sus colores y sabores. Arquitecto de software & Full Stack Developer con experiencia en la industria del desarrollo de software y la consultoría. Amante de la programación y el Ajedrez.

5 comentarios en “Estructuras de datos – Listas ligadas

  1. 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?

    1. 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

    1. 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.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *