Listas enlazadas

APUNTE : N-4
RAMO : ESTRUCTURA DE DATOS
PROFESORA : MAGDALENA NIETO G.
CARRERA : ICI 1er semestre 2011

UNIDAD: LISTAS ENLAZADAS

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

1.- Clase auto-referenciada: Es una clase con almenos un campo cuyo tipo de referencia es el nombre de la clase:
class Empleado
{ private int codigo;
private String nombre;
private double sueldo;
public Empleado next;//campo de enlace
// otros atributos
} Empleado es una clase auto-referenciada porque su campo next tiene el tipo Empleado.

2.- Nodo: un objeto creado desde una clase auto-referenciada.

3.- Campo deenlace: 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, codigo, nombre, y sueldo son campos no de enlace.

4.- Enlace: la referencia a un campo de enlace. En el fragmento de código anterior, la referencia next a un nodo Empleado es un enlace.

Los cuatro conceptos anteriores nos llevan a la siguientedefinición:
Una lista enlazada es una secuencia de nodos que se interconectan mediante sus campos de enlace.

Para representar a las listas enlazadas se utilizará la siguiente notación:

La figura anterior presenta tres nodos: A, B y C. Cada nodo se divide en áreas de contenido (en amarillo) y una o más áreas de enlace (en verde).
Las áreas de contenido representan todos los campos queno 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). El único á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 tresvariantes más populares son:
• la lista de enlace simple
• la lista doblemente enlazada y
• la lista enlazada circular.

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 (top) contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y elenlace 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:



INSERCIÓN EN LA LISTA ENLAZADA DINÁMICA

Unalgoritmo común de las listas de enlace simple es la inserción de nodos. Este algoritmo tiene 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
• cuando la lista de enlace simple no existe.


Declaración de la clase Nodo:
class Nodo
{ private intcodigo;
private String nombre;
public Nodo next;
}

Declaración de variable que guarda dirección de inicio de la lista
Nodo top = -1; // top inicialmente tiene valor nulo
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 Nodo y top:

Caso 1: La lista de enlace simple no existe (insertaremos el 1er nodo)top = new Nodo // se crea un Nodo y se asigna a top
top.nombre = "A" //se inicializa su dato no enlace
top.next = NULL //asigna null a su campo enlace next

Representación gráfica:



Caso 2: El nodo debe insertarse antes del primer nodo:

DECLARE Nodo nuevo

nuevo= NEW Nodo //se crea un nodo se asigna a nuevo
nuevo.nombre = "B" //se inicializa su campo no de...