PDF de programación - Tema 4. Listas enlazadas - Programación II

Programación II
Tema 4. Listas enlazadas

Iván Cantador
Escuela Politécnica Superior
Universidad Autónoma de Madrid

Contenidos

1

• El TAD Lista
• Estructura de datos de Lista
• Implementación en C de Lista
• Implementación de Pila y Cola con Lista
• Tipos de Listas

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

10/03/2015

1

Contenidos

• El TAD Lista
• Estructura de datos de Lista
• Implementación en C de Lista
• Implementación de Pila y Cola con Lista
• Tipos de Listas

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

El TAD Lista. Definición
• Lista. Colección de objetos donde: 

• todos menos uno tienen un objeto “siguiente”
• todos menos uno tienen un objeto “anterior”

• Permite la representación secuencial y ordenada de 

objetos de cualquier tipo
• Insertando o extrayendo objetos al principio/final
• Insertando o extrayendo objetos en cualquier punto

• Puede verse como una meta‐EdD más que como un TAD
• Puede usarse para implementar pilas, colas, colas de prioridad, 

etc.

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

2

3

10/03/2015

2

El TAD Lista. Funciones primitivas

• Funciones primitivas básicas

Lista lista_crear()
void lista_liberar(Lista l)
boolean lista_vacia(Lista l)
// ¡Ojo! No existe lista_llena
status lista_insertarIni(Lista l, Elemento e) // Inserta al inicio
Elemento lista_extraerIni(Lista l)
// Extrae del inicio
status lista_insertarFin(Lista l, Elemento e) // Inserta al final
Elemento lista_extraerFin(Lista l)
// Extrae del final

• … y otras

// Inserta el elemento e en la posicion pos de la lista L
status lista_insertarPos(Lista l, Elemento e, int pos)
// Inserta el elemento e en la lista L en orden
status lista_insertarOrden(Lista l, Elemento e)
...

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

• El TAD Lista
• Estructura de datos de Lista
• Implementación en C de Lista
• Implementación de Pila y Cola con Lista
• Tipos de Listas

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

4

5

10/03/2015

3

EdD de Lista: array
• Opción 1: tabla/array de elementos

6

T =

0

1

2

3

siguiente(T[i]) ≡ T[i + 1]; anterior(T[i])≡ T[i – 1]

• Ventajas

‐ Fácil implementación
‐ Memoria estática

• Inconvenientes

‐ Desperdicio de espacio
‐ Ineficiencia al insertar al inicio y en posiciones intermedias: hay que 

mover todos los elementos a la derecha una posición (posible solución: 
lista circular? ocurre lo mismo?)

inserción

0

…

106

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

EdD de Lista: lista enlazada (LE)
• Opción 2: Lista Enlazada (LE)

• Listas de nodos
• Nodo

‐ Campo info: contiene el objeto/dato a guardar
‐ Campo next: apunta al siguiente nodo de la lista

7

info

next

• Lista enlazada: colección de nodos enlazados + puntero al nodo 

inicial. El next del último nodo apunta a NULL.

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

10/03/2015

4

EdD de Lista: LE estática
• Estructura estática para LE

• Tabla de nodos

i= 1

• Ventajas

‐ Memoria estática

• Inconvenientes

0
1

2

3

4

5

6

7

n= 4
n= 6

n= 2

n= -1

info

next

‐ Desperdicio de memoria
‐ Complejidad (p.e. ¿siguiente nodo libre?)

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

EdD de Lista: LE dinámica
• Los nodos se crean/destruyen dinámicamente

• Uso de memoria dinámica
• Creación de nodos ≡ malloc
• Liberación de nodos ≡ free

• Ventajas

nodo

• Sólo se tiene reservada la memoria que se necesita en cada momento
• Se pueden albergar tantos elementos como la memoria disponible permita
•

Insertar/extraer nodos no requiere desplazamientos de memoria

• Inconvenientes

• Bueno para acceso secuencial; malo para acceso aleatorio

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

8

9

10/03/2015

5

10/03/2015

10

EdD de Lista en C

• EdD de Nodo

• Se oculta al usuario definiéndola y poniendo la implementación 

de sus funciones asociadas en lista.c
// En lista.c (antes de la definición de Lista)
struct _Nodo {

Elemento *info;
struct _Nodo *next;

};
typedef struct _Nodo Nodo;

info

next

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

EdD de Lista en C
• Creación de un nodo

Nodo *nodo_crear() {
Nodo *pn = NULL;
pn = (Nodo *) malloc(sizeof(Nodo));
if (!pn) return NULL;
pn->info = NULL;
pn->next = NULL;
return pn;

}

// Habrá que apuntar info a un elemento

11

• Ejemplo de llamada

Nodo *n = NULL;
n = nodo_crear();
if (!n) {
// CdE
}

nodo_crear


pn

llamada a nodo_crear


n

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

6

10/03/2015

12

EdD de Lista en C
• Liberación de un nodo

void nodo_liberar(Nodo *pn) {

if (pn) {

elemento_liberar(pn->info); // Libera elemento de info
free(pn);

// Libera nodo

}

}

• Ejemplo de llamada

Nodo *n = NULL;
n = nodo_crear();
if (!n) {
// CdE
}
...
nodo_liberar(n);

nodo_liberar


pn

llamada a nodo_liberar


n

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

13

EdD de Lista en C
• Lista enlazada

• Colección de nodos enlazados 
• La lista es un puntero (first) al nodo inicial
• El último nodo apunta a NULL 

first

• Tipo de dato Lista ≡ Puntero al nodo inicial

// En lista.h
typedef struct _Lista Lista;
// En lista.c
struct _Lista {
Nodo *first;
};

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

7

Contenidos

14

• El TAD Lista
• Estructura de datos de Lista
• Implementación en C de Lista
• Implementación de Pila y Cola con Lista
• Tipos de Listas

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

15

Implementación en C: primitivas
// Primitivas de Nodo
Nodo *nodo_crear()
// luego habrá que apuntar info a un elemento
void nodo_liberar(Nodo *pn) // llama a elemento_liberar sobre info
// Primitivas de Lista (Nodo está oculto para el usuario)
Lista *lista_crear()
void lista_liberar(Lista *pl)
boolean lista_vacia(Lista *pl)
status lista_insertarIni(Lista *pl, Elemento *pe)
Elemento *lista_extraerIni(Lista *pl)
status lista_insertarFin(Lista *pl, Elemento *pe)
Elemento *lista_extraerFin(Lista *pl)

Importante: para mayor legibilidad, en algunas de las implementaciones que  
siguen NO se realizan ciertos controles de argumentos de entrada y de errores      
 ¡habría que hacerlos!

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

10/03/2015

8

10/03/2015

Implementación en C: lista_crear

16

struct _Lista {
Nodo *first;
};

• Crear una lista

Lista *lista_crear() {

Lista *pl = NULL;
pl = (Lista *) malloc(sizeof(Lista));
if (!pl) return NULL;
pl->first = NULL;
return pl;

}

}

• Ejemplo de llamada

Lista *l = NULL;
l = lista_crear();

lista_crear


pl


l

llamada a lista_crear



first

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C: lista_vacia

17

• Comprobar si una lista está vacía

boolean lista_vacia(Lista *pl) {
if (!pl) return TRUE;
if (!pl->first) return TRUE;
return FALSE;

// Caso de error
// Caso de lista vacía
// Caso de lista no vacía

• Ejemplo de llamada

Lista *l = NULL;
l = lista_crear();
...
if (lista_vacia(l) == FALSE) {
}

...

lista_vacia


pl


l

llamada a lista_vacia



first

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

9

Implementación en C: lista_insertarIni
• Insertar un elemento al inicio de una lista

1) Crear un nuevo nodo
2) Hacer que este nodo apunte al inicio de la lista
3) El nuevo nodo es ahora el inicio de la lista

18

• Pseudocódigo
status lista_insertarIni(Lista l, Elemento e) {

Nodo n = nodo_crear()
info(n) = e
next(n) = l
l = n
devolver OK

}

3)

l

e

1)

n

l

2)

x

x

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C: lista_extraerIni

19

• Implementar la función lista_insertarIni

status lista_insertarIni(Lista *pl, Elemento *pe)

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

10/03/2015

10

Implementación en C: lista_insertarIni
• Implementación
status lista_insertarIni(Lista *pl, Elemento *pe) {

Nodo *pn = NULL;
if (!pl || !pe) return ERROR;
pn = nodo_crear();
if (!pn) {
return ERROR;
}
pn->info = elemento_copiar(pe);
if (!pn->info) {
nodo_liberar(pn);
return ERROR;

}
pn->next = pl->first;
pl->first = pn;
return OK;

pl->first

3)
pl->first

2)

e

1)

pn

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C: lista_insertarIni
• Implementación
status lista_insertarIni(Lista *pl, Elemento *pe) {

Nodo *pn = NULL;
if (!pl || !pe) return ERROR;
pn = nodo_crear();
if (!pn) {
return ERROR;
}
pn->info = elemento_copiar(pe);
if (!pn->info) {
nodo_liberar(pn);
return ERROR;

}
pn->next = pl->first;
pl->first = pn;
return OK;

pl->first

3)
pl->first

2)

e

1)

pn

Programación II – Tema 4: Listas enlazadas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

}

}

x

x

x

x

20

21

10/03/2015

11

Implementación en C: lista_insertarIni
• Implementación
status lista_insertarIni(Lista *pl, Elemento *pe) {

2

1

Nodo *pn = NULL;
if (!pl || !pe) return ERROR;
pn = nodo_crear();
if (!pn) {
return ERROR;
}
pn->info = elemento_copiar(pe);
if (!pn