PDF de programación - Tema 4.3. Tipos de datos lineales. Listas - Estructuras de Datos y Algoritmos

Estructuras de Datos 

y Algoritmos

Tema 4.3. Tipos de datos lineales.

Listas

Prof. Dr. P. Javier Herrera

Contenido

•
•
•
•
•
•
•

Listas: Conceptos generales
Operaciones básicas
Especificación algebraica
Implementación dinámica
Extensión de operaciones
Extensión de la especificación algebraica
Extensión de la implementación dinámica

Tema 4.3. Listas

22

Listas: Conceptos generales

•

•

•

•

•

Vivimos rodeados de listas: la lista de la compra, la lista de regalos de boda, la lista de libros 
para el próximo curso, etc., siendo el denominador común de todas estas listas el establecer 
una ordenación entre sus elementos.

Las listas son las estructuras de datos lineales más flexibles, puesto que su única 
característica es imponer un orden entre los elementos almacenados en ellas.

Según este criterio, las pilas y las colas serían casos particulares de listas, donde se ha 
restringido la forma de acceso a la estructura.

No existe una visión unánime de las listas como TAD, con un conjunto básico de operaciones.

Se trata de un tipo de datos parametrizado, donde el comportamiento de las operaciones 
sobre los valores del tipo lista es independiente de la naturaleza de los elementos que la 
componen.

Tema 4.3. Listas

3
3

Operaciones básicas

•

Un posible TAD de las listas cuenta con las siguientes operaciones:

– crear la lista vacía,
– generar una lista unitaria formada por un elemento dado,
– añadir un elemento por la izquierda,
– añadir un elemento por la derecha,
– consultar el elemento más a la izquierda,
– consultar el elemento más a la derecha,
– eliminar el elemento más a la izquierda,
– eliminar el elemento más a la derecha,
– determinar si una lista es vacía,
– concatenar dos listas, y
– calcular la longitud de una lista.

Tema 4.3. Listas

4
4

Especificación algebraica

especificación LISTAS[ELEM]
usa BOOLEANOS, NATURALES
tipos lista
operaciones

[ ]
_ : _
[ _ ]
_ # _
izquierdo
elim-izq
derecho
elim-der
es-lista-vacía?
_ ++ _
longitud

:
: elemento lista
: elemento
: lista elemento
: lista
: lista
: lista
: lista
: lista
: lista lista
: lista

{ constructora }
{ constructora }

→ lista
→ lista
→ lista
→ lista
→p elemento
→p lista
→p elemento
→p lista
→ bool
→ lista
→ nat

Tema 4.3. Listas

5
5

Especificación algebraica

variables

: elemento

e, f
x, y, z : lista

ecuaciones

= e : [ ]

[e]
x # e = x ++ [e]

izquierdo([ ])
izquierdo(e : x) = e

= error

elim-izq([ ])
elim-izq(e : x)

= error
= x

= error

derecho([ ])
derecho(e : [ ]) = e
derecho(e : f : x) = derecho(f : x)

Tema 4.3. Listas

6
6

Especificación algebraica

= error

elim-der([ ])
elim-der(e : [ ]) = [ ]
elim-der(e : f : x) = e : elim-der(f : x)

es-lista-vacía?([ ]) = cierto
es-lista-vacía?(e : x) = falso

[ ] ++ y
(e : x) ++ y

= y
= e : (x ++ y)

longitud([ ])
longitud(e : x)

= 0
= 1 + longitud(x)

fespecificación

•

También podemos considerar como constructoras la operación que crea la lista vacía y la que 
añade un elemento por la derecha (situación simétrica a la anterior); o bien elegir la lista 
vacía, la operación de construcción de la lista unitaria y la operación de concatenación.

Tema 4.3. Listas

7
7

Implementación dinámica

•

•

•

Los elementos de una lista se representan mediante una sucesión de nodos doblemente 
enlazados: cada nodo, además del valor del elemento concreto almacenado, contiene 
enlaces al nodo siguiente y al anterior en la sucesión.

La ventaja de tener estos dobles enlaces es que así se pueden eliminar elementos por ambos 
extremos de la lista con un coste en tiempo constante.

Una lista será un registro con un campo que guarda la longitud de la lista y enlaces a los 
nodos más a la izquierda y más a la derecha de la sucesión.

Tema 4.3. Listas

8
8

Implementación dinámica

tipos

enlace-lista
nodo-lista

= puntero a nodo-lista
= reg

valor : elemento
sig, ant : enlace-lista

lista

freg
= reg

longitud : nat
izquierdo, derecho : enlace-lista

freg

ftipos

Tema 4.3. Listas

9
9

Implementación dinámica

•

La lista vacía no tiene elementos, por lo que la longitud es cero, y como no hay elementos, 
los punteros izquierdo y derecho son nulos.

fun lista-vacía() dev l : lista

 1O
{ }

l.longitud := 0
l.izquierdo := nil
l.derecho := nil

ffun

•

Una lista es vacía cuando los punteros (uno o ambos, pues ambas condiciones son 
equivalentes) son nulos pues eso significa que no hay nodos en la estructura.

fun es-lista-vacía?(l : lista) dev r : bool

r := (l.izquierdo = nil)

 1O
{ }

ffun

Tema 4.3. Listas

10
10

Implementación dinámica

•

Añadir un elemento por la izquierda consiste en reservar memoria para un nuevo nodo, 
almacenar en él el nuevo elemento, y enlazarlo con la estructura, distinguiendo el caso en el 
que la lista inicial sea vacía. En cualquier caso la longitud de la lista aumenta en una unidad.

proc añadir-izq(e e : elemento, l : lista)
var p : enlace-lista

 1O
{ }

reservar(p)
p↑.valor := e ; p↑.ant := nil
si l.izquierdo = nil entonces

p↑.sig := nil ; l.derecho := p

si no

{ l es vacía }

p↑.sig := l.izquierdo ; (l.izquierdo)↑.ant := p

fsi
l.izquierdo := p
l.longitud := l.longitud + 1

fproc

Tema 4.3. Listas

11
11

Implementación dinámica

•

Añadir un elemento por la derecha es la operación simétrica.

proc añadir-der(l : lista, e e : elemento)
var p : enlace-lista

 1O
{ }

reservar(p)
p↑.valor := e ; p↑.sig := nil
si l.derecho = nil entonces

p↑.ant := nil ; l.izquierdo := p

si no

p↑.ant := l.derecho ; (l.derecho)↑.sig := p

fsi
l.derecho := p
l.longitud := l.longitud + 1

fproc

Tema 4.3. Listas

12
12

Implementación dinámica

•

Construir una lista unitaria a partir de un elemento dado consiste en crear una nueva lista 
con un único nodo que es apuntado tanto por izquierdo como por derecho. La longitud es 1.

fun unitaria(e : elemento) dev l : lista
var p : enlace-lista

 1O
{ }

reservar(p)
p↑.valor := e
p↑.ant := nil ; p↑.sig := nil
l.izquierdo := p ; l.derecho := p
l.longitud := 1

ffun

Tema 4.3. Listas

13
13

Implementación dinámica

•

•

El elemento más a la izquierda de una lista no vacía se obtiene accediendo al campo valor del 
nodo apuntado por izquierdo. Si la lista es vacía se produce un mensaje de error. 
La operación derecho es simétrica.

fun izquierdo(l : lista) dev e : elemento

 1O
{ }
si l.izquierdo = nil entonces error(Lista vacía)
si no e := (l.izquierdo)↑.valor
fsi

ffun

fun derecho(l : lista) dev e : elemento

 1O
{ }
si l.derecho = nil entonces error(Lista vacía)
si no e := (l.derecho)↑.valor
fsi

ffun

Tema 4.3. Listas

14
14

Implementación dinámica

•

Para eliminar el izquierdo se libera el primer nodo de la estructura, dejándola bien enlazada. 
Las operaciones derecho y elim-der son simétricas a las dos anteriores.

proc elim-izq(l : lista)
var p : enlace-lista

 1O
{ }

si l.izquierdo = nil entonces error(Lista vacía)
si no

p := l.izquierdo ; l.izquierdo := p↑.sig
si l.izquierdo = nil entonces l.derecho := nil
si no (l.izquierdo)↑.ant := nil
fsi
l.longitud := l.longitud − 1
liberar(p)

fsi
fproc

Tema 4.3. Listas

15
15

Implementación dinámica

•

La operación elim-der es simétrica.

proc elim-der(l : lista)
var p : enlace-lista

 1O
{ }

si l.derecho = nil entonces error(Lista vacía)
si no

p := l.derecho ; l.derecho := p↑.ant
si l.derecho = nil entonces l.izquierdo := nil
si no (l.derecho)↑.sig := nil
fsi
l.longitud := l.longitud − 1
liberar(p)

fsi
fproc

Tema 4.3. Listas

16
16

Implementación dinámica

•

La lista resultado de concatenar las dos listas que recibe como argumento, comienza siendo 
una copia de la primera lista. A continuación se recorre la sucesión de nodos de la segunda 
lista, añadiendo cada elemento por la derecha a la lista resultado. El coste en tiempo de 
concatenar es lineal respecto a la suma de las longitudes  de las listas concatenadas.

 
y
O
{ }


longitud

 
x



longitud

fun concatenar(x, y : lista) dev z : lista
var p : enlace-lista

z := lista-vacía() ; p := x.izquierdo
mientras p ≠ nil hacer

añadir-der(z, p↑.valor) ; p := p↑.sig

fmientras
p := y.izquierdo
mientras p ≠ nil hacer

añadir-der(z, p↑.valor) ; p := p↑.sig

fmientras

ffun

Tema 4.3. Listas

17
17

Implementación dinámica

•

•

Si se implementara la operación concatenar mediante un procedimiento, se podría conseguir 
un coste constante modificando el primer argumento para que también fuera el resultado, 
para lo cual bastaría encadenar el nodo derecho de x con el izquierdo de y, y sumar las dos 
longitudes.

La longitud de una lista se obtiene consultando el campo correspondiente, con un coste en 
tiempo constante.

 1O
fun longitud(l : lista) dev n : nat { }

n := l.longitud

ffun

Tema 4.3. Listas

18
18

Extensión de operaciones

•

Extender la especificación para considerar las siguientes operaciones:

– determinar si un elemento aparece en una lista,
– localizar la posición de un elemento (devolviendo 0 si el elemento no está),
– calcular el número de repeticiones de un elemento,
– eliminar todas las apariciones de un elemento,
– determinar si dos listas son iguales,
– determinar si una lista es capicúa,
– consultar el elemento en una posición,
– insertar un elemento en una posición,
– eliminar el elemento en una posición, y
– modificar el elemento en una posición.

Tema 4.3. Listas

19
19

Extensión de la especificación algebraica

especificación LISTAS+[ELEM=]
usa LISTAS[ELEM=], NATURALES, BOOLEANOS
operaciones

está?
posición
repeticiones
eliminar
_ == _
es-capicúa?
_ [ _ ]
insertar
eliminar
modificar

variables

: elemento lista → bool
: elemento lista → nat
: elemento lista → nat
: elemento lista → lista
: lista lista
→ bool
→ bool
: lista
→p elemento
: lista nat
: lista nat elemento →p lista
→p