Lista (informática)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de julio de 2020; las comprobaciones requieren 2 ediciones .

En informática , una lista ( en inglés list ) es un tipo de dato abstracto , que es un conjunto ordenado de valores en el que un determinado valor puede aparecer más de una vez. Una instancia de una lista es una implementación informática del concepto matemático de una secuencia finita . Las instancias de valores en una lista se denominan elementos de la lista ( inglés item, entry o element ); si el valor aparece varias veces, cada aparición se considera un elemento independiente.

El término lista también se refiere a varias estructuras de datos específicas que se utilizan en la implementación de listas abstractas, especialmente listas enlazadas .

Definición

Usando la notación del método de construcción orientado sintácticamente de C. Hoare , la definición de una lista se puede escribir de la siguiente manera:

Lista(A)=NIL+(A\veces Lista(A))

prefijo={\text{constructor}}

Lista (A)

head,tail={\text{selectores}}

Lista (A)

null,nonnull={\text{predicados}}

Lista (A)

NIL,nonNIL={\text{partes}}

Lista (A)

La primera línea de esta definición significa que la lista de elementos del tipo (digamos: "lista encima ") es la unión discriminada de la lista vacía y el producto cartesiano del átomo del tipo con la lista encima . Para crear listas, se utilizan dos constructores (la segunda línea de la definición), el primero de los cuales crea una lista vacía y el segundo, uno no vacío, respectivamente. Está bastante claro que el segundo constructor recibe algún átomo y una lista como parámetros de entrada, y devuelve una lista, cuyo primer elemento es el átomo original, y el resto son los elementos de la lista original. Es decir, el átomo se antepone a la lista, razón por la cual se le da ese nombre al constructor. La lista vacía no es un átomo y, por lo tanto, no puede tener un prefijo. Por otro lado, una lista vacía es el elemento nulo para la construcción de listas, por lo que cualquier lista contiene una lista vacía al final: la construcción comienza con ella. $A$ $A$ $A$ $A$ $[]$

La tercera línea define los selectores de la lista, es decir, las operaciones para acceder a los elementos dentro de la lista. El selector toma una lista como entrada y devuelve el primer elemento de esta lista, es decir, el tipo del resultado es type . Este selector no puede recibir una lista vacía como entrada; en este caso, el resultado de la operación no está definido. El selector devuelve la lista obtenida de la entrada como resultado de cortarle la cabeza (el primer elemento). Este selector tampoco puede aceptar una lista vacía como entrada, ya que en este caso el resultado de la operación es indefinido. Usando estas dos operaciones, puede obtener cualquier elemento de la lista. Por ejemplo, para obtener el tercer elemento de la lista (si hay uno), debe aplicar el selector dos veces seguidas y luego aplicar el selector . En otras palabras, para obtener el elemento de la lista que está en posición (comenzando por el primer elemento, como es habitual en la programación), debe aplicar el selector una vez y luego aplicar el selector . $cabeza$ $A$ $cola$ $cola$ $cabeza$ $norte$ ${\ estilo de visualización 0}$ $norte$ $cola$ $cabeza$

La cuarta línea de la definición describe predicados de lista , es decir, funciones que devuelven un valor booleano dependiendo de algunas condiciones. El primer predicado devuelve un valor si la lista dada está vacía. El segundo predicado funciona a la inversa. Finalmente, la quinta línea describe las partes de la lista, que, como ya se mencionó, son las listas vacías y no vacías. $verdadero$

Propiedades

La estructura de datos definida de esta manera tiene algunas propiedades:

El tamaño de la lista es el número de elementos que contiene, excluyendo el último elemento "nulo", que es, por definición, una lista vacía.
El tipo de elementos es el mismo tipo sobre el que se construye la lista; todos los elementos de la lista deben ser de este tipo. $A$
Ordenado : la lista se puede ordenar de acuerdo con algunos criterios de clasificación (por ejemplo, valores enteros ascendentes, si la lista consta de números enteros).
Accesibilidad : algunas listas, según la implementación, pueden proporcionar al programador selectores para acceder directamente al elemento numerado.
Comparabilidad : las listas se pueden comparar entre sí para determinar la correspondencia y, según la implementación, la operación de comparación de listas puede usar diferentes tecnologías.

Las listas se utilizan para almacenar conjuntos de elementos del mismo tipo. Dichos elementos se pueden ordenar para su uso en funciones de búsqueda o funciones para insertar rápidamente nuevos elementos en una lista.

Listas en lenguajes de programación

Lenguajes funcionales

Las listas en lenguajes funcionales son una estructura fundamental. La mayoría de los lenguajes funcionales tienen funciones integradas para trabajar con listas, como obtener la longitud de la lista, la cabeza (el primer elemento de la lista), la cola (la parte de la lista que sigue al primer elemento), aplicando una función a cada elemento de la lista ( Mapa ), plegando la lista , etc.

Lenguaje Haskell El Lenguaje Lisp

Idiomas imperativos

Véase también

Tipos de datos
Ininterpretable	Un poco Picar Byte qubit Tratar Rasgo Palabra
Numérico	Entero punto fijo punto flotante Racional Complejo Largo intervalo
Texto	Simbólico Cuerda
Referencia	Dirección Enlace Puntero Envoltura
Compuesto	Tipo de dato algebraico ( genérico ) Clase Tipo-producto ( Escribir tupla estructura ) Un objeto Consolidación ( etiquetado ) Par ordenado
resumen	formación Lista Giro Pila Matriz asociativa (pantalla, mapa ) Un montón de multiconjunto Escribe Grafico
Otro	Lógico Más bajo Más alto Polimórfico Funcional enumerable Recopilación Excepción Género ( Metaclase ) Monada Semáforo Caudal vacío
Temas relacionados	tipo de datos abstractos tipo primitivo Estructura de datos Genérico variable de tipo Interfaz Constructor (OOP) Constructor (FP) constructor de tipos Tipo de fundición Prototipo sistema de tipos

Estructuras de datos
Liza	formación lista enlazada simple lista doblemente enlazada lista de pases
Árboles	árbol B Árbol de búsqueda binario árbol AVL árbol rojo-negro montón
cuenta	Gráfico dirigido Gráfico Acíclico Dirigido Diagrama de decisión binaria Hipergrafo
Otro	Tabla de picadillo Pila