Listas

Una lista está formada por un número variable de datos (elementos) de un mismo tipo, ordenados según una secuencia lineal. Cada elemento, salvo el primero, tiene un predecesor en la lista. Todos los elementos, salvo el último, tienen un sucesor. La lista es una estructura dinámica.
Podemos definir una lista como una estructura de datos formada por registros de, al menos, dos campos, en que uno de ellos contiene información que permite localizar al siguiente registro en la lista según una secuencia dada. La lista no es direccionable, tan sólo se puede recuperar un elemento accediendo previamente a los que le anteceden, y por tanto, en cada momento hay sólo un elemento en disposición de ser procesado.
Un tipo de lista especialmente importante es la pila o lista de LIFO, en que se añaden y eliminan elementos sólo en un extremo; es decir, no se puede eliminar más que el elemento que ocupa el primer lugar de la lista en ese momento. Las pilas se utilizan en hardware y software para almacenar las direcciones de instrucciones desde las que se hacen llamadas a subrutinas.
Se denominan cola o listas FIFO a una lista en que las inserciones se realizan sólo en el final y sólo se puede acceder o eliminar en un instante dado el primer elemento de la lista.
Las listas se memorizan utilizando punteros.

Representación de una lista

Listas Enlazadas
una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior y/o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio.

Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares

Lista de Enlace Simple
Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del último nodo contiene null para indicar el final de la lista. a la variable de referencia se la suele llamar top. . La siguiente figura presenta una lista de enlace simple de tres nodos, donde top referencia al nodo A, A conecta con B y B conecta con C y C es el nodo final:

Un algoritmo común de las listas de enlace simple es la inserción de nodos. Este algoritmo está implicado de alguna forma porque tiene mucho que ver con cuatro casos: cuando el nodo se debe insertar antes del primer nodo; cuando el nodo se debe insertar después del último nodo; cuando el nodo se debe insertar entre dos nodos; y cuando la lista de enlace simple no existe.

DECLARE CLASS Node
DECLARE STRING name
DECLARE Node next
END DECLARE
DECLARE Node top = NULL

Este pseudocódigo declara una clase auto-referenciada llamada Node con un campo no de enlace llamado name y un campo de enlace llamado next. También declara una variable de referencia top (del tipo Node) que contiene una referencia al primer Node de una lista de enlace simple. Como la lista todavía no existe, el valor inicial de top es NULL. Cada uno de los siguientes cuatro casos asume las declaraciones de Node y top.

La lista de enlace simple no existe
Este es el caso más simple. Se crea un Node, se asigna su referencia a top, se inicializa su campo no de enlace, y se asigna NULL a su campo de enlace. El siguiente pseudocódigo realiza estas tareas:

• top = NEW Node
• top.name = "A"
• top.next = NULL

En la siguiente imagen se puede ver la lista de enlace simple que emerge del pseudocódigo anterior:

El nodo debe insertarse antes del primer nodo
Se crea un Node, se inicialia su campo no de enlace, se asigna la referencia de top al campo de enlace next, y se asigna la referencia del Node recien creado a top. El siguiente pseudocódigo (que asume que se ha ejecutado el pseudocódigo anterior) realiza estas tareas:

DECLARE Node temp
temp = NEW Node
temp.name = "B"
temp.next = top
top = temp

El resultado del listado anterior aparece en la siguiente imagen:


El nodo debe insertarse detrás del último nodo

Se crea un Node, se inicializa su campo no de enlace, se asigna NULL al campo de enlace, se atraviesa la lista de enlace simple hasta el último Node, y se asigna la referencia del Node recien creado al campo next del último nodo. El siguiente pseudocódigo realiza estas tareas:

temp = NEW Node
temp.name = "C"
temp.next = NULL
DECLARE Node temp2
temp2 = top
// We assume top (and temp2) are not NULL
// because of the previous pseudocode
WHILE temp2.next IS NOT NULL
temp2 = temp2.next
END WHILE
// temp2 now references the last node
temp2.next = temp

La siguiente imagen revela la lista después de la inserceción del nodo C después del nodo A.

El nodo se debe insertar entre dos nodos
Este es el caso más complejo. Se crea un Node, se inicializa su campo no de enlace, se atraviesa la lista hasta encontrar el Node que aparece antes del nuevo Node, se asigna el campo de enlace del Node anterior al campo de enlace del Node recien creado, y se asigna la referencia del Node recien creado al campo del enlace del Node anterior. El siguiente pseudocódigo realiza estas tareas:

temp = NEW Node
temp.name = "D"
temp2 = top
// We assume that the newly created Node is inserted after Node
// A and that Node A exists. In the real world, there is no
// guarantee that any Node exists, so we would need to check
// for temp2 containing NULL in both the WHILE loop's header
// and after the WHILE loop completes.
WHILE temp2.name IS NOT "A"
temp2 = temp2.next
END WHILE
// temp2 now references Node A.
temp.next = temp2.next
temp2.next = temp

La siguiente imagen muestra la inserción del nodo D entre los nodos A y C.

El siguiente listado presenta el equivalente Java de los ejemplos de pseudocódigo de insercción anteriores:

// SLLInsDemo.java
class SLLInsDemo {
static class Node {
String name;
Node next;
}

public static void main (String [] args) {
Node top = null;

// 1. The singly linked list does not exist
top = new Node ();
top.name = "A";
top.next = null;

dump ("Case 1", top);

// 2. The singly linked list exists, and the node must be inserted
// before the first node

Node temp;
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;

dump ("Case 2", top);

// 3. The singly linked list exists, and the node must be inserted
// after the last node
temp = new Node ();
temp.name = "C";
temp.next = null;

Node temp2;
temp2 = top;

while (temp2.next != null)
temp2 = temp2.next;

temp2.next = temp;

dump ("Case 3", top);

// 4. The singly linked list exists, and the node must be inserted
// between two nodes
temp = new Node ();
temp.name = "D";

temp2 = top;

while (temp2.name.equals ("A") == false)
temp2 = temp2.next;
temp.next = temp2.next;
temp2.next = temp;

dump ("Case 4", 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 ();
}
}

Borrar el Primer nodo

Asigna el enlace del campo next del nodo referenciado por top a top:
• top = top.next; // Reference the second Node (or NULL if there is only one Node)
La siguiente imagen presenta las vistas anterior y posterior de una lista donde se ha borrado el primer nodo. en esta figura, el nodo B desaparece y el nodo A se convierte en el primer nodo.

Borrar cualquier nodo que no sea el primero
Localiza el nodo que precede al nodo a borrar y le asigna el enlace que hay en el campo next del nodo a borrar al campo next del nodo que le precede. El siguiente pseudocódigo borra el nodo D:

temp = top
WHILE temp.name IS NOT "A"
temp = temp.next
END WHILE
// We assume that temp references Node A
temp.next = temp.next.next
// Node D no longer exists

La siguiente figura presenta las vistas anterior y posterior de una lista donde se ha borrado un nodo intermedio. En esa figura el nodo D desaparece.

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 ();
}
}

Lista Doblemente Enlazada/span>
Las listas de enlace simple restringen el movimiento por lo nodos a una sóla 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 atraversarlos en dirección opuesta, problamente 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 desaperecen 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 direccion 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 direccion 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 direccion hacia adelante, y topBackward referencia el primero nodo la dirección inversa.

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;
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 ();
}
}
[+/-] Leer más...