Algoritmos e Estruturas de Dados/Listas

Lista é definido como uma implementação de um tipo de dado abstrato (ADT), formalizando o conceito de uma coleção ordenada de entidades.Uma lista trata-se de uma série finita de dados, cuja principal propriedade baseia-se na posição relativa dos elementos dispostos linearmente. Uma lista tem as seguintes propriedades:

  • se a lista é vazia ; n=0 senão:
    • a1 é o primeiro elemento da lista (cabeça);
    • an é o último elemento da lista;
    • ak é um elemento entre a1 e an (1<k<n).
Um exemplo de uma lista- uma simples lista ligada com três valores inteiros

Diversas operações podem ser realizadas sobre uma lista como :

  • Acessar um elemento qualquer da lista;
  • Inserir um elemento em uma posição especificada da lista;
  • Excluir um elemento em uma posição especificada da lista;
  • Combinar duas listas em uma;
  • Particionar uma lista em duas;
  • Ordenar elementos de uma lista;
  • e outras.

Casos especiais de listas

editar

Conforme o modo como uma lista é estruturada, e como esta é manipulada, podemos nos referir a ela de forma mais específica.

Pilha é um modelo de lista onde as operações de inserção, remoção e acesso aos dados são feitos em um único extremo. Por isto este modelo é também chamado de LIFO (Last In - First Out).

Fila é um modelo de lista onde a operação de inserção é efetuada por um extremo e a remoção pelo outro extremo. Por isto este modelo é também chamado de FIFO (First In - First Out).