Lista (tipo de dados abstratos) - List (abstract data type)

Na ciência da computação , uma lista ou sequência é um tipo de dado abstrato que representa um número finito de valores ordenados , onde o mesmo valor pode ocorrer mais de uma vez. Uma instância de uma lista é uma representação de computador do conceito matemático de uma tupla ou sequência finita ; o análogo (potencialmente) infinito de uma lista é um fluxo . As listas são um exemplo básico de contêineres , pois contêm outros valores. Se o mesmo valor ocorrer várias vezes, cada ocorrência será considerada um item distinto.

Uma estrutura de lista unida, implementando uma lista com três elementos inteiros.

A lista de nomes também é usada para várias estruturas de dados concretas que podem ser usadas para implementar listas abstratas , especialmente listas vinculadas e matrizes . Em alguns contextos, como na programação Lisp , o termo lista pode se referir especificamente a uma lista vinculada em vez de um array. Na programação baseada em classes , as listas são normalmente fornecidas como instâncias de subclasses de uma classe de "lista" genérica e percorridas por iteradores separados .

Muitas linguagens de programação fornecem suporte para tipos de dados de lista e têm sintaxe e semântica especiais para listas e operações de lista. Uma lista muitas vezes pode ser construído por escrever os artigos em sequência, separados por vírgulas , ponto e vírgula , e / ou espaços , dentro de um par de delimitadores tais como parênteses '()', suportes '[]', cintas '{}', ou colchetes angulares '<>'. Algumas linguagens podem permitir que os tipos de lista sejam indexados ou divididos como tipos de array , caso em que o tipo de dados é descrito com mais precisão como um array.

Na teoria dos tipos e na programação funcional , as listas abstratas são geralmente definidas indutivamente por duas operações: nil, que produz a lista vazia, e contras , que adiciona um item no início de uma lista.

Operações

A implementação da estrutura de dados da lista pode fornecer algumas das seguintes operações :

um construtor para criar uma lista vazia;
uma operação para testar se uma lista está vazia ou não;
uma operação para anexar uma entidade a uma lista
uma operação para anexar uma entidade a uma lista
uma operação para determinar o primeiro componente (ou a "cabeça") de uma lista
uma operação para se referir à lista que consiste em todos os componentes de uma lista, exceto o primeiro (isso é chamado de "cauda" da lista.)
uma operação para acessar o elemento em um determinado índice.

Implementações

As listas são normalmente implementadas como listas vinculadas (unicamente ou duplamente vinculadas) ou como matrizes , geralmente de comprimento variável ou matrizes dinâmicas .

A forma padrão de implementar listas, originada da linguagem de programação Lisp , é fazer com que cada elemento da lista contenha seu valor e um ponteiro indicando a localização do próximo elemento na lista. Isso resulta em uma lista vinculada ou uma árvore , dependendo se a lista tem sublistas aninhadas. Algumas implementações Lisp mais antigas (como a implementação Lisp do Symbolics 3600) também suportavam "listas compactadas" (usando codificação CDR ) que tinham uma representação interna especial (invisível para o usuário). As listas podem ser manipuladas por iteração ou recursão . O primeiro é frequentemente preferido em linguagens de programação imperativas , enquanto o último é a norma em linguagens funcionais .

As listas podem ser implementadas como árvores de busca binária de autobalanceamento contendo pares de índice-valor, fornecendo acesso em tempo igual a qualquer elemento (por exemplo, todos residentes na periferia e nós internos que armazenam o índice da criança mais à direita, usados para orientar a pesquisa) , tomando o tempo logarítmico no tamanho da lista, mas contanto que não mude muito, fornecerá a ilusão de acesso aleatório e habilitará as operações de troca, prefixo e acréscimo em tempo logarítmico.

Suporte a linguagem de programação

Algumas linguagens não oferecem uma estrutura de dados de lista , mas oferecem o uso de matrizes associativas ou algum tipo de tabela para emular listas. Por exemplo, Lua fornece tabelas. Embora Lua armazene listas que possuem índices numéricos como matrizes internamente, eles ainda aparecem como dicionários.

Em Lisp , as listas são o tipo de dados fundamental e podem representar o código do programa e os dados. Na maioria dos dialetos, a lista dos três primeiros números primos pode ser escrita como (list 2 3 5). Em vários dialetos do Lisp, incluindo Scheme , uma lista é uma coleção de pares, consistindo em um valor e um ponteiro para o próximo par (ou valor nulo), formando uma lista unida individualmente.

Formulários

Como o nome indica, as listas podem ser usadas para armazenar uma lista de elementos. No entanto, ao contrário dos arrays tradicionais , as listas podem expandir e diminuir e são armazenadas dinamicamente na memória.

Na computação, as listas são mais fáceis de implementar do que os conjuntos. Um conjunto finito no sentido matemático pode ser realizado como uma lista com restrições adicionais; ou seja, elementos duplicados não são permitidos e a ordem é irrelevante. A classificação da lista acelera a determinação se um determinado item já está no conjunto, mas para garantir a ordem, é necessário mais tempo para adicionar uma nova entrada à lista. Em implementações eficientes, no entanto, os conjuntos são implementados usando árvores de busca binária de autobalanceamento ou tabelas de hash , em vez de uma lista.

As listas também formam a base para outros tipos de dados abstratos, incluindo a fila , a pilha e suas variações.

Definição abstrata

A lista abstrata tipo L com elementos de algum tipo E (uma lista monomórfica ) é definida pelas seguintes funções:

nulo: () → L

contras: E × L → L

primeiro: L → E

resto: L → L

com os axiomas

primeiro (cons ( e , l )) = e

resto (cons ( e , l )) = l

para qualquer elemento ee qualquer lista l . Está implícito que

contras ( e , l ) ≠ l

contras ( e , l ) ≠ e

cons ( e ₁ , l ₁ ) = cons ( e ₂ , l ₂ ) se e ₁ = e ₂ e l ₁ = l ₂

Observe que first (nil ()) e rest (nil ()) não estão definidos.

Esses axiomas são equivalentes aos do tipo de dados de pilha abstrata .

Na teoria dos tipos , a definição acima é considerada mais simplesmente como um tipo indutivo definido em termos de construtores: nil e contras . Em termos algébricos, este pode ser representado como a transformação 1 + E × G → G . primeiro e o resto são então obtidos por correspondência de padrões no construtor contras e tratando separadamente o caso nulo .

A lista mônada

O tipo de lista forma uma mônada com as seguintes funções (usando E ^{* em} vez de L para representar listas monomórficas com elementos do tipo E ):

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

{\ displaystyle {\ text {bind}} \ dois pontos A ^ {*} \ to (A \ to B ^ {*}) \ to B ^ {*} = l \ mapsto f \ mapsto {\ 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}}}

onde append é definido como:

{\ displaystyle {\ text {append}} \ dois pontos 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, a mônada pode ser definida em termos de operações return , fmap e join , com:

{\ displaystyle {\ text {fmap}} \ dois pontos (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}} \ dois pontos {A ^ {*}} ^ {*} \ to A ^ {*} = l \ mapsto {\ begin {cases} {\ text {nil}} & {\ texto {if}} \ l = {\ text {nil}} \\ {\ text {append}} \, a \, ({\ text {join}} \, l ') & {\ text {if}} \ l = {\ text {cons}} \, a \, l '\ end {casos}}}

Observe que fmap , join , append e bind são bem definidos, pois são aplicados a argumentos progressivamente mais profundos a cada chamada recursiva.

O tipo de lista é uma mônada aditiva, com nil como o zero monádico e anexado como soma monádica.

As listas formam um monóide sob a operação de acréscimo . O elemento de identidade do monóide é a lista vazia, nulo . Na verdade, este é o monóide livre sobre o conjunto de elementos da lista.

Languages

In other projects