Lista (tipo de dato abstracto)

En informática , una lista o secuencia es una colección de elementos finitos en número y en un orden determinado . Una instancia de lista es una representación informática del concepto matemático de 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.

Una estructura de lista enlazada simple, que implementa una lista con tres elementos enteros.

El término « lista» también se utiliza para referirse a diversas estructuras de datos concretas que pueden emplearse para implementar listas abstractas , especialmente listas enlazadas y arreglos . 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 un arreglo. En la programación basada en clases , las listas suelen proporcionarse como instancias de subclases de una clase genérica «lista» y se recorren mediante iteradores independientes .

Muchos lenguajes de programación admiten listas como tipos de datos y cuentan con una sintaxis y semántica especiales para listas y operaciones con listas. Una lista se puede construir escribiendo los elementos en secuencia, separados por comas , puntos y comas o espacios , entre delimitadores como paréntesis (), corchetes ([]), llaves ({}) o corchetes angulares (<>). Algunos lenguajes permiten indexar o segmentar listas como si fueran arreglos , en cuyo caso el tipo de dato se describe con mayor precisión como un arreglo.

En teoría de tipos y programación funcional , las listas abstractas se definen generalmente 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 ]}

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

Operaciones

La implementación de la estructura de datos de lista puede proporcionar algunas o todas las siguientes operaciones como primitivas de bajo nivel:

Crea una lista vacía
Comprueba si la lista está vacía.
Anteponer un elemento a la lista
Agregue un elemento al final de la lista.
obtener el primer o el último elemento de una lista
Haz que el resto de la lista pase su primer o último elemento.
Obtener un elemento por el índice de su posición en una lista.
crear una lista que contenga un único elemento dado
crear una lista que contenga los elementos dados
adjuntar dos listas
map, flatmap, filter, reduce, etc.

Implementaciones

Las listas se implementan normalmente como listas enlazadas (ya sean enlazadas simples o doblemente) o como arreglos , generalmente de longitud variable o arreglos dinámicos .

La forma estándar de implementar listas, originada en el lenguaje de programación Lisp , consiste en que cada elemento de la lista contenga tanto su valor como un puntero que indique la ubicación del siguiente elemento. Esto da como resultado una lista enlazada o un árbol , dependiendo de si la lista tiene sublistas anidadas. Algunas implementaciones antiguas de Lisp (como la implementación de Lisp del Symbolics 3600) también admitían "listas comprimidas" (mediante codificación CDR ), que tenían una representación interna especial (invisible para el usuario). Las listas se pueden manipular mediante iteración o recursión . La primera suele ser la preferida 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 binaria 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 almacenan el índice del hijo más a la derecha, utilizado para guiar la búsqueda), tomando un tiempo logarítmico en el tamaño de la lista, pero mientras no cambie mucho proporcionará la ilusión de acceso aleatorio y permitirá operaciones de intercambio, prefijo y adición también en tiempo logarítmico. ^{[ 3 ]}

Compatibilidad con lenguajes de programación

Algunos lenguajes no ofrecen una estructura de datos de lista , pero sí permiten el uso de arreglos asociativos o algún tipo de tabla para emular listas. Por ejemplo, Lua proporciona tablas. Aunque Lua almacena internamente las listas con índices numéricos como arreglos, siguen apareciendo como diccionarios. ^{[ 4 ]}

En Lisp , las listas son el tipo de dato 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 se puede escribir 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 ]}

Aplicaciones

A diferencia de un array , 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 el sentido matemático, puede representarse como una lista con restricciones adicionales: no se permiten elementos duplicados y el orden es irrelevante. Ordenar la lista acelera la comprobación de si un elemento ya está presente, pero para garantizar el orden, se requiere más tiempo para añadir una nueva entrada. Sin embargo, en implementaciones eficientes, los conjuntos se implementan mediante árboles de búsqueda binaria autoequilibrados o tablas hash , en lugar de listas.

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

Definición abstracta

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

nil: () → L

cons: E × L → L

primero: L → E

descanso: L → L

con los axiomas

primero (cons ( e , l )) = e

resto (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 ₂

Tenga en cuenta que first (nil ()) y rest (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 simplemente 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 mediante la coincidencia de patrones en el constructor cons y manejando por separado el caso nil .

La mónada de lista

El tipo de lista forma una mónada con las siguientes funciones (usando E ^* en lugar de 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{si}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{si}}\ l={\text{cons}}\,a\,l'\end{cases}}

donde agregar se define como:

{\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{si}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{si}}\ 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:

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

{\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{si}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{si}}\ 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 añadir . El elemento neutro del monoide es la lista vacía, nil . De hecho, este es el monoide libre sobre el conjunto de elementos de lista.

Véase también

Tipo de datos Array : tipo de datos que representa una colección ordenada de elementos (valores o variables). Páginas que muestran descripciones breves de destinos de redirección.
Cola – Tipo de dato abstracto
Conjunto : tipo de dato abstracto para almacenar valores distintos.
Pila – Tipo de dato abstracto
Flujo : secuencia de elementos de datos disponibles a lo largo del tiempo.

Referencias

↑ Reingold, Edward; Nievergelt, Jurg; Narsingh, Deo (1977). Algoritmos combinatorios: teoría y práctica . Englewood Cliffs, Nueva Jersey: Prentice Hall. págs. 38–41 . ISBN 0-13-152447-X.
↑ Abelson, Harold; Sussman, Gerald Jay (1996). Estructura e interpretación de programas informáticos . MIT Press.
↑ Barnett, Granville; Del Tonga, Luca (2008). "Estructuras de datos y algoritmos" (PDF) . mta.ca. Consultado el 12 de noviembre de 2014 .
^ Lerusalimschy, Roberto (diciembre de 2003). Programación en Lua (primera edición) (Primera ed.). Lua.org. ISBN 8590379817Consultado el 12 de noviembre de 2014 .
↑ Steele, Guy (1990). Common Lisp (Segunda edición). Digital Press. págs. 29–31 . ISBN 1-55558-041-6.

[1] Reingold, Edward; Nievergelt, Jurg; Narsingh, Deo (1977). Algoritmos combinatorios: teoría y práctica . Englewood Cliffs, Nueva Jersey: Prentice Hall. págs. 38–41 . ISBN 0-13-152447-X.

[2] Abelson, Harold; Sussman, Gerald Jay (1996). Estructura e interpretación de programas informáticos . MIT Press.

[3] Barnett, Granville; Del Tonga, Luca (2008). "Estructuras de datos y algoritmos" (PDF) . mta.ca. Consultado el 12 de noviembre de 2014 .

[4] Lerusalimschy, Roberto (diciembre de 2003). Programación en Lua (primera edición) (Primera ed.). Lua.org. ISBN 8590379817Consultado el 12 de noviembre de 2014 .

[5] Steele, Guy (1990). Common Lisp (Segunda edición). Digital Press. págs. 29–31 . ISBN 1-55558-041-6.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]