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 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 . [1] : §3.5 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.
La lista de nombres también se usa para varias estructuras de datos concretas que se pueden usar 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 generalmente se proporcionan como instancias de subclases de una clase de "lista" genérica y se recorren mediante iteradores separados .
Muchos lenguajes de programación brindan soporte para tipos de datos de listas y tienen una sintaxis y semántica especiales para listas y operaciones de listas. 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 listas se indexen o dividan como tipos de matrices , en cuyo caso el tipo de datos se describe con mayor precisión como una matriz.
En teoría de tipos y programación funcional , las listas abstractas generalmente se definen inductivamente mediante dos operaciones: nil, que produce la lista vacía, y cons , que agrega un elemento al principio de una lista. [2]
La implementación de la estructura de datos de la lista puede proporcionar algunas de las siguientes operaciones :
Las listas generalmente se implementan como listas enlazadas (ya sea simple o doblemente enlazadas) o como matrices , generalmente de longitud variable o matrices dinámicas .
La forma estándar de implementar listas, que se origina en 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ían una representación interna especial (invisible para el usuario). Las listas se pueden manipular mediante iteración o recursividad . El primero suele ser el preferido 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 í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 secundario más a la derecha, utilizado para guiar la búsqueda). , tomar el tiempo logarítmico en el tamaño de la lista, pero siempre que no cambie mucho, proporcionará la ilusión de acceso aleatorio y también permitirá operaciones de intercambio, prefijo y adición en tiempo logarítmico. [3]
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, todavía aparecen 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), lo que forma una lista enlazada individualmente. [5]
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 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 determinado ya está en el conjunto, pero para garantizar el orden, se necesita 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 o tablas hash autoequilibrados , en lugar de una lista.
Las listas también forman la base para 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:
con los axiomas
para cualquier elemento e y cualquier lista l . Está implícito que
Tenga en cuenta que primero (nil ()) y 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 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. primero y el resto se obtienen mediante la coincidencia de patrones en el constructor de contras y manejando por separado el caso nulo .
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 ):
donde anexar se define como:
Alternativamente, la mónada puede definirse en términos de operaciones return , fmap y join , con:
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 agregado como suma monádica.
Las listas forman un monoide bajo la operación de agregar . 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.
