Lista (tipo de datos abstracto)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Tipo de datos abstracto utilizado en la ciencia informática

En informática, una lista o secuencia es un tipo de datos abstracto que representa un número finito de valores ordenados, donde el mismo valor puede aparecer más de una vez. Una instancia de una lista es una representación informática del concepto matemático de una tupla o secuencia finita; el análogo (potencialmente) infinito de una lista es una secuencia. Las listas son un ejemplo básico de contenedores, ya que contienen otros valores. Si el mismo valor aparece varias veces, cada aparición se considera un elemento distinto.

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

El nombre lista también se usa para varias estructuras de datos concretas que se pueden usar para implementar listas abstractas, especialmente listas enlazadas y arreglos. En algunos contextos, como en la programación de Lisp, el término lista puede referirse específicamente a una lista enlazada en lugar de una matriz. En la programación basada en clases, las listas suelen proporcionarse como instancias de subclases de una "lista" genérica. clase, y atravesado a través de iteradores separados.

Muchos lenguajes de programación brindan soporte para tipos de datos de lista y tienen una sintaxis y semántica especiales para listas y operaciones de lista. A menudo se puede construir una lista 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 dividan como 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 final. principio de una lista.

Operaciones

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

un constructor para crear una lista vacía;
una operación para probar si una lista está vacía o no;
una operación para prepennder a una entidad a una lista
una operación para pasar una entidad a una lista
una operación para determinar el primer componente (o la "cabeza") de una lista
una operación para referirse a la lista que consiste en todos los componentes de una lista excepto por su primera (esto se llama "la cola" de la lista.)
una operación para acceder al elemento en un índice dado.

Implementaciones

Las listas normalmente se implementan como listas enlazadas (ya sea con enlaces simples o dobles) o como arreglos, generalmente de longitud variable o arreglos dinámicos.

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 indique la ubicación del siguiente elemento en la lista. Esto da como resultado una lista vinculada o un árbol, dependiendo de si la lista tiene sublistas anidadas. Algunas implementaciones Lisp más antiguas (como la implementación Lisp de Symbolics 3600) también admitían "listas comprimidas" (usando codificación CDR) que tenía una representación interna especial (invisible para el usuario). Las listas se pueden manipular mediante iteración o recursividad. El primero suele preferirse en los lenguajes de programación imperativos, mientras que el segundo es la norma en los lenguajes funcionales.

Las listas se pueden implementar como árboles de búsqueda binarios autoequilibrados que contienen pares de valores de índice, lo que brinda acceso en el mismo tiempo a cualquier elemento (por ejemplo, todos los que residen en la periferia y los nodos internos que almacenan el índice secundario 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á las operaciones de intercambio, prefijo y adición en logarítmico el tiempo también

Soporte de lenguaje de programación

Algunos lenguajes no ofrecen una estructura de datos de lista, pero ofrecen el uso de matrices asociativas o algún tipo de tabla para emular listas. Por ejemplo, Lua proporciona tablas. Aunque Lua almacena internamente listas que tienen índices numéricos como matrices, aún aparecen como diccionarios.

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 individualmente.

Aplicaciones

Como su nombre lo indica, las listas se pueden usar para almacenar una lista de elementos. Sin embargo, a diferencia de las matrices tradicionales, las listas pueden expandirse y reducirse, y se almacenan dinámicamente en la memoria.

En informática, las listas son más fáciles de implementar que los conjuntos. Un conjunto finito en el sentido matemático se puede realizar como una lista con restricciones adicionales; es decir, los elementos duplicados no están permitidos 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, como la cola, la pila y sus variaciones.

Definición abstracta

La lista abstracta tipo 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

Descanse: L → L

con los axiomas

primero (conservadores)e, l) = e

(conservadores)e, l) = l

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

conse, l) l

conse, l) e

conse₁, l₁.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 la 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 luego se obtienen mediante la coincidencia de patrones en el constructor cons y manejando por separado el caso nil.

La mónada 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 Ato A^{*}=amapsto {text{cons}},a,{text{nil}}

{text{bind}}colon A^{*}to (Ato B^{*})to B^{*}=lmapsto fmapsto {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}}

donde append se define 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 definirse en términos de operaciones return, fmap y join, con:

{text{fmap}}colon (Ato B)to (A^{*}to B^{*})=fmapsto lmapsto {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^{*}=lmapsto {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 aplica 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 append. 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.

Contenido relacionado

Más resultados...