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

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

Pilha

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).

Filas

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).