Tema 3: La estructura de datos Lista
Estructuras de DatosIngeniería en InformáticaUniversidad Carlos III de Madrid
Laboratorio DEICurso 2003/04
Laboratorio DEI
2003/04 Estructura de Datos Listas - 2
Listas: descripción lógica LISTA = colección de elementos homogéneos
entre los que existe una relación linealCada elemento de la lista, a excepción del primero, tiene un único predecesorCada elemento de la lista, a excepción del último, tiene un único sucesor
Nodos y enlaces
Laboratorio DEI
2003/04 Estructura de Datos Listas - 3
Listas: descripción lógica Orden de nodos afecta a la función de acceso
Según orden de inserciónSegún clave
EjemploLista de calificaciones ::= <Alumno> + {<Alumno>}<Alumno>::= <<DNI>> + <<NIA>> + <Apellido1> +
<Apellido2> + <Nombre> + <Calificación>
Laboratorio DEI
2003/04 Estructura de Datos Listas - 4
Listas: descripción lógica Listas Arrays
Listas son flexibles y permiten cambio de implementación
OperacionesInsertar, Borrar, Modificar, etc.
Tipos de listasSimplesOrdenadasPilasColasDoblemente enlazadas (LDE)Circulares
Laboratorio DEI
2003/04 Estructura de Datos Listas - 5
TAD Lista: Posibles implementaciones
····UNG
i = min +1 +2 ... ... ... max
posición = i
elem[i] =
tamaño = 3
i = 1 2 3 4 5 … max
posición = i
elem[i] =
tamaño = 3
G 4 · · · · N 5 U 0 · · · ··
IUNG
i = 1 2 3 4 5 6 7 8
posición = i
elem[i] =
tamaño = 4max = 4
TONS
tamaño = 3max = 8
Vector original
Vector ampliado
G I
U
N
S null
posición
tamaño = 5
Estática Dinámica
En
laza
da
Secu
en
cia
l
Laboratorio DEI
2003/04 Estructura de Datos Listas - 6
Listas Simples Lista Simple = colección de elementos
homogéneos cuya relación lineal es determinada por la posición del elemento en la lista
Comienzo + Enlace al siguiente ( puntero)
Definición:<listaSimple> ::= <comienzo> + {<nodo>}<nodo> ::= <informacion> + <enlace><informacion> ::= <<dato>>{<<dato>>}<enlace> ::= (<<ReferenciaNodo>> | NULL)<comienzo> :: =<enlace>
Laboratorio DEI
2003/04 Estructura de Datos Listas - 7
TAD Lista Simple: operaciones
asignarInfo(referenciaNodo, valorInformacion)
asignarEnlace(referenciaNodo, valorEnlace)
Modificación de los nodos
info(referenciaNodo) Informacionsiguiente(referenciaNodo) enlace
Acceso a los nodos
recorrer(nombreLista Recorrido de la lista
buscar(nombreLista, dato) informacionbuscar(nombreLista, dato) referenciaNodopertenece(nombreLista,informacion) Booleano
borrar(nombreLista, valorInfo) Borrado de nodos
insertar(nombreLista, valorInfo, posicion)
insertar(nombreLista, valorInfo)
listaVacia(nombreLista) BooleanolistaVacia(referenciaNodo) BooleanolistaLlena(nombreLista) Booleano
Comprobación del estado
crearLista (nombreLista)Creación de una lista
Inserción de nodos
Búsqueda de un nodo
Laboratorio DEI
2003/04 Estructura de Datos Listas - 8
Listas Simples Aclaraciones a las operaciones:
listaLlena sólo tiene sentido si lista es acotadaacceso y modificación serán métodos get y put
Ejemplo y pseudocódigoinsertar (nombreLista, valorInfo, posición)insertar (nombreLista, valorInfo)borrar (nombreLista, valorInfo)buscar (nombreLista, dato) informaciónrecorrer (nombreLista)
Laboratorio DEI
2003/04 Estructura de Datos Listas - 9
Laboratorio DEI
2003/04 Estructura de Datos Listas - 10
Laboratorio DEI
2003/04 Estructura de Datos Listas - 11
Listas Ordenadas La posición de cada nodo viene determinada por el valor
de uno o más campos obligatorios de información del nodo denominados clave
No se permite tener dos nodos con la misma clave
Definición<listaOrdenada> ::= <comienzo> + {<nodo>}<comienzo> ::= <enlace><enlace> ::= (<<ReferenciaNodo>> | NULL)<nodo> ::= <clave> + <informacion> + <enlace><clave> ::= <<dato>>{<<dato>>}<informacion> ::= {<<dato>>}
Laboratorio DEI
2003/04 Estructura de Datos Listas - 12
TAD Lista Ordenada: operaciones
asignarClave(referenciaNodo, valorClave)
asignarInfo(referenciaNodo, valorInformacion)
asignarEnlace(referenciaNodo, valorEnlace)
Modificación de los nodos
clave(referenciaNodo) Claveinfo(referenciaNodo) Informacionsiguiente(referenciaNodo) enlace
Acceso a los nodos
recorrer(nombreLista Recorrido de la lista
buscar(nombreLista, valorClave) Informacionbuscar(nombreLista, valorClave)ReferenciaNodopertenece(nombreLista,valorClave) Booleano
borrar(nombreLista, valorClave)Borrado de nodos
insertar(nombreLista, valorClave, valorInfo)
listaVacia(nombreLista) BooleanolistaVacia(referenciaNodo) BooleanolistaLlena(nombreLista) Booleano
Comprobación del estado
crearLista (nombreLista)Creación de una lista
Inserción de nodos
Búsqueda de un nodo
Laboratorio DEI
2003/04 Estructura de Datos Listas - 13
Pilas Pila = colección ordenada de elementos homogéneos en la
que sólo se pueden añadir y eliminar elementos por el principio de la misma (cabecera) filosofía LIFO
Definición<pila> ::= <cabecera> + {<nodo>}<cabecera> ::= <enlace><enlace> ::= (<<ReferenciaNodo>> | NULL)<nodo> ::= <informacion> + <enlace><informacion> ::= <<dato>>{<<dato>>}
Laboratorio DEI
2003/04 Estructura de Datos Listas - 14
TAD Pila: operaciones
pop(nombrePila) informacionExtracción de nodos
push(nombrePila, valorInfo)Inserción de nodos
pilaVacia(nombrePila) BooleanopilaLlena(nombrePila) Booleano
Comprobación del estado
crearPila (nombrePila)Creación de pila
asignarInfo(referenciaNodo, valorInformacion)
asignarEnlace(referenciaNodo, valorEnlace)Modificación de los nodos
info(referenciaNodo) Informacionsiguiente(referenciaNodo) Enlace
Acceso a los nodos
cabecera(nombrePila) informacionAcceso a la cabecera*
* Opcional: Accede a la cabecera sin eliminarla
Laboratorio DEI
2003/04 Estructura de Datos Listas - 15
TAD Pila: ejemplos de aplicación Vuelta atrás en un navegador web
Comando “undo” en un editor
Secuencia de métodos activos en la Java Virtual Machine:
main() {int i = 5;foo(i);}
foo(int j) {int k;k = j+1;bar(k);}
bar(int m) {…}
bar PC = 1 m = 6
foo PC = 3 j = 5 k = 6
main PC = 2 i = 5
• Cuando se invoca un método, se inserta en la pila una nueva entrada
• Por cada método se guardan:variables localesvalor devueltocontador de programa
• Cuando el método finaliza se saca ese elemento de la pila y se devuelve el control al método que esté en la cabecera
Laboratorio DEI
2003/04 Estructura de Datos Listas - 16
Colas Cola = colección ordenada de elementos homogéneos en la
que sólo se pueden añadir elementos por el final y se eliminan por el principio (frente) filosofía FIFO
Definición<cola> ::= <frente> + <final> + {<nodo>}<frente> ::= <enlace><enlace> ::= (<<ReferenciaNodo>> | NULL)<final> ::= <enlace><nodo> ::= <informacion> + <enlace>< informacion > ::= <<dato>>{<<dato>>}
Laboratorio DEI
2003/04 Estructura de Datos Listas - 17
TAD Cola: operaciones
desencolar(nombreCola) informacionExtracción de nodos
encolar(nombreCola, valorInfo)Inserción de nodos
colaVacia(nombreCola) BooleanocolaLlena(nombreCola) Booleano
Comprobación del estado
crearCola (nombreCola)Creación de cola
asignarInfo(referenciaNodo, valorInformacion)
asignarEnlace(referenciaNodo, valorEnlace)Modificación de los nodos
info(referenciaNodo) Informacionsiguiente(referenciaNodo) Enlace
Acceso a los nodos
cabecera(nombreCola) informacionAcceso a la cabecera*
* Opcional: Accede a la cabecera sin eliminarla
Laboratorio DEI
2003/04 Estructura de Datos Listas - 18
TAD Cola: casos particulares Colas circulares
Implementación estática como arrayReferencia al primero y al últimoAritmética módulo C (Capacidad de la cola)Llevar la cuenta del número de elementos
Laboratorio DEI
2003/04 Estructura de Datos Listas - 19
TAD Cola: casos particulares Colas de prioridad
Laboratorio DEI
2003/04 Estructura de Datos Listas - 20
TAD Cola: ejemplos de aplicación Listas de espera Acceso a recursos compartidos dedicados (v.g.,
impresoras) Multiprogramación de la CPU
Laboratorio DEI
2003/04 Estructura de Datos Listas - 21
Listas Doblemente Enlazadas (LDE) Relación lineal en ambos sentidos Enlace a predecesor y antecesor en cada nodo Recorrido puede ser en ambos sentidos Pueden ser simples u ordenadas
Definición:<lde> ::= <comienzo> + {<nodo>}<comienzo> :: = <enlace><enlace> ::= (<<ReferenciaNodo>> | NULL)<nodo> ::= <informacion> + <predecesor> + <sucesor><predecesor> ::= <enlace><sucesor> ::= <enlace><informacion> ::= <<dato>>{<<dato>>}
Laboratorio DEI
2003/04 Estructura de Datos Listas - 22
LDE: operacionesCreación de una lista crearLista(nombreLista)
Comprobación del estado listaVacia(nombreLista) BooleanolistaVacia(referenciaNodo) BooleanolistaLlena(nombreLista) Booleano
Inserción de nodos insertar(nombreLista, valorInfo, posicion)
insertar(nombreLista, valorInfo)
Borrado de nodos borrar(nombreLista, valorInfo)
Búsqueda de un nodo buscar(nombreLista, dato) informacionbuscar(nombreLista, dato) referenciaNodopertenece(nombreLista,informacion) Booleano
Recorrido de la lista recorrer(nombreLista, sentido)
Acceso a los nodos info(referenciaNodo) Informacionanterior(referenciaNodo) enlacesiguiente(referenciaNodo) enlace
Modificación de los nodos asignarInfo(referenciaNodo, valorInformacion)
asignarAnterior(referenciaNodo, valorEnlace)
asignarSiguiente(referenciaNodo, valorEnlace)
Laboratorio DEI
2003/04 Estructura de Datos Listas - 23
Técnicas de Simplificación
Algunos elementos (principio y final) se tratan como casos especiales al implementar las operaciones
Rediseño de estructuras para que los elementos terminales se traten igual que el resto
Estructuras auxiliaresCentinelasCabeceras
A B C D
Laboratorio DEI
2003/04 Estructura de Datos Listas - 24
Técnica de Simplificación (i) Búsqueda en lista ordenada: evaluar dos condiciones buscar(nombreLista, valorClave) informacion
INICIO posicion nombreLista.comienzo continuar CIERTO MIENTRAS NO(listaVacia(posicion)) Y continuar) SI (clave(posicion) < valorClave) ENTONCES posicion siguiente(posicion) SI NO continuar FALSO SI(clave(posicion) = valorClave) ENTONCES DEVOLVER informacion(posicion) SI NO DEVOLVER error ese nodo no está en la lista FIN-SI FIN-SI FIN-MIENTRAS FIN
Laboratorio DEI
2003/04 Estructura de Datos Listas - 25
Centinela en listas ordenadas Centinela = nodo auxiliar al final de la lista
Para buscar un elemento:Colocar en el centinela el valor buscadoCondición de terminación: se encuentra el valor buscado o uno mayorSi se llega al centinela, el elemento no está en la lista
Ejemplo e Implementación
Laboratorio DEI
2003/04 Estructura de Datos Listas - 26
Centinelas: ejemplos Buscar(comienzo, 15, centinela, posición) Buscar(comienzo, 50, centinela, posición)
Laboratorio DEI
2003/04 Estructura de Datos Listas - 27
Técnica de simplificación (ii) Inserción en lista ordenada: caso especial
insertarPosicion (nombreLista, valorClave, valorInfo, anterior, posterior)// Coloca el nodo entre anterior y posterior. Si anterior es vacío, entonces nodo será el primer elemento de la lista, si posterior es vacío será el últimoINICIO nodo nuevoNodo(valorClave, valorInfo) asignarEnlace(nodo, posterior) SI listaVacia(anterior) ENTONCES nombreLista.comienzo nodo SI NO asignarEnlace(anterior, nodo) FIN SIFIN
Laboratorio DEI
2003/04 Estructura de Datos Listas - 28
Cabecera en listas ordenadas Cabecera = nodo auxiliar situado al principio de
la lista, cuyos contenidos (clave e info) no pertenecen a la lista
Consecuencias:No hace falta marcar comienzoNo hace falta caso especial cuando lista es vacía
Laboratorio DEI
2003/04 Estructura de Datos Listas - 29
Cabeceras: ejemplos insertarElemento (cabecera, 7)
insertarElemento (cabecera, 1)
Laboratorio DEI
2003/04 Estructura de Datos Listas - 30
Cabecera + centinela Usar el mismo nodo auxiliar como cabecera y
centinela Convertir la lista en circular
Laboratorio DEI
2003/04 Estructura de Datos Listas - 31
Otras técnicas de simplificación Inserción ordenada sin puntero al anterior
Buscar posición del primer elemento mayor que la clave a insertar, colocar un nodo nuevo detrás e intercambiar
Borrado sin puntero al anteriorBuscar posición del elemento a borrarCopiar información del siguiente a esa posiciónBorrar el siguiente
(no funciona para borrar el último elemento hay que usar centinela)
Laboratorio DEI
2003/04 Estructura de Datos Listas - 32
Estructuras Intrusivas Información de interés vs. Datos de control Cómo se almacenan:
Las estructuras intrusivas incluyen la información de interés entre sus elementosLas estructuras no intrusivas almacenan la información de interés en un área separada, incluyendo punteros a la misma
Ejemplo: mantener 2 listas (v.g., alumnos) ordenadas por distintos campos clave k1, k2, etc. (v.g., NIA y NIF)
Listas intrusivas independientesListas intrusivas con información compartidaListas no intrusivas
Laboratorio DEI
2003/04 Estructura de Datos Listas - 33
Listas intrusivas independientes Información duplicada Pueden producirse inconsistencias y se ocupa
más espacio
Laboratorio DEI
2003/04 Estructura de Datos Listas - 34
Listas intrusivas con info compartida Incorporar un puntero por cada clave de
ordenación Hay que modificar la estructura para dar acceso
a través de un nuevo campo
Laboratorio DEI
2003/04 Estructura de Datos Listas - 35
Listas no intrusivas Separar info de datos de control La incorporación de nuevas listas no afecta a la
definición de las previas