Listas Enlazadas#
Recuerden que estas estructuras se suelen colocar en una clase mayor de Java llamada Collection
Figura 27 Here is my figure caption!#
Listas Simples Enlazadas con Nodos#
Una lista simple enlazada es una estructura de datos lineal formada por nodos, donde cada nodo tiene un dato y una referencia al siguiente nodo de la lista.
Figura 28 Here is my figure caption!#
Figura 29 Here is my figure caption!#
Hay una clase de java ya implementada llamada LinkedList.
Figura 30 Here is my figure caption!#
Implementación en Java#
public class Nodo {
int data; // Dato almacenado en el nodo
Nodo siguiente; // Referencia al siguiente nodo
public Nodo(int data) {
this.data = data;
this.siguiente = null; // Inicialmente, no tiene un nodo siguiente
}
}
public class ListaSimpleEnlazada {
private Nodo cabeza; // Primer nodo de la lista
public ListaSimpleEnlazada() {
cabeza = null; // La lista comienza vacía
}
// Método para agregar un nodo al final de la lista
public void agregar(int data) {
Nodo nuevoNodo = new Nodo(data);
if (cabeza == null) {
cabeza = nuevoNodo; // Si la lista está vacía, el nuevo nodo es la cabeza
}
else {
Nodo temp = cabeza;
while (temp.siguiente != null) {
temp = temp.siguiente; // Avanza al último nodo
}
temp.siguiente = nuevoNodo; // Se enlaza el nuevo nodo al final
}
}
// Método para imprimir la lista
public void imprimir() {
Nodo temp = cabeza;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.siguiente;
}
System.out.println("null");
}
public static void main(String[] args) {
ListaSimpleEnlazada lista = new ListaSimpleEnlazada();
lista.agregar(10);
lista.agregar(20);
lista.agregar(30);
lista.imprimir(); // Imprime: 10 -> 20 -> 30 -> null
}
}
// probar clase aquí
Nodos en Listas Doblemente Enlazadas#
Una lista doblemente enlazada es una estructura en la que cada nodo tiene dos referencias:
Una referencia al siguiente nodo.
Una referencia al nodo anterior.
Esto permite recorrer la lista en ambas direcciones.
Figura 31 Here is my figure caption!#
Implementación en Java#
class NodoDoble {
int data;
NodoDoble siguiente;
NodoDoble anterior;
public NodoDoble(int data) {
this.data = data;
this.siguiente = null;
this.anterior = null;
}
}
public class ListaDobleEnlazada {
private NodoDoble cabeza;
public ListaDobleEnlazada() {
cabeza = null;
}
// Método para agregar un nodo al final de la lista
public void agregar(int data) {
NodoDoble nuevoNodo = new NodoDoble(data);
if (cabeza == null) {
cabeza = nuevoNodo;
} else {
NodoDoble temp = cabeza;
while (temp.siguiente != null) {
temp = temp.siguiente;
}
temp.siguiente = nuevoNodo;
nuevoNodo.anterior = temp; // El nuevo nodo apunta al anterior
}
}
// Método para imprimir la lista de forma directa
public void imprimirDirecto() {
NodoDoble temp = cabeza;
while (temp != null) {
System.out.print(temp.data + " <-> ");
temp = temp.siguiente;
}
System.out.println("null");
}
// Método para imprimir la lista de forma inversa
public void imprimirInverso() {
if (cabeza == null) return;
NodoDoble temp = cabeza;
while (temp.siguiente != null) {
temp = temp.siguiente; // Avanza al último nodo
}
while (temp != null) {
System.out.print(temp.data + " <-> ");
temp = temp.anterior; // Retrocede en la lista
}
System.out.println("null");
}
public static void main(String[] args) {
ListaDobleEnlazada lista = new ListaDobleEnlazada();
lista.agregar(10);
lista.agregar(20);
lista.agregar(30);
lista.imprimirDirecto(); // Imprime: 10 <-> 20 <-> 30 <-> null
lista.imprimirInverso(); // Imprime: 30 <-> 20 <-> 10 <-> null
}
}
// probar clases y métodos aquí
Nodos en Grafos#
Un grafo es una estructura de datos que consiste en nodos (llamados vértices) y enlaces entre ellos (aristas). Los grafos pueden ser dirigidos o no dirigidos, dependiendo de si las conexiones entre los nodos tienen una dirección.
En un grafo:
Los nodos representan entidades.
Las aristas representan las relaciones entre estas entidades.
Implementación básica de un grafo usando nodos#
import java.util.ArrayList;
import java.util.List;
class NodoGrafo {
int data;
List<NodoGrafo> vecinos; // Lista de nodos vecinos
public NodoGrafo(int data) {
this.data = data;
vecinos = new ArrayList<>();
}
// Método para agregar una arista (relación) entre este nodo y otro
public void agregarVecino(NodoGrafo vecino) {
vecinos.add(vecino);
}
}
public class Grafo {
private List<NodoGrafo> nodos;
public Grafo() {
nodos = new ArrayList<>();
}
// Método para agregar un nodo al grafo
public void agregarNodo(int data) {
NodoGrafo nuevoNodo = new NodoGrafo(data);
nodos.add(nuevoNodo);
}
// Método para conectar dos nodos
public void conectarNodos(NodoGrafo nodo1, NodoGrafo nodo2) {
nodo1.agregarVecino(nodo2);
nodo2.agregarVecino(nodo1); // Grafo no dirigido
}
public static void main(String[] args) {
Grafo grafo = new Grafo();
NodoGrafo nodo1 = new NodoGrafo(1);
NodoGrafo nodo2 = new NodoGrafo(2);
NodoGrafo nodo3 = new NodoGrafo(3);
grafo.conectarNodos(nodo1, nodo2);
grafo.conectarNodos(nodo2, nodo3);
System.out.println("El nodo 1 está conectado con: " + nodo1.vecinos.size() + " nodo(s).");
System.out.println("El nodo 2 está conectado con: " + nodo2.vecinos.size() + " nodo(s).");
}
}
Enlazadas Circularmente#
Figura 32 Here is my figure caption!#
Ejercicio#
Taller 5
Implementen los códigos de nodos, listas simples y doblemente enlazadas de las tres referencias y la clase de LinkedList de java. Este taller se hace de a cuatro personas, cada uno elije un libro diferente y la idea es comparar los códigos.
La idea es que estos códigos son implementaciones más completas y robustas de lo que vimos en clase, clases con muchos métodos y una implementación optimizada.
No olviden que deben implementar los códigos y probarlos creando objetos y ejecutando sus métodos. Además deben presentar un documento en formato markdown donde se hable de la comparación entre las implementaciones: ventajas, desventajas, métodos, diferencias, etc.
Conclusiones#
Los nodos y las referencias son componentes fundamentales en la implementación de estructuras de datos como listas enlazadas, listas doblemente enlazadas y grafos. Al dominar estos conceptos, los estudiantes pueden implementar estructuras de datos más complejas y optimizadas, cruciales para la resolución eficiente de problemas en la programación. Las listas permiten manejar datos dinámicos, mientras que los grafos ofrecen una manera poderosa de modelar relaciones entre entidades.