Lista (tipo de datos abstractos)

En informática , una lista o secuencia es una colección de elementos finitos en número y en un orden particular . Una instancia de una lista es una representación informática del concepto matemático de una tupla o secuencia finita .

Una lista puede contener el mismo valor más de una vez y cada aparición se considera un elemento distinto.

El término lista también se utiliza para varias estructuras de datos concretas que se pueden utilizar para implementar listas abstractas , especialmente listas enlazadas y matrices . En algunos contextos, como en la programación Lisp , el término lista puede referirse específicamente a una lista enlazada en lugar de a una matriz. En la programación basada en clases , las listas se proporcionan normalmente como instancias de subclases de una clase "lista" genérica y se recorren mediante iteradores independientes .

Muchos lenguajes de programación admiten tipos de datos de lista y tienen una sintaxis y una semántica especiales para listas y operaciones con listas. A menudo, una lista se puede construir escribiendo los elementos en secuencia, separados por comas , punto y coma y/o espacios , dentro de un par de delimitadores como paréntesis '()', corchetes '[]', llaves '{}' o corchetes angulares '<>'. Algunos lenguajes pueden permitir que los tipos de lista se indexen o se dividan como los tipos de matriz , en cuyo caso el tipo de datos se describe con mayor precisión como una matriz.

En la teoría de tipos y la programación funcional , las listas abstractas suelen definirse de forma inductiva mediante dos operaciones: nil , que produce la lista vacía, y cons , que añade un elemento al principio de una lista. ^[1]

Un flujo es el análogo potencialmente infinito de una lista. ^{[2] : §3.5}

La implementación de la estructura de datos de lista puede proporcionar algunas de las siguientes operaciones :

• crear
• prueba de vacio
• añadir elemento al principio o al final
• acceder al primer o último elemento
• acceder a un elemento por índice

Las listas normalmente se implementan como listas enlazadas (simple o doblemente enlazadas) o como matrices , generalmente de longitud variable o matrices dinámicas .

La forma estándar de implementar listas, que se originó con el lenguaje de programación Lisp , es hacer que cada elemento de la lista contenga tanto su valor como un puntero que indica la ubicación del siguiente elemento en la lista. Esto da como resultado una lista enlazada o un árbol , dependiendo de si la lista tiene sublistas anidadas. Algunas implementaciones de Lisp más antiguas (como la implementación de Lisp de Symbolics 3600) también admitían "listas comprimidas" (usando codificación CDR ) que tenían una representación interna especial (invisible para el usuario). Las listas se pueden manipular utilizando iteración o recursión . La primera suele preferirse en lenguajes de programación imperativos , mientras que la segunda es la norma en lenguajes funcionales .

Las listas se pueden implementar como árboles de búsqueda binarios autoequilibrados que contienen pares índice-valor, proporcionando acceso en tiempo igual a cualquier elemento (por ejemplo, todos los que residen en la periferia y los nodos internos que almacenan el índice del hijo más a la derecha, utilizado para guiar la búsqueda), tomando el tiempo logarítmico en el tamaño de la lista, pero mientras no cambie mucho, proporcionará la ilusión de acceso aleatorio y habilitará operaciones de intercambio, prefijo y adición en tiempo logarítmico también. ^[3]

Algunos lenguajes no ofrecen una estructura de datos de lista , pero sí ofrecen el uso de matrices asociativas o algún tipo de tabla para emular listas. Por ejemplo, Lua ofrece tablas. Aunque Lua almacena internamente listas que tienen índices numéricos como matrices, siguen apareciendo como diccionarios. ^[4]

En Lisp , las listas son el tipo de datos fundamental y pueden representar tanto código de programa como datos. En la mayoría de los dialectos, la lista de los tres primeros números primos podría escribirse como (list 2 3 5). En varios dialectos de Lisp, incluido Scheme , una lista es una colección de pares, que consta de un valor y un puntero al siguiente par (o valor nulo), formando una lista enlazada simple. ^[5]

A diferencia de una matriz , una lista puede expandirse y contraerse.

En informática, las listas son más fáciles de implementar que los conjuntos. Un conjunto finito en sentido matemático puede realizarse como una lista con restricciones adicionales; es decir, no se permiten elementos duplicados y el orden es irrelevante. Ordenar la lista acelera la determinación de si un elemento dado ya está en el conjunto, pero para garantizar el orden, se requiere más tiempo para agregar una nueva entrada a la lista. Sin embargo, en implementaciones eficientes, los conjuntos se implementan utilizando árboles de búsqueda binarios autoequilibrados o tablas hash , en lugar de una lista.

Las listas también forman la base de otros tipos de datos abstractos, incluida la cola , la pila y sus variaciones.

La lista abstracta tipo L con elementos de algún tipo E (una lista monomórfica ) se define mediante las siguientes funciones:

nulo: () → L

Contras: E × L → L

primero: L → E

resto: L → L

con los axiomas

primero (cons ( e , l )) = e

resto (cons ( e , l )) = l

para cualquier elemento e y cualquier lista l . Está implícito que

contras ( e , l ) ≠ l

contras ( e , l ) ≠ e

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

Tenga en cuenta que el primero (nil()) y el resto (nil()) no están definidos.

Estos axiomas son equivalentes a los del tipo de datos de pila abstracta .

En teoría de tipos , la definición anterior se considera más sencilla como un tipo inductivo 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 mediante la coincidencia de patrones en el constructor cons y manejando por separado el caso nil .

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

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

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

donde append se define como:

${\displaystyle {\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 definirse en términos de las operaciones return , fmap y join , con:

${\displaystyle {\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}}}$

${\displaystyle {\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 se aplican a argumentos progresivamente más profundos en cada llamada recursiva.

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

Las 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 elementos de la lista.

Busque lista en Wikcionario, el diccionario libre.

• Tipo de datos de matriz  : tipo de datos que representa una colección ordenada de elementos (valores o variables)Pages displaying short descriptions of redirect targets
• Cola  – Tipo de datos abstracto
• Conjunto  : tipo de datos abstracto para almacenar valores únicos
• Pila  – Tipo de datos abstracto
• Flujo  : secuencia de elementos de datos disponibles a lo largo del tiempo