|
Buscador
Secciones
Otras zonas
Foros
Ganamos
Registro
|
Inicio > Tutoriales > Lenguajes orientados a objeto > J2EE > Estructuras de Datos y Algoritmos en Java
Otro algoritmo común de las listas de enlace simples es el borrado de nodos. Al contrario que la insercción de nodos, sólo hay dos casos a considerar:
El siguiente listado representa el equivalente Java a los pseudocódigos de borrado anteriores:
// SLLDelDemo.java
class SLLDelDemo {
static class Node {
String name;
Node next;
}
public static void main (String [] args) {
// Build Figure 6's singly linked list (i.e., B A D C)
Node top = new Node ();
top.name = "C";
top.next = null;
Node temp = new Node ();
temp.name = "D";
temp.next = top;
top = temp;
temp = new Node ();
temp.name = "A";
temp.next = top;
top = temp;
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;
dump ("Initial singly-linked list", top);
// 1. Delete the first node
top = top.next;
dump ("After first node deletion", top);
// Put back B
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;
// 2. Delete any node but the first node
temp = top;
while (temp.name.equals ("A") == false)
temp = temp.next;
temp.next = temp.next.next;
dump ("After D node deletion", top);
}
static void dump (String msg, Node topNode) {
System.out.print (msg + " ");
while (topNode != null) {
System.out.print (topNode.name + " ");
topNode = topNode.next;
}
System.out.println ();
}
}
Cuando ejecute SLLDelDemo, observará la siguiente salida: Initial singly linked list B A D C After first node deletion A D C After D node deletion B A C
Después de estudiar SLLDelDemo, podría preguntarse qué sucede si asigna null al nodo referenciado por top: ¿el recolector de basura recogerá toda la lista? Para responder a esta cuestión, compile y ejecute el código del siguiente listado:
// GCDemo.java
class GCDemo {
static class Node {
String name;
Node next;
protected void finalize () throws Throwable {
System.out.println ("Finalizing " + name);
super.finalize ();
}
}
public static void main (String [] args) {
// Build Figure 6's singly linked list (i.e., B A D C)
Node top = new Node ();
top.name = "C";
top.next = null;
Node temp = new Node ();
temp.name = "D";
temp.next = top;
top = temp;
temp = new Node ();
temp.name = "A";
temp.next = top;
top = temp;
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;
dump ("Initial singly-linked list", top);
top = null;
temp = null;
for (int i = 0; i < 100; i++)
System.gc ();
}
static void dump (String msg, Node topNode) {
System.out.print (msg + " ");
while (topNode != null){
System.out.print (topNode.name + " ");
topNode = topNode.next;
}
System.out.println ();
}
}
GCDemo crea la misma lista de cuatro nodos que SLLDelDemo. Después de volcar los nodos a la salida estándar, GCDemo asigna null a top y a temp. Luego, GCDemo ejecuta System.gc (); hasta 100 veces. ¿Qué sucede después? Mire la salida (que he observado en mi plataforma Windows): Initial singly-linked list B A D C Finalizing C Finalizing D Finalizing A Finalizing B La salida revela que todos los nodos de la lista de enlace simple han sido finalizados (y recolectados). Como resultado, no tiene que preocuparse de poner a null todos los enlaces de una lista de enlace simple cuando se quiera deshacer de ella. (Podría necesitar tener que incrementar el número de ejecuciones de System.gc (); si su salida no incluye los mensajes de finalización.)
|
| Truco: |
|---|
| Piense en una lista doblemente enlazada como una pareja de listas de enlace simple que interconectan los mismos nodos. |
La inserción y borrado de nodos en una lista doblemente enlazada son operaciones comunes. Estas operaciones se realizan mediante algoritmos que se basan en los algoritmos de inserción y borrado de las listas de enlace simple (porque las listas doblemente enlazadas sólo son una pareja de listas de enlace simple que interconectan los mismos nodos).
El siguiente listado muestra la inserción de nodos para crear la lista de la figura anterior, el borrado de nodos ya que elimina el nodo B de la lista, y el movimiento por la lista en ambas direcciones:
Tutoriales
// DLLDemo.java
class DLLDemo {
static class Node {
String name;
Node next;
Node prev;
}
public static void main (String [] args) {
// Build a doubly linked list
Node topForward = new Node ();
topForward.name = "A";
Node temp = new Node ();
temp.name = "B";
Node topBackward = new Node ();
topBackward.name = "C";
topForward.next = temp;
temp.next = topBackward;
topBackward.next = null;
topBackward.prev = temp;
temp.prev = topForward;
topForward.prev = null;
// Dump forward singly linked list
System.out.print ("Forward singly-linked list: ");
temp = topForward;
while (temp != null){
System.out.print (temp.name);
temp = temp.next;
}
System.out.println ();
// Dump backward singly linked list
System.out.print ("Backward singly-linked list: ");
temp = topBackward;
while (temp != null){
System.out.print (temp.name);
temp = temp.prev;
}
System.out.println ();
// Reference node B
temp = topForward.next;
// Delete node B
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
// Dump forward singly linked list
System.out.print ("Forward singly-linked list (after deletion): ");
temp = topForward;
while (temp != null){
System.out.print (temp.name);
temp = temp.next;
}
System.out.println ();
// Dump backward singly linked list
System.out.print ("Backward singly-linked list (after deletion): ");
temp = topBackward;
while (temp != null){
System.out.print (temp.name);
temp = temp.prev;
}
System.out.println ();
}
}
Cuando se ejecuta, DLLDemo produce la siguiente salida:
Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA
Algoritmo de Inserción-OrdenadaAlgunas veces querrá crear una lista doblemente enlazada que organice el orden de sus nodos basándose en un campo no de enlace. Atravesar la lista doblemente enlazada en una dirección presenta esos nodos en orden ascendente, y atravsarla en en dirección contraria los presenta ordenados descedentemente. El algoritmo de ordenación de burbuja es inapropiado en este caso porque requiere índices de array. Por el contrario, inserción-ordenada construye una lista de enlace simple o una lista doblemente enlzada ordenadas por un campo no de enlace para identificar el punto de inserción de cada nuevo nodo. El siguiente litado demuestra el algoritmo de inserción-ordenada:
// InsSortDemo.java
class InsSortDemo {
// Note: To keep Employee simple, I've omitted various constructor and
// nonconstructor methods. In practice, such methods would be present.
static class Employee {
int empno;
String name;
Employee next;
Employee prev;
}
public static void main (String [] args) {
// Data for a doubly linked list of Employee objects. The lengths of
// the empnos and names arrays must agree.
int [] empnos = { 687, 325, 567, 100, 987, 654, 234 };
String [] names = { "April", "Joan", "Jack", "George", "Brian", "Sam", "Alice" };
Employee topForward = null;
Employee topBackward = null;
// Prime the doubly linked list by creating the first node.
topForward = new Employee ();
topForward.empno = empnos [0];
topForward.name = names [0];
topForward.next = null;
topForward.prev = null;
topBackward = topForward;
// Insert remaining Employee nodes (in ascending order -- via empno)
// into the doubly linked list.
for (int i = 1; i < empnos.length; i++) {
// Create and initialize a new Employee node.
Employee e = new Employee ();
e.empno = empnos [i];
e.name = names [i];
e.next = null;
e.prev = null;
// Locate the first Employee node whose empno is greater than
// the empno of the Employee node to be inserted.
Employee temp = topForward;
while (temp != null && temp.empno <= e.empno)
temp = temp.next;
// temp is either null (meaning that the Employee node must be
// appended) or not null (meaning that the Employee node must
// be inserted prior to the temp-referenced Employee node).
if (temp == null) {
topBackward.next = e; // Append new Employee node to
// forward singly linked list.
e.prev = topBackward; // Update backward singly linked
topBackward = e; // list as well.
}
else{
if (temp.prev == null) {
e.next = topForward; // Insert new Employee node at
topForward = e; // head of forward singly linked
// list.
temp.prev = e; // Update backward singly linked
// list as well.
}
else {
e.next = temp.prev.next; // Insert new Employee node
temp.prev.next = e; // after last Employee node
// whose empno is smaller in
// forward singly linked list.
e.prev = temp.prev; // Update backward
temp.prev = e; //singly linked list as well.
}
}
}
// Dump forward singly linked list (ascending order).
System.out.println ("Ascending order:\n");
Employee temp = topForward;
while (temp != null) {
System.out.println ("[" + temp.empno + ", " + temp.name + "] ");
temp = temp.next;
}
System.out.println ();
// Dump backward singly linked list (descending order).
System.out.println ("Descending order:\n");
temp = topBackward;
while (temp != null) {
System.out.println ("[" + temp.empno + ", " + temp.name + "] ");
temp = temp.prev;
}
System.out.println ();
}
}
InsSortDemo simplifica su operación creando primero un nodo Employee primario. Para el resto de nodos Employee, InsSortDemo localiza la posición de inserción apropiada basándose en el campo no de enlace empno, y luego inserta el Employee en esa posición. Cuando ejecute InsSortDemo, podrá observar la siguiente salida:
Ascending order: [100, George] [234, Alice] [325, Joan] [567, Jack] [654, Sam] [687, April] [987, Brian] Descending order: [987, Brian] [687, April] [654, Sam] [567, Jack] [325, Joan] [234, Alice] [100, George]
Tanto la inserción-ordenada como la ordenación de burbuja exhiben prácticamente el mismo rendimiento.
Lista de Enlace CircularEl campo de enlace del último nodo de una lista de enlace simple contiene un enlace nulo, ocurre lo mismo en los campos de enlace del primer y último elemento en ambas direcciones en las listas doblemente enlazadas. Supongamos que en vez de esto los últimos nodos contiene un enlace a los primeros nodos. En esta situacion, usted terminará con una lista de enlace circular, como se ve en la siguiente figura:
Las listas de enlace circular se utilizan con frecuencia en procesamiento repetitivo de nodos en un orden específico. Dichos nodos podrían representar conexiones de servidor, procesadores esperando una sección crítica, etc. Esta estructura de datos también sirve como base para una variante de una estructura de datos más compleja: la cola (que veremos más adeltante).
Listas Enlazadas frente a ArraysLas listas enlazadas tienen las siguiente ventajas sobre los arrays:
En contraste, los arrays ofrecen las siguiente ventajas sobre las listas enlazadas:
Las listas enlazadas son más apropiadas cuando se trabaja con datos dinámicos. En otras palabras, inserciones y borrados con frecuencia. Por el contrario, los arrays son más apropiados cuando los datos son estáticos (las inserciones y borrados son raras). De todas formas, no olvide que si se queda sin espacio cuando añade ítems a un array, debe crear un array más grande, copiar los datos del array original el nuevo array mayor y elimiar el original. Esto cuesta tiempo, lo que afecta especialmente al rendimiento si se hace repetidamente.
Mezclando una lista de enlace simple con un array uni-dimensional para acceder a los nodos mediante los índices del array no se consigue nada. Gastará más memoria, porque necesitará los elementos del array más los nodos, y tiempo, porque necesitará mover los ítems del array siempre que inserte o borre un nodo. Sin embargo, si es posible integrar el array con una lista enlazada para crear una estructura de datos útil (por ejemplo, las tablas hash).
 |
Leer comentarios (67) |
 |
Escribir comentario |
Puntuación: (51 votos) |
|
 |
Votar |
 |
Recomendar este tutorial |
 |
Estadísticas |
Copyright © 1999-2007
Programación en castellano.
Todos los derechos reservados.
Formulario de Contacto -
Datos legales -
Publicidad
Mantenida por: Claudio y
Dani.
Hospedaje web y servidores dedicados linux por Ferca Network
red internet: jugar gratis | amor | navidad 2009 | registro de dominios |
servidores dedicados
más internet: comprar | gratis | posicionamiento en buscadores | decoración libre | gifs animados