Lista Doblemente Enlazada - Movimiento Bidireccional y Borrado Simple

Lista Doblemente Enlazada

Las listas de enlace simple restringen el movimiento por lo nodos a una sola dirección: no
puede atravesar una lista de enlace simple en dirección opuesta a menos que primero
utilice el algoritmo de inversión para invertir los enlaces de los nodos, lo que lleva
tiempo. Después de a tras versarlos en dirección opuesta, probablemente necesitará
repetir la inversión para restaurar el orden original, lo que lleva aún más tiempo. Un
segundo problema implica el borrado de nodos: no puede borrar un nodo arbitrario sin
acceder al predecesor del nodo. Estos problemas desaparecen cuando se utiliza una lista
doblemente enlazada.
Una lista doblemente enlazada es una lista enlazada de nodos, donde cada nodo tiene un
par de campos de enlace. Un campo de enlace permite atravesar la lista hacia adelante,
mientras que el otro permite atravesar la lista haca atrás. Para la dirección hacia adelante,
una variable de referencia contiene una referencia al primer nodo. Cada nodo se enlaza
con el siguiente mediante el campo de enlace next, excepto el último nodo, cuyo campo
de enlace next contiene null para indicar el final de la lista (en dirección hacia adelante).
De forma similar, para la dirección contraria, una variable de referencia contiene una
referencia al último nodo de la dirección normal (hacia adelante), lo que se interpreta
como el primer nodo. Cada nodo se enlaza con el anterior mediante el campo de enlace
previous, y el primer nodo de la dirección hacia adelante, contiene null en su campo
previous para indicar el fin de la lista. La siguiente figura representa una lista doblemente
enlazada de tres nodos, donde topForward referencia el primer nodo en la dirección hacia
adelante, y topBackward referencia el primero nodo la dirección inversa.

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:
// 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;
temp = temp.prev;
}


// 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;
temp = temp.next;
}


// Dump backward singly linked list

System.out.print ("Backward singly-linked list (after deletion): ");

temp = topBackward;
temp = temp.prev;
}
}
}

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-Ordenada

Algunas 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 a tras versarla en dirección
contraria los presenta ordenados descendentemente. 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 enlazada
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;
}


// 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;
}

}
}
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 Circular

El 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 situación, 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.

Listas Enlazadas frente a Arrays

Las listas enlazadas tienen las siguientes ventajas sobre los arrays:
No requieren memoria extra para soportar la expansión. Por el contrario, los arrays
requieren memoria extra si se necesita expandirlo (una vez que todos los elementos
tienen datos no se pueden añadir datos nuevos a un array).
Ofrecen una inserción/borrado de elementos más rápida que sus operaciones equivalentes
en los arrays. Sólo se tienen que actualizar los enlaces después de identificar la posición
de inserción/borrado. Desde la perspectiva de los arrays, la inserción de datos requiere el
movimiento de todos los otros datos del array para crear un elemento vacío. De forma
similar, el borrado de un dato existente requiere el movimiento de todos los otros datos
para eliminar el elemento vacío.
En contraste, los arrays ofrecen las siguientes ventajas sobre las listas enlazadas:
Los elementos de los arrays ocupan menos memoria que los nodos porque no requieren
campos de enlace.
Los arrays ofrecen un acceso más rápido a los datos, mediante índices basados en enteros.
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 eliminar
el original. Esto cuesta tiempo, lo que afecta especialmente al rendimiento si se hace
repetidamente.
Mezclando una lista de enlace simple con un array unidimensional 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.

Lista Doblemente Enlazada - Movimiento Bidireccional y Borrado Simple

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Viewers also liked

Viewers also liked (13)

Similar to Lista Doblemente Enlazada - Movimiento Bidireccional y Borrado Simple

Similar to Lista Doblemente Enlazada - Movimiento Bidireccional y Borrado Simple (20)

Recently uploaded

Recently uploaded (20)

Lista Doblemente Enlazada - Movimiento Bidireccional y Borrado Simple