Lista enlazadas

LISTAS ENLAZADAS

PARTE 1
CLASE N°6
Leissi M. Castañeda León lcl@upnorte.edu.pe lcl@comunidad.upn.edu.pe https://sites.google.com/site/leissicl/

Que veremos hoy?
1. 2. 3. 4.

Introducción Listas Simplemente Enlazadas Listas Doblemente Enlazadas Listas Circulares

2

1. Introducción
Las estructura de datos como arreglos y registros, se denominan estáticas (durante la compilaciónse le asigna un espacio de memoria, y no se altera durante la ejecución) La estructura de datos lista, es lineal (cada elemento le puede seguir a otro) y dinámica (manejar memoria de manera flexible) de datos. VENTAJA principal: dinamismo, se puede adquirir posiciones de memoria y liberar a medida que se necesiten. Considerar que NO pueden reemplazar en todas las aplicaciones a los arreglos.
3Introducción
Las listas enlazadas son colecciones de elementos llamados nodos; el orden entre éstos se establece por medio de un tipo de datos denominado punteros, apuntadores o referencias a otros nodos. Entonces se podrá distinguir: el dato de tipo apuntador y el dato contenido en la celda al cual éste apunta. Operaciones más importantes: búsqueda (no muy eficiente), inserción y eliminación.Tipos:
Listas simplemente enlazadas Listas doblemente enlazadas Listas circulares
4

2. Listas Simplemente Enlazadas

5

Listas Simplemente Enlazadas
Una LSE constituye una colección de elementos llamados nodos. El orden entre los nodos se establece por punteros (referencias a otros nodos). Un tipo especial: la lista vacía Un nodo está formado por:
Un campo INFORMACIÓN, del tipo de datoque se quiere almacenar. Un campo ENLACE, de tipo puntero, para enlazar con otro nodo. Si fuera el último tendría como valor NULL.

6

Estructura Nodo para una LSE
typedef struct Nodo { int dato; struct Nodo *sgt; } TNodo;

INFORMACIÓN ENLACE

7

Creando un puntero cabecera
Crearemos un puntero, de tipo de la estructura Nodo (Tnodo), que apunte al nodo inicial de la LSE typedefstruct LSE { TNodo *pInicio; } TLSE;

8

Para crear una lista vacía
Crea una lista devolviendo un puntero Tnodo TLSE *crearLista() { TLSE *l=(TLSE*)malloc(sizeof(struct LSE)); l->pInicio=NULL; return l; NULL }
pInicio
9

Ejemplo

4

2

1

NULL

pInicio

10

Operaciones con LSE
Recorrido de la lista
Iterativo Recursivo

Inserción de un elemento
Al Inicio Al Final Antesque un determinado nodo Después que un determinado nodo

11

Operaciones con LSE
Eliminación de un elemento
El primer nodo El último nodo Eliminar un nodo con información X Eliminar el nodo anterior al nodo con información X Eliminar el nodo posterior al nodo con información X

Búsqueda de un elemento
Desordenada Ordenada Recursivo

12

Recorrido de la lista
Esta operación consisteen visitar cada uno de los nodos que forman la lista. La visita puede implicar una operación simple; por ejemplo, imprimir la información del nodo, o una compleja, dependiendo del problema que se intente resolver. Para recorrer todos los nodos de una LSE se comienza con el primero. Se toma el valor del campo ENLACE de éste y se avanza al segundo, así hasta llegar al último nodo, cuyo campo ENLACEtenga el valor NULL. En general, la dirección de un nodo, excepto el primero está dada por el campo ENLACE de su predecesor.
13

Recorrido de la lista: Iterativa
/*Imprimiremos los datos en el recorrido iterativo de la lista*/

void recorridoIterativo(TLSE *lista) { TNodo *p=NULL; p=lista->pInicio; while(p!=NULL) { printf(" %d ->",p->dato); p=p->sgt; } }
14

Recorrido de la lista:Recursiva
/*Imprimiremos los datos en el recorrido recursivo de la lista*/

void recorridoRecursivo(TNodo *p) { if(p!=NULL) { printf(" %d ->",p->dato); recorridoRecursivo(p->sgt); } }
Nota: el TNodo *p que ingresa en la primera llamada es el nodo Inicio
15

Inserción de un elemento
Esta operación en las LSE consiste en agregar un nuevo nodo a la lista. Dependiendo de la posición en la que se...