Listas enlazadas

Listas Enlazadas en C++:

Paso

Ejemplo Tipos Básicos Estructuras
struct Tcomplex { double p_r; double p_i; }; typedef Tcomplex *TPComplex;

Definición del Tipo typedef char *TPChar;typedef int *TPInt;

ó typedef struct Tcomplex *TPComplex; struct Tcomplex { double p_r; double p_i; };

Declaración de varibles

Petición de if((p_int == NULL) || memoria (y (p_char == NULL))comprobación de { que la ha asignado) Acceso I: Modifición Acceso II: Consulta Borrado

TPInt p_int; TPChar p_char; p_int = new(int); p_char = new(char);

TPComplex p_complex; p_complex = new(Tcomplex);if(p_complex == NULL) { cout p_i; delete(p_complex);

cout > *p_char; cout sig = NULL; }

d paux

NULL

2. Si la lista es vacía introducimos al principio: NULL
if( l == NULL ) { l = paux; }l d paux

=>
NULL

l d paux NULL

3. Si no es vacía comprobamos si hay que añadir al principio: e
if( l.dato > d ) { paux->sig = l; l = paux; }

…

e

…

l d paux

=>
NULL

l dpaux

4. Insertamos en medio a
/* Creamos un puntero auxiliar para buscar la posición donde insertar */ pbusca = l;

b

e

…

l d pbusca paux a l d pbusca a l d pbusca paux paux b e … NULLb e … NULL

/* Recoremos la lista buscando donde insertar */ while( (pbusca->sig != NULL) && (pbusca->sig->datos < d)) { pbusca = pbusca->sig; }

/* Una vez encontrada la posición insertamos elnuevo nodo */ paux->sig = pbusca->sig; pbusca->sig = paux;

Borrar: Borrar es similar a la insertar. Primero se comprueba si es vacía, en tal caso no hacemos nada. Si no está vacía buscamos elelemento que queramos borrar, y una vez localizado, lo sacamos de la lista y liberamos la memoria que tenía asignada1. Borrado del primer elemento
if(l->dato == d) { ptr = l; l = l->sig; delete(ptr); }d l

e

... => l

d

e

...

ptr

ptr

2. Borrado de un elemento intermedio
/* Creamos dos punteros auxiliares uno que examine la posición actual y otro que indique la posición...