Lista (tipo de dados abstrato)

Em 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 seqüência finita ; o análogo (potencialmente) infinito de uma lista é um fluxo . [1] : §3.5  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 encadeada individualmente, 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 encadeadas e arrays . Em alguns contextos, como na programação Lisp , o termo lista pode se referir especificamente a uma lista encadeada em vez de um array. Na programação baseada em classe , as listas geralmente são fornecidas como instâncias de subclasses de uma classe genérica de "lista" e percorridas por meio de iteradores separados .

Muitas linguagens de programação fornecem suporte para tipos de dados de lista e possuem sintaxe e semântica especiais para listas e operações de lista. Uma lista geralmente pode ser construída escrevendo os itens em sequência, separados por vírgulas , ponto e vírgula e/ou espaços , dentro de um par de delimitadores como parênteses '()', colchetes '[]', colchetes '{}' ou colchetes angulares '<>'. Algumas linguagens podem permitir que 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 geralmente são definidas indutivamente por duas operações: nil que produz a lista vazia e cons , que adiciona um item no início de uma lista. [2]

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á ou não vazia;
  • 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 o "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 (simples ou duplamente vinculadas) ou como arrays , geralmente de comprimento variável ou arrays dinâmicos .

A maneira padrão de implementar listas, originária 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 encadeada ou em uma árvore , dependendo se a lista possui sublistas aninhadas. Algumas implementações Lisp mais antigas (como a implementação Lisp do Symbolics 3600) também suportavam "listas comprimidas" (usando codificação CDR ) que tinham uma representação interna especial (invisível para o usuário). As listas podem ser manipuladas usando 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 binárias de busca autobalanceadas contendo pares de valores de índice, fornecendo acesso em tempo igual a qualquer elemento (por exemplo, todos residindo na periferia e nós internos armazenando o índice filho mais à direita, usado para guiar a pesquisa) , assumindo o tempo logarítmico no tamanho da lista, mas desde que não mude muito, fornecerá a ilusão de acesso aleatório e permitirá operações de troca, prefixo e acréscimo em tempo logarítmico também. [3]

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 arrays internamente, elas ainda aparecem como dicionários. [4]

Em Lisp , as listas são o tipo de dados fundamental e podem representar tanto o código do programa quanto 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 de Lisp, incluindo Scheme , uma lista é uma coleção de pares, consistindo de um valor e um ponteiro para o próximo par (ou valor nulo), formando uma lista encadeada individualmente. [5]

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 encolher 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 percebido como uma lista com restrições adicionais; ou seja, elementos duplicados não são permitidos e a ordem é irrelevante. Ordenar a lista agiliza a determinação se um determinado item já está no conjunto, mas para garantir a ordem, requer mais tempo para adicionar uma nova entrada à lista. Em implementações eficientes, no entanto, os conjuntos são implementados usando árvores de pesquisa binária autobalanceadas 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 × LL
primeiro: LE
resto: LL

com os axiomas

primeiro (contras ( e , l )) = e
resto (cons ( e , l )) = l

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

contras ( e , l ) ≠ l
contras ( e , l ) ≠ e
cons ( e 1 , l 1 ) = cons ( e 2 , l 2 ) se e 1 = e 2 e l 1 = l 2

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

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

Na teoria de tipos , a definição acima é considerada mais simplesmente como um tipo indutivo definido em termos de construtores: nil e cons . Em termos algébricos, isso pode ser representado como a transformação 1 + E × LL . first e rest são então obtidos pela correspondência de padrões no construtor cons e manipulando separadamente o caso nil .

A mônada da lista

O tipo 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 ):

onde append é definido como:

Alternativamente, a mônada pode ser definida em termos das operações return , fmap e join , com:

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, nil . Na verdade, este é o monóide livre sobre o conjunto de elementos da lista.

Veja também

Referências

  1. ^ Abelson, Harold; Sussman, Gerald Jay (1996). Estrutura e Interpretação de Programas de Computador . Imprensa MIT.
  2. ^ Reingold, Edward; Nievergelt, Jurg; Narsingh, Deo (1977). Algoritmos Combinatórios: Teoria e Prática . Englewood Cliffs, Nova Jersey: Prentice Hall. pp. 38–41. ISBN 0-13-152447-X.
  3. ^ Barnett, Grandville; Del tonga, Luca (2008). "Estruturas de Dados e Algoritmos" (PDF) . mta.ca . Acesso em 12 de novembro de 2014 .
  4. ^ Lerusalimschy, Roberto (dezembro de 2003). Programação em Lua (primeira edição) (Primeira ed.). Lua.org. ISBN 8590379817. Acesso em 12 de novembro de 2014 .
  5. ^ Steele, Guy (1990). Common Lisp (Segunda ed.). Imprensa Digital. pp. 29–31. ISBN 1-55558-041-6.