PDF de programación - Unidad III - Listas

Unidad III - Listas



Lista de Enlace Simple
Los Algoritmos de Concatenación e

Inversión

Lista Doblemente Enlazada
Algoritmo de Inserción-

Ordenada

Lista de Enlace Circular
Listas Enlazadas frente a Arrays



Java en castellano (Tutorial Estructuras de Datos y Algoritmos en Java)
http://www.programacion.com/java/tutorial/jap_data_alg/

Tutorial original en Inglés
http://www.javaworld.com/



Listas Enlazadas

Además de los arrays, otra de las estructuras de datos muy utilizadas es la lista enlazada. Esta estructura
implica cuatro conceptos: clase auto-refenciada, nodo, campo de enlace y enlace.

• Clase auto-referenciada: una clase con al menos un campo cuyo tipo de referencia es el

nombre de la clase:



class Employee {
private int empno;
private String name;
private double salary;

public Employee next;

// Other members

}

Employee es una clase auto-referenciada porque su campo next tiene el tipo Employee.

• Nodo: un objeto creado desde una clase auto-referenciada.
• Campo de enlace: un campo cuyo tipo de referencia es el nombre de la clase. En el fragmento
de código anterior, next es un campo de enlace. Por el contrario, empno, name, y salary son
campos no de enlace.

• Enlace: la referencia a un campo de enlace. En el fragmento de código anterior, la referencia

next a un nodo Employee es un enlace.

Los cuatro conceptos de arriba nos llevan a la siguiente definición: una lista enlazada es una secuencia
de nodos que se interconectan mediante sus campos de enlace. En ciencia de la computación se utiliza
una notación especial para ilustrar las listas enlazadas. En la siguiente imagen aparece una variante de
esta notación que utilizaré a lo largo de esta sección:

_____________________________________________________________


Java en castellano (Tutorial Estructuras de Datos y Algoritmos en Java)
http://www.programacion.com/java/tutorial/jap_data_alg/
Tutorial original en Inglés
http://www.javaworld.com/





La figura anterior presenta tres nodos: A, B y C. Cada nodo se divide en áreas de contenido (en naranja) y
una o más áreas de enlace (en verde). Las áreas de contenido representan todos los campos que no son
enlaces, y cada área de enlace representa un campo de enlace. Las áreas de enlace de A y C tienen
unas flechas para indicar que referencian a otro nodo del mismo tipo (o subtipo). La única área de enlace
de B incorpora una X para indicar una referencia nula. En otras palabras, B no está conectado a ningún
otro nodo.

Aunque se pueden crear muchos tipos de listas enlazadas, las tres variantes más populares son la lista
de enlace simple, la lista doblemente enlazada y la lista enlazada circular. Exploremos esas variantes,
empezando con la lista enlazada.

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.
Aunque normalmente a la variable de referencia se la suele llamar top, usted puede elegir el nombre que
quiera. 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. Antes de estudiar cada caso consideremos
el siguiente pseudocódigo:



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:

_____________________________________________________________


Java en castellano (Tutorial Estructuras de Datos y Algoritmos en Java)
http://www.programacion.com/java/tutorial/jap_data_alg/
Tutorial original en Inglés
http://www.javaworld.com/



• 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 inicializa su campo no de enlace, se asigna la referencia de top al campo
de enlace next, y se asigna la referencia del Node recién 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 recién
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



_____________________________________________________________


Java en castellano (Tutorial Estructuras de Datos y Algoritmos en Java)
http://www.programacion.com/java/tutorial/jap_data_alg/
Tutorial original en Inglés
http://www.javaworld.com/







// temp2 now references the last node

temp2.next = temp

La siguiente imagen revela la lista después de la inserció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 recién creado, y se asigna la referencia
del Node recién 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 inserció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

_____________________________________________________________


Java en castellano (Tutorial Estructuras de Datos y Algoritmos en Java)
http://www.programacion.com/java/tutorial/jap_data_alg/
Tutorial original en Inglés
http://www.javaworld.com/




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 = t