Estructuras de datos y algoritmos - LISTA

En la informática, una lista es un tipo de dato abstracto TDA que consiste en la colección lineal de elementos. Una manera más formal de definir a una lista sería como una secuencia de cero o más elementos de un tipo determinado.

a1, a2...,aN

Donde N >= 0 y cada ai es de un sólo tipo. 
Al número n de elementos se le llama longitud 
de la lista.    

Al suponer n >= 1, se dice que ai es el primer elemento y an el último elemento. Si n = 0 se tiene una lista vacía, es decir, que no tiene elementos.
Una propiedad importante de mencionar acerca del TDA lista es que sus elementos pueden estas ordenados en forma lineal de acuerdo con sus posiciones en la misma. Se dice que a, precede a ai+1 para i = 1, 2,...n-1, y que ai sucede a ai-1 para i = 2, 3,..., n. Se dice que el elemento ai está en la posición i. Es conveniente mencionar también la existencia de una posición que sucede a la del último elemento de la lista. La función Fin(L) devolverá la posición que sigue a la posición n en una lista L de n elementos. Obsérvese que la posición Fin(L), con respecto al principio de la lista, está a una distancia que varía conforme la lista crece o se reduce, mientras que las demás posiciones guardan una distancia fija con resecto al principio de la lista.

Operaciones esenciales de una LISTA

• L es una lista de objetos de tipo type_data
• x es un objeto de tipo type_data
• p es de tipo posición

1. INSERTA (x, p, L). Esta función inserta x en la poscición p de la lista L, pasando los elementos de la posición p y siguientes a la posición inmediata posterior. Esto quiere decir que si L es a1, a2, ..., an, se convierte en a1, a2, ..., ap-1, x, ap...an. Si p es FIN(L), entonces L se convierte en a1, a2, ..., an, x. Si la lista L no tiene posición p, el resultado es indefinido.

2. LOCALIZA(x, L). Esta función devuelve la posición de x en la lista L. Si x figura más de una vez en L, la posición de la primera aparición de x es la que se devuelve. Si x no figura en la lista, entonces se devuelve FIN(L).

3. RECUPERA(p, L). Esta función devuelve el elemento que está en la posición p de la lista L. El resultado no está definido si p = FIN(L) o si L no tiene posición p. Obsérvese que si se utiliza RECUPERA, los elementos deben ser de un tipo que pueda ser devuelto por una función. No obstante, en la práctica siempre es posible modificar RECUPERA para devolver un apuntador a un objeto de tipo type_data.

4. SUPRIME(p, L). Esta función elimina el elemento en la posición p de la lista L. Si L es a1, a2, ..., an, L se convierte en a1, a2, ..., ap-1, ap+1, ..., an. El resultado no está definido si L no tiene posición p o si p = FIN(L)

5. SIGUIENTE(p, L) y ANTERIOR(p, L) devuelven las posiciones siguientes y anterior , respectivamente, a p en la lista L. Si p es la última posición de L, SIGUIENTE(p, L) = FIN(L). SIGUIENTE no está definida si p es FIN(L). ANTERIOR no está definida si p es 1. Ambas funciones están indefinidas cuando L no tiene posición p.

6. ANULA(L). Esta función ocasiona que L se convierta en la lista vacía y devuelva la posición FIN(L).

7. PRIMERO(L). Esta función devuelve la primera posición de la lista L. Si L está vacía, la posición _FIN(L).

8. IMPRIME_LISTA(L). Imprime los elementos de L en su orden de aparición en la lista.

Implementación

Debido a que las listas se pueden representar como arreglos o como apuntadores, será en otro post que se extienda la explicación detallada de la codificación.

Referencias

1. Aho, Hopcroft, Ullman. (1988). Estructuras de datos y algoritmos. Mexico: Pearson.
2. Imágen 1