Tema 4: La estructura de datos ListaEstructura de DatosIngeniera de Informtica

TAD ListaLISTA = coleccin de elementos homogneos entre los que existe una relacin linealCada elemento de la lista, a excepcin del primero, tiene un nico predecesorCada elemento de la lista, a excepcin del ltimo, tiene un nico sucesorNodos y enlaces

Listas: descripcin lgicaOrden de nodos afecta a la funcin de accesoSegn orden de insercinSegn clave

EjemploLista de calificaciones ::= + {}::= + + + + +

Listas: descripcin lgicaListas ArraysListas son flexibles y permiten cambio de implementacinOperacionesInsertar, Borrar, Modificar, etc.Tipos de listasSimplesOrdenadasPilasColasDoblemente enlazadas (LDE)Circulares

ImplementacionesEstticaDinmicaEnlazadaSecuencial

U

N

G

i =min+1+2.........max

posicin = i

elem[i] =

tamao = 3

4

G

N

5

U

0

i =12 3 4 5 max

posicin = i

elem[i] =

tamao = 3

Texto

I

U

N

G

i =12345678

posicin = i

elem[i] =

tamao = 4max = 4

T

O

N

S

Vector original

tamao = 3max = 8

Vector ampliado

G

I

U

N

S

null

posicin

tamao = 5

Listas SimplesLista Simple = coleccin de elementos homogneos cuya relacin lineal es determinada por la posicin del elemento en la listaComienzo + Enlace al siguiente ( puntero)

Definicin: ::= + {} ::= + ::= {} ::= ( | NULL) :: =

TAD Lista Simple: operacionesasignarInfo(referenciaNodo, valorInformacion)asignarEnlace(referenciaNodo, valorEnlace) Modificacin de los nodosinfo(referenciaNodo) Informacionsiguiente(referenciaNodo) enlaceAcceso a los nodosrecorrer(nombreLista) Recorrido de la listabuscar(nombreLista, dato) informacionbuscar(nombreLista, dato) referenciaNodopertenece(nombreLista,informacion) Booleanoborrar(nombreLista, valorInfo) Borrado de nodosinsertar(nombreLista, valorInfo, posicion)insertar(nombreLista, valorInfo)listaVacia(nombreLista) BooleanolistaVacia(referenciaNodo) BooleanolistaLlena(nombreLista) Booleano Comprobacin del estado crearLista (nombreLista)Creacin de una listaInsercin de nodosBsqueda de un nodo

Listas SimplesAclaraciones a las operaciones:listaLlena slo tiene sentido si lista es acotadaacceso y modificacin sern mtodos get y putEjemplo y pseudocdigoinsertar (nombreLista, valorInfo, posicin)insertar (nombreLista, valorInfo)borrar (nombreLista, valorInfo)buscar (nombreLista, dato) informacinrecorrer (nombreLista)Insercin: casos

Listas OrdenadasLa posicin de cada nodo viene determinada por el valor de uno o ms campos obligatorios de informacin del nodo denominados claveNo se permite tener dos nodos con la misma clave

Definicin ::= + {} ::= ::= ( | NULL) ::= + + ::= {} ::= {}

TAD Lista Ordenada: operacionesasignarClave(referenciaNodo, valorClave)asignarInfo(referenciaNodo, valorInformacion)asignarEnlace(referenciaNodo, valorEnlace) Modificacin de los nodosclave(referenciaNodo) Claveinfo(referenciaNodo) Informacionsiguiente(referenciaNodo) enlaceAcceso a los nodosrecorrer(nombreLista Recorrido de la listabuscar(nombreLista, valorClave) Informacionbuscar(nombreLista, valorClave)ReferenciaNodopertenece(nombreLista,valorClave) Booleanoborrar(nombreLista, valorClave)Borrado de nodosinsertar(nombreLista, valorClave, valorInfo)listaVacia(nombreLista) BooleanolistaVacia(referenciaNodo) BooleanolistaLlena(nombreLista) Booleano Comprobacin del estado crearLista (nombreLista)Creacin de una listaInsercin de nodosBsqueda de un nodo

PilasPila = coleccin ordenada de elementos homogneos en la que slo se pueden aadir y eliminar elementos por el principio de la misma (cabecera) filosofa LIFO

Definicin ::= + {} ::= ::= ( | NULL) ::= + ::= {}

TAD Pila: operacionespop(nombrePila) informacionExtraccin de nodospush(nombrePila, valorInfo)Insercin de nodospilaVacia(nombrePila) BooleanopilaLlena(nombrePila) BooleanoComprobacin del estado crearPila (nombrePila)Creacin de pilaasignarInfo(referenciaNodo, valorInformacion)asignarEnlace(referenciaNodo, valorEnlace)Modificacin de los nodosinfo(referenciaNodo) Informacionsiguiente(referenciaNodo) Enlace Acceso a los nodos cabecera(nombrePila) informacionAcceso a la cabecera** Opcional: Accede a la cabecera sin eliminarla

TAD Pila: ejemplos de aplicacin Vuelta atrs en un navegador web

Comando undo en un editor

Secuencia de mtodos 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 = 6foo PC = 3 j = 5 k = 6main PC = 2 i = 5 Cuando se invoca un mtodo, se inserta en la pila una nueva entrada

Por cada mtodo se guardan:variables localesvalor devueltocontador de programa

Cuando el mtodo finaliza se saca ese elemento de la pila y se devuelve el control al mtodo que est en la cabecera

ColasCola = coleccin ordenada de elementos homogneos en la que slo se pueden aadir elementos por el final y se eliminan por el principio (frente) filosofa FIFO

Definicin ::= + + {} ::= ::= ( | NULL) ::= ::= + < informacion > ::= {}

TAD Cola: operacionesdesencolar(nombreCola) informacionExtraccin de nodosencolar(nombreCola, valorInfo)Insercin de nodoscolaVacia(nombreCola) BooleanocolaLlena(nombreCola) BooleanoComprobacin del estado crearCola (nombreCola)Creacin de colaasignarInfo(referenciaNodo, valorInformacion)asignarEnlace(referenciaNodo, valorEnlace)Modificacin de los nodosinfo(referenciaNodo) Informacionsiguiente(referenciaNodo) Enlace Acceso a los nodos cabecera(nombreCola) informacionAcceso a la cabecera** Opcional: Accede a la cabecera sin eliminarla

TAD Cola: casos particularesColas circularesImplementacin esttica como arrayReferencia al primero y al ltimoAritmtica mdulo C (Capacidad de la cola)Llevar la cuenta del nmero de elementos

TAD Cola: casos particularesColas de prioridad

TAD Cola: ejemplos de aplicacinListas de esperaAcceso a recursos compartidos dedicados (v.g., impresoras)Multiprogramacin de la CPU

Listas Doblemente EnlazadasRelacin lineal en ambos sentidosEnlace a predecesor y antecesor en cada nodoRecorrido puede ser en ambos sentidosPueden ser simples u ordenadas

Definicin: ::= + {} :: = ::= ( | NULL) ::= + + ::= ::= ::= {}

LDE: operaciones

Acceso a los nodos info(referenciaNodo) Informacionanterior(referenciaNodo) enlacesiguiente(referenciaNodo) enlace Modificacin de los nodos asignarInfo(referenciaNodo, valorInformacion)asignarAnterior(referenciaNodo, valorEnlace)asignarSiguiente(referenciaNodo, valorEnlace)

Tcnicas de SimplificacinAlgunos elementos (principio y final) se tratan como casos especiales al implementar las operacionesRediseo de estructuras para que los elementos terminales se traten igual que el restoEstructuras auxiliaresCentinelasCabecerasABCD

Tcnicas de Simplificacin (i)Bsqueda 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

Centinela en listas ordenadasCentinela = nodo auxiliar al final de la lista

Para buscar un elemento:Colocar en el centinela el valor buscadoCondicin de terminacin: se encuentra el valor buscado o uno mayorSi se llega al centinela, el elemento no est en la listaEjemplo e Implementacin

Centinelas: ejemplosBuscar(comienzo, 15, centinela, posicin)Buscar(comienzo, 50, centinela, posicin)

Tcnicas de simplificacin (ii)Insercin en lista ordenada: caso especialinsertarPosicion (nombreLista, valorClave, valorInfo, anterior, posterior) // Coloca el nodo entre anterior y posterior. Si anterior es vaco, entonces nodo ser el primer elemento de la lista, si posterior es vaco ser el ltimo INICIO nodo nuevoNodo(valorClave, valorInfo) asignarEnlace(nodo, posterior) SI listaVacia(anterior) ENTONCES nombreLista.comienzo nodo SI NO asignarEnlace(anterior, nodo) FIN SI FIN

Cabecera en listas ordenadasCabecera = 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 vaca

Cabeceras: ejemplosinsertarElemento (cabecera, 7)

insertarElemento (cabecera, 1)

Cabecera + centinelaUsar el mismo nodo auxiliar como cabecera y centinelaConvertir la lista en circular

Otras tcnicas de simplificacinInsercin ordenada sin puntero al anteriorBuscar posicin del primer elemento mayor que la clave a insertar, colocar un nodo nuevo detrs e intercambiar

Borrado sin puntero al anteriorBuscar posicin del elemento a borrarCopiar informacin del siguiente a esa posicinBorrar el siguiente(no funciona para borrar el ltimo elemento hay que usar centinela)