Lista (tipo de dato abstracto)

En ciencias de la computación, una lista o secuencia es un tipo de dato abstracto que representa una secuencia ordenada de valores, donde el mismo valor puede ocurrir más de una vez. Un caso de una lista es una representación computacional del concepto matemático de una secuencia finita. Las listas son un ejemplo básico de contenedores, cuando contienen otros valores. Si el mismo valor se repite varias veces, cada ocurrencia está considerada un elemento distinto.

Una simple estructura de lista enlazada, implementando una lista con 3 elementos enteros.

El concepto lista es también utilizado para varias estructuras de datos que puede soler implementar listas abstractas, especialmente listas enlazadas.

Muchos lenguajes de programación proporcionan soporte para tipos de dato de la lista, y tienen sintaxis especiales y semánticas para listas y operaciones de lista. Una lista a menudo puede ser construida escribiendo los elementos en secuencia, separado por comas, puntos y comas, o espacios, dentro de un par de delimitadores como paréntesis'()', corchetes'[]', tirantes '{}', o paréntesis angulares '<>'. Algunos lenguajes permiten indexación sobre las listas, similar a los array (vectores), en tal caso es más adecuado describirlas como array. En programación orientada a objetos las listas son normalmente proporcionadas como instancias de una clase "Lista" genérica, y recorridas por iteradores separados. Los tipo de datos de lista son usualmente implementados usando estructuras de datos de array o listas enlazadas, pero otras estructuras de dato pueden ser más apropiadas para algunas aplicaciones. En algunos contextos, como en programación en Lisp, el término lista se puede referir específicamente a una lista enlazada más que un array.

En teoría de tipos y programación funcional, las listas abstractas son normalmente definidas recursivamente por dos operaciones: nil que devuelve la lista vacía, y cons, el cual añade un elemento a principios de una lista.​

Operaciones

La implementación de la estructura de dato de lista puede conllevar a algunas de las operaciones siguientes:

• Un constructor para crear una lista vacía;
• Una operación para probar si una lista está vacía;
• Una operación para agregar una entidad al inicio de una lista
• Una operación para agregar una entidad al final de una lista
• Una operación para determinar el primer elemento (o la "cabeza") de una lista
• Una operación para referirse a la lista que consta de todos los componentes de una lista excepto su primero (esto es llamado "cola" de la lista.)

Implementaciones

Las listas son usualmente implementadas tanto como listas enlazadas (simple o doblemente enlazadas) o como arrays, normalmente de longitud variable o arrays dinámico.

La manera estándar de implementar listas, originanda con el lenguaje de programación Lisp, es que cada elemento de la lista contiene su valor y un puntero que indica la ubicación del elemento próximo en la lista. Esto resulta una lista enlazada o un árbol, dependiendo de si la lista tiene sublistas anidadas. Algunas implementaciones antiguas de Lisp (como Symbolics 3600) soportan "listas comprimidas" (utilizando codificación CDR) las cuales tuvieron una representación interna especial (invisible al usuario). Las listas pueden ser manipuladas utilizando iteración o recursión. La primera forma es a menudo preferida en lenguajes de programación imperativos, mientras la última es la norma en lenguajes funcionales.

Las listas pueden ser implementadas como árboles binarios de búsqueda balanceados manteniendo pares de índice valor, proporcionando acceso en el mismo tiempo a cualquier elemento

Soporte de lenguaje de programación

Algunos lenguajes no ofrecen una estructura de datos de la lista, pero ofrecen el uso de arrays asociativos o algún tipo de tabla para emular listas. Por ejemplo, Lua ofrece tablas. Aunque Lua almacena listas que tienen índices numéricos como arrays internamente, aparecen como tablas hash. ​

En Lisp, las listas son el tipo de dato fundamental y pueden representar tanto el código del programa como datos. En la mayoría de los dialectos, la lista de los primeros tres números primos podrían ser escritos como (list 2 3 5). En varios dialectos de Lisp, incluyendo Scheme, una lista es una colección de pares, constando de un valor y un puntero al par próximo (o valor nulo), haciendo una simple lista enlazada.​

Aplicaciones

Como el nombre indica, las listas pueden ser usadas para almacenar una lista de registros.

Debido a que en la informática, las listas son más fáciles de realizar que los Conjuntos, un conjunto finito en sentido matemático se puede implementar como una lista con restricciones adicionales, es decir, duplicar los elementos no está permitido y su orden es irrelevante. Si la lista está ordenada, esto acelera la determinación de si un elemento está en el conjunto, pero, a fin de garantizar el orden, se requiere más tiempo para añadir nueva entrada a la lista. En implementaciones eficientes, sin embargo, los conjuntos se implementan utilizando árboles binarios de búsqueda balanceados o tablas hash, en lugar de una list

Definición abstracta

El tipo de lista abstracto L con elementos de algún tipo E (un monomorphic lista) está definido por las funciones siguientes:

nil: () → L

cons: E × L → L

first: L → E

rest: L → L

Con los axiomas

first (cons (e, l)) = e

rest (cons (e, l)) = l

Para cualquier elemento e y cualquier lista l. Es implícito que

cons (e, l) ≠ l

cons (e, l) ≠ e

cons (e₁, l₁) = cons (e₂, l₂) si e₁ = e₂ y l₁ = l₂

Notar que first(nil()) y rest(rest()) no está definido.

Estos axiomas son equivalentes a los del tipo abstracto pila.

En teoría el tipo, la definición anterior es más sencillamente considerada como un tipo recursivo definido en términos de constructores: nil y cons. En términos algebraicos, esto se puede representar como la transformación 1 + E × L → L. first y rest se obtienen entonces por coincidencia de patrones en el constructor cons y manipulando por separado el caso nil.

La lista mónada

El tipo de lista forma una mónada con las funciones siguientes (utilizando E* más que L para representar listas monomórficas con elementos de tipo E):

${\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}$

${\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

Dónde append está definido como:

${\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}$

Alternativamente, la mónada puede ser definida en término de operaciones return, fmap y join con:

${\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

${\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

Tenga en cuenta que fmap, join, append y bind están bien definidos, ya que son aplicados a los argumentos progresivamente más profundos en cada llamada recursiva.

El tipo de lista es una mónada aditivo, con nil como el monádico cero y append como monádico suma.

Listas forman un monoide bajo la operación de anexión. El elemento de identidad del monoide es la lista vacía, nil. De hecho, este es el monoide libre sobre el conjunto de los elementos de la lista.

Véase también

• Array
• Cola
• Conjunto
• Flujo

• Datos: Q27948