Tutorial listas enlazadas

Clase adicional 9
Temas Listas enlazadas Árboles Problemas de la clase adicional Ejercicios de diseño

Listas enlazadas
Previamente en este curso, ya habrá trabajado con dos de las estructuras de datos más básicas: los arrays y los vectores. En esta clase adicional, estudiaremos estructuras de datos más avanzadas: las listas enlazadas, los árboles y los grafos. Aunque los arrays son una buenasolución para almacenar un número de conjunto del mismo tipo de objetos, y aunque los vectores nos permiten controlar dinámicamente el tamaño del espacio de almacenamiento, ambas estructuras de datos tienen un inconveniente importante. Si queremos insertar o eliminar una entrada, es preciso desplazar hacia arriba o hacia abajo todos los elementos situados “debajo” de dicha entrada copiándolos enlos elementos adyacentes. A pesar de que es posible salvar esta dificultad (por ejemplo, estableciendo los elementos no utilizados en null), la cantidad de memoria utilizada en un sistema de estas características podría ser ingente y sería necesario modificar el código para manipular todos los espacios vacíos. Un método más eficaz para almacenar los datos que puedan requerir numerosas adiciones yeliminaciones es la lista enlazada. Definición Una lista enlazada es una serie de objetos que “saben" dónde se encuentra el siguiente miembro de la lista en la memoria del ordenador. El último miembro de la lista suele indicar que el miembro siguiente es un "null". Para lograrlo, cada objeto de la lista debe disponer de un miembro que pueda almacenar la ubicación en la memoria del siguiente objetode la lista. Este tipo de listas son listas enlazadas simples, ya que el código puede desplazarse en la lista en una sola dirección. También existen listas enlazadas dobles. Una referencia al objeto de la lista suele indicar el comienzo de la misma. Operaciones en listas enlazadas Algunas de las operaciones básicas que pueden realizarse en una lista enlazada son: Crear una lista Buscar unelemento en la lista Insertar un elemento al final de la lista Eliminar una elemento de la lista

Implementación en Java

El siguiente código es una implementación sencilla de una lista enlazada: (NOTA: para resumir, el código para buscar un elemento en la lista se incluye en el método de eliminación). Aquí está la clase que declara los datos básicos en cada enlace de la lista: class Check { privatestatic int totalChecks=0; // una variable para el seguimiento de todas las comprobaciones private int checkNumber; private double checkAmount; private Check nextCheck; // referencia a la siguiente comprobación de la lista public Check ( double amount ) { checkNumber = ++totalChecks; checkAmount = amount; nextCheck = null; } public static int getTotalChecks() { return totalChecks; } public intgetCheckNumber() { return checkNumber; } public Check getNextCheck() { return nextCheck; } public void setNextCheck(Check c) { nextCheck = c; } public void print() { System.out.println("Número de comprobación: #" + checkNumber + "; Check Amount : $"+ checkAmount); } } Éste es el código que proporciona los operadores de la lista (añadir, eliminar, está vacío, etc.) Se incluye una excepción comoejemplo en el método deleteChecks. Sería mejor que el código comprobase los null antes de buscar otro enlace, y no que se estancase en la excepción para tratar la excepción NullPointerException que se genera al intentar leer un objeto que no existe. class ListOfChecks { // crea una referencia a nuestra lista private Check head; public ListOfChecks() { // establece la referencia a la lista en null, yaque la lista // no tiene ningún miembro Check head = null; } public boolean isEmpty() { return (head == null); // si la lista está vacía, devolver true } public boolean addToEnd ( double amount ) { if ( isEmpty() ) // si la lista está vacía, comenzar una nueva

... }

head = new Check(amount); else { // "Recorrer la lista" hasta llegar al final (esto es, cuando la siguiente comprobación es...