Listas ligadas en Java paso a paso y en Español

En este post explicaremos paso a paso como crear una lista ligada en Java, como sabemos existe un api llamado Collections api que se encuentra en el paquete java.util, nosotros no lo utilizaremos y crearemos una desde cero para entender como funciona.

Una lista ligada es un conjunto dinámico de elementos de cualquier tipo almacenados en memoria, estos pueden ser:

  • Des ordenadas
  • Ordenadas
  • Con elementos únicos
  • Con elementos duplicados
  • Simplemente ligadas
  • Doblemente ligadas

En este post explicaremos como crear una lista simplemente ligada.

Creando la clase Nodo

La clase nodo será la clase base y será utilizada para representar cada elemento en la lista.

/**
 * @author raidentrance
 *
 */
public class Node {
	private Integer value;
	private Node next;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}

}

Como se puede observar cada elemento de la lista contendrá dos atributos:

  • Integer value : Almacena el valor contenido en el elemento
  • Node next : Almacena una referencia al nodo siguiente de la lista

Las listas se llaman ligadas porque cada elemento contiene una referencia al nodo siguiente como se muestra en la siguiente imagen :

linkedlist

Creando la lista ligada

Una vez que definimos la estructura que tendrá el nodo el siguiente paso será crear una clase que represente las acciones disponibles sobre esa lista, en este caso crearemos una clase llamada LinkedList.


import java.util.Optional;

/**
 * @author raidentrance
 *
 */
public class LinkedList {
	private Node head;

	public void append(Integer value) {
		if (head == null) {
			head = new Node(value);
			return;
		}
		Optional<Node> lastNode = getLastNode();
		Node node = lastNode.get();
		node.setNext(new Node(value));
	}

	public void print() {
		for (Node i = head; i != null; i = i.getNext()) {
			System.out.print(i.getValue() + "\t");
		}
		System.out.println();
	}

	public Optional<Node> getLastNode() {
		if (head != null) {
			Node current = head;
			while (current.getNext() != null) {
				current = current.getNext();
			}
			return Optional.of(current);
		} else {
			return Optional.empty();
		}
	}

	public void delete(Integer value) {
		System.out.printf("Deleting %d \n", value);
		if (head == null) {
			return;
		}
		if (head.getValue() == value) {
			head = head.getNext();
			return;
		}
		Node current = head;
		while (current != null && current.getNext() != null) {
			if (current.getNext().getValue() == value) {
				current.setNext(current.getNext().getNext());
			}
			current = current.getNext();
		}

	}
}

Como se puede observar, las acciones soportadas en esta clase son las siguientes:

  • void append(Integer value) : Agrega un valor al final de la lista

  • void print() : Imprime el contenido de la lista

  • Optional getLastNode() : Devuelve una referencia al nodo final de la lista en caso de existir

  • void delete(Integer value) : Borra el o los elementos que contengan el valor pasado como parámetro de la lista

Probando la lista

Una vez que determinamos los nodos y las disponibles en la lista el siguiente paso será probarla para esto crearemos la siguiente clase:


/**
 * @author raidentrance
 *
 */
public class TestLinkedList {
	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		list.append(10);
		list.append(11);
		list.append(12);
		list.append(13);
		list.append(14);
		list.append(12);
		list.print();
		list.delete(14);
		list.print();
		list.delete(10);
		list.print();
		list.delete(12);
		list.print();
	}

}

Salida:

10	11	12	13	14	12
Deleting 14
10	11	12	13	12
Deleting 10
11	12	13	12
Deleting 12
11	13

En siguientes posts se explicará como utilizar una lista doblemente ligada así como otras estructuras de datos, Si te gusta el contenido compártelo y no olvides seguirnos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Anuncios

3 Comentarios »

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s