Estruturas de Dados Básicas - Listas Lineares

Lista é uma estrutura em que operações inserir, retirar e localizar são definidas. As listas podem crescer ou diminuir de tamanho durante a execução de um programa, de acordo com a demanda. Listas são ideais para aplicações onde não é possível prever a demanda por memória, permitindo a manipulação de quantidades imprevisíveis de dados. Elas são úteis em aplicações como gerência de memória e compiladores, por exemplo.

Uma lista linear é uma sequência de zero ou mais itens. Sua principal propriedade estrutural envolve as posições relativas dos itens em uma dimensão.

Para criar um tipo abstrato de dados Lista, é preciso definir um conjunto de operações sobre os objetos do tipo Lista. As operações a serem definidas depende de cada aplicação, mas normalmente a maioria das aplicações possui as seguintes operações:

1. Criar uma lista vazia

2. Inserir um novo item após o último item

3. Retirar um item

4. Localizar um item específico e retornar ou alterar o seu conteúdo

5. Combinar duas ou mais listas em uma única lista

6. Dividir uma lista em duas

7. Fazer uma cópia da lista

8. Ordenar os itens da lista em ordem crescente ou decrescente

9. Pesquisar a ocorrência de um item com um valor específico na lista

Várias estruturas de dados podem ser utilizadas para representar listas lineares, cada uma com vantagens e desvantagens. As duas representações mais comuns são as implementações por meio de arrays e de ponteiros.

Implementação de Listas por meio de Arrays

Em listas do tipo Array, os itens são armazenados em posições contíguas de memória. Nesse caso a lista pode ser percorrida em qualquer direção. Para inserir um novo item ao final da lista o curto é constante, para inserir um item no meio da lista é necessário deslocar todos os outros itens após o item inserido. Da mesma forma, retirar um item do início da lista requer o deslocamento de todos os itens para preencher o espaço vazio.

Os itens são armazenados em um array com o tamanho suficiente para armazenar a lista. A constante MAXTAM possui o tamanho máximo permitido para a lista. O campo Ultimo possui um ponteiro para a posição seguinte a do último elemento da lista.

#define MAXTAM 100

typedef struct { 
	int Chave; 
	/* −−− outros componentes −−− */
} TipoItem; 

typedef struct { 
	TipoItem Item[MAXTAM] ; 
	int Primeiro, Ultimo;
} TipoLista; 

Uma possível implementação das cinco principais operações ficaria assim:

// Cria uma lista vazia
void FLVazia(TipoLista *Lista){ 
	Lista->Primeiro = 1; 
	Lista->Ultimo = Lista->Primeiro; 
}

// Verifica se a lista está vazia
int Vazia(TipoLista Lista){ 
	return (Lista.Primeiro == Lista.Ultimo); 
}

// Insere um item na lista
void Insere(TipoItem x, TipoLista *Lista){ 
	if(Lista->Ultimo > MAXTAM) 
		printf("Lista esta cheia\n");
	else { 
		Lista->Item[Lista->Ultimo − 1] = x; 
		Lista->Ultimo++;
	} 
}

// Retira um item da lista
void Retira(int p, TipoLista *Lista , TipoItem *Item){
	int Aux; 
	if(Vazia(*Lista) || p >= Lista->Ultimo){ 
		printf("Erro: Posicao nao existe\n"); 
		return;
	} 
	*Item = Lista->Item[p − 1]; 
	Lista->Ultimo--; 
	for(Aux = p; Aux < Lista->Ultimo; Aux++) 
		Lista->Item[Aux − 1] = Lista->Item[Aux];
}

// Imprime a lista
void Imprime(TipoLista Lista){ 
	int Aux; 
	for(Aux = Lista.Primeiro - 1; Aux <= (Lista.Ultimo - 2); Aux++) 
		printf("%d\n", Lista.Item[Aux].Chave);
}

Implementar uma lista usando arrays possui vantagens e desvantagens. Como vantagem temos a economia de memória. Como desvantagens temos: o custo para inserir e retirar um item da lista, pois pode causar o deslocamento da lista inteira; e a não previsibilidade do crescimento da lista, pois é preciso definir o tamanho máximo da lista em tempo de compilação.

Implementação de Listas por meio de Ponteiros

Em listas do tipo ponteiros, cada item da lista é encadeado com o seguinte mediante uma variável TipoApontador. Esse tipo de implementação permite utilizar posições não contíguas de memória, e permite inserir e retirar elementos sem a necessidade de deslocar os itens da lista.

Nesse tipo de implementação, é interessante utilizar uma "célula cabeça" que aponta para o primeiro elemento da lista. Apesar de a célula não possuir informação é recomendável fazê-la com a mesma estrutura que as outras células para simplificar as operações com a lista.

A lista é construída com células que possuem um item da lista e um ponteiro para a célula seguinte. O registro TipoLista possue um ponteiro para a "célula cabeça" e um ponteiro para a última célula da lista.

typedef struct{ 
	int Chave; 
	/* −−− outros itens −−− */
} TipoItem; 

typedef struct TipoCelula *TipoApontador; 

typedef struct TipoCelula{ 
	TipoItem Item; 
	TipoApontador Prox; 
} TipoCelula;

typedef struct{ 
	TipoApontador Primeiro, Ultimo;
} TipoLista; 

Uma possível implementação das cinco principais operações ficaria assim:

// Cria uma lista vazia
void FLVazia(TipoLista *Lista){ 
	Lista->Primeiro = (TipoApontador) malloc(sizeof(TipoCelula )); 
	Lista->Ultimo = Lista->Primeiro; 
	Lista->Primeiro->Prox = NULL;
}

// Verifica se a lista está vazia
int Vazia(TipoLista Lista){ 
	return (Lista.Primeiro == Lista.Ultimo); 
}

// Insere um item na lista
void Insere(TipoItem x, TipoLista *Lista){ 
	Lista->Ultimo->Prox = (TipoApontador)malloc(sizeof(TipoCelula)); 
	Lista->Ultimo = Lista->Ultimo->Prox; 
	Lista->Ultimo->Item = x; 
	Lista->Ultimo->Prox = NULL;
}

// Retira um item da lista
void Retira(TipoApontador p, TipoLista *Lista, TipoItem *Item){ 
	TipoApontador q; 
	if(Vazia(*Lista) || p == NULL || p->Prox == NULL){
		printf ("Erro: Lista vazia ou posicao nao existe\n"); 
		return;
	} 
	q = p->Prox; 
	*Item = q->Item; 
	p->Prox = q->Prox; 
	if(p->Prox == NULL) 
		Lista->Ultimo = p; 
	
	free(q);
} 

// Imprime a lista
void Imprime(TipoLista Lista){ 
	TipoApontador Aux; 
	Aux = Lista.Primeiro->Prox; 
	while(Aux != NULL){ 
		printf("%d\n", Aux->Item.Chave); 
		Aux = Aux->Prox; 
	}
} 

Implementar uma lista usando ponteiros permite inserir ou retirar itens do meio da lista a um custo constante. Em casos onde o crescimento da lista não pode ser definido em tempo de compilação, é interessante usar lista encadeadas com ponteiros, pois não é necessário definir o tamanho da lista. A maior desvantagem deste tipo de implementação é a utilização de memória extra para armazenar os ponteiros.

Referências

• ZIVIANI, Nivio. Projeto de algoritmos : com implementações em Pascal e C. 3. ed. rev. e ampl. São Paulo: Cengage Learning, 2011.