São aplicações onde os objetos são representados e manipulados em uma sequência ordenada de valores. Ou seja, a partir de um determinado objeto, há um objeto na sequência.
São estruturas que permitem representar um conjunto de dados, que de alguma forma se relacionam, de forma que os elementos fiquem dispostos em sequência. Cada elemento (nó) da lista, pode conter um dado primitivo (inteiro, string, etc.) ou dado composto.
Algumas operações mais comuns são:
• Criar: cria uma lista vazia. • Verificar lista vazia: verifica se há algum elemento na lista. • Verificar lista cheia: verifica se a lista esta cheia. • Inserir: insere um elemento numa determinada posição ou no final da lista. • Alterar: alterar algum elemento da lista. • Remover: remove um elemento de uma determinada posição. • Buscar: acessa um elemento da lista. • Exibir a quantidade: retorna a quantidade de elementos da lista. • Combinar: combina duas ou mais listas em uma única. • Dividir lista: dividi uma lista em duas ou mais. • Ordenar: ordena os elementos da lista de acordo com algum de seus componentes. • Esvaziar: esvaziar a lista.
São exemplos de lista: notas de alunos, cadastro de clientes, produtos em estoque, meses do ano, setores de disco rígido acessado pelo sistema operacional, lista de pacotes transmitido por um computador em uma rede de computadores, etc.
As listas podem ser implementadas de forma estática ou dinâmica. No desenvolvimento de um programa pode ser necessário determinar como será a inserção ou a remoção de elementos de uma lista. Dependendo do critério escolhido, poderemos ter uma implementação em forma de pilha ou lista. As operações implementadas em uma lista dependem do tipo de aplicação.
Em uma lista encadeada, para cada novo elemento inserido na estrutura, alocamos um espaço de memória para armazená-lo. Dessa forma, o espaço total ocupado na memória é proporcional ao número de elementos da lista. No entanto, não podemos garantir que os elementos armazenados na memória ocuparão um espaço contíguo, e por isso não temos acesso aos elementos da lista diretamente.
Para percorrer e ter acesso aos elementos da lista devemos guardar o seu encadeamento. Sendo assim a estrutura consiste em uma sequência encadeada de elementos, chamados de nós da lista. Cada nó da lista tem a sua informação, podendo ser um valor inteiro, real, caractere ou até uma sequência de caracteres, e um ponteiro para o próximo elemento da lista.
A imagem a seguir representa este conceito, onde do primeiro elemento, temos acesso ao segundo, e assim por diante.
Abaixo temos um código em C de exemplo:
Sendo que o último elemento armazenado um ponteiro inválido, com valor NULL, indicando o fim da lista.
struct lista {
int info;
struct lista *prox;
};
typedef struct lista Lista;
Devemos notar que essa estrutura é auto referenciada, pois o campo
*struct lista* prox;* é um ponteiro para para uma estrutura do mesmo tipo. Além disso, uma boa estratégia e definir o tipo “Lista“ como sinônimo de *struct lista* conforme demonstra o trecho de código acima. Com isso, o tipo “Lista“ representa um nó da lista, e a estrutura de lista encadeada será representada por um ponteiro para o primeiro elemento da lista (tipo *Lista**).
Para cada novo elemento inserido na lista devemos alocar dinamicamente a memória para armazená-lo, e posteriormente fazer o encadeamento na lista. Uma possível implementação dessa função é exemplificada a seguir. Deve-se observar que a inserção ocorre sempre no início da lista neste exemplo. A função tem como parâmetros um tipo Lista*, que representa um ponteiro para o primeiro elemento de uma lista e o valor da informação que queremos armazenar. Note que após alocar a memória para o novo elemento, devemos atualizar o ponteiro que representa a lista. Nesse caso, o novo nó aponta (ou seja, tem como próximo elemento) para o elemento que era o primeiro da lista. E então a função retorna a nova lista, representada pelo ponteiro para o novo primeiro elemento.
Lista* inserir(Lista* l, int i){
Lista* novo = (Lista*)malloc(sizeof(Lista));
novo->info = i;
novo->prox = l;
return novo;
Lista *remover(Lista *l, int valor)
{
Lista *anterior = NULL; // ponteiro para o elemento anterior
Lista *p = l; // Ponteiro para percorrer a lista
// procura o elemento na lista, guardando o elemento anterior
while (p != NULL && p->info != valor) {
anterior = p;
p = p->prox;
}
// verifica se achou o elemento
if (p == NULL)
return l; // não achou, retorna à lista original
if (anterior == NULL)
l = p->prox; // caso 1
else {
anterior->prox = p->prox; // caso 2
}
free(p);
return l;
}
Se o elemento que queremos remover for o primeiro, devemos fazer o novo valor da lista passar a ser o ponteiro para o segundo elemento, e então liberamos o espaço alocado para o elemento que iremos retirar. Se o elemento a ser removido estiver no meio da lista, devemos fazer com que o elemento anterior passe a apontar para o seguinte a ele, e então poderemos liberar o espaço de memória (free(p)).
A função percorre a lista em busca do elemento com o valor enviado como parâmetro, caso o ponteiro p tenha como valor final NULL, significa que toda a lista foi percorrida e não foi encontrado o elemento. Caso ele seja diferente de NULL, o elemento foi encontrado e temos dois possíveis casos já citados anteriormente:
Para percorrer uma lista utilizamos uma variável auxiliar do tipo ponteiro, para armazenar o endereço de cada elemento. A imagem abaixo mostra uma função que percorre todos os elementos e imprime o seu valor.
Com estas funções básicas de manipulação de listas demonstradas ao lado podemos utilizar seus conceitos e melhorá-las, e assim criar funções de busca, inserções ordenadas, entre outras possibilidades.
void percorrer(Lista *l)
{
Lista *p;
for (p = l; p != NULL; p = p->prox)
{
printf("info=%d\\n", p->info);
}
}
é um tipo especial de lista em que os elementos a serem inseridos ou removidos ocorrem no topo da pilha. Segue a ordem LIFO (Last in First Out). Em outras palavras, o último elemento inserido está no topo da pilha. Portanto, o elemento para acessar o primeiro é o último elemento inserido. Além disso, a inserção de elementos na pilha é chamada de operação push e a remoção de elementos da pilha é chamada de operação pop.
Algumas operações mais comuns em pilha são: