aula_listasDuplamenteLigadas

Prévia do material em texto

Listas Duplamente Ligadas
Valéria de Carvalho Santos
valeriac@icmc.usp.br
Departamento de Estatística, Matemática Aplicada e Computação
Instituto de Geociências e Ciências Exatas
Universidade Estadual Paulista “Júlio de Mesquita”
19 de abril de 2013
Implementação Dinâmica
•Nas listas duplamente ligadas, cada nó mantém um
ponteiro para o nó anterior e posterior
•A manipulação da lista é mais complexa, porém algumas 
operações são diretamente beneficiadas
•Por exemplo, as operações de inserção e remoção em
uma dada posição
a b c d
início fim
Implementação Dinâmica
struct ITEM{
int valor; 
};
struct NO{
ITEM item;
struct NO *prox;
struct NO *ant;
};
struct LISTA_DUPLAMENTE_LIGADA{
NO *inicio;
NO *fim;
};
Implementação Dinâmica
int cria(LISTA_DUPLAMENTE_LIGADA *lista){
lista->inicio = NULL;
lista->fim = NULL;
}
int vazia(LISTA_DUPLAMENTE_LIGADA *lista){
return (lista->inicio == NULL && lista->fim == NULL);
}
Implementação Dinâmica
int insereInicio(LISTA_DUPLAMENTE_LIGADA *lista, ITEM *item){
NO *noNovo = (NO*)malloc(sizeof(NO));//cria um novo nó
if(noNovo != NULL){
noNovo->item = *item; 
noNovo->prox = lista->inicio;
noNovo->ant = NULL; 
if(lista->inicio != NULL)
lista->inicio->ant = noNovo;
else
lista->fim = noNovo;
lista->inicio = noNovo; 
return 1; 
} 
return 0;
}
Implementação Dinâmica
int insereFim(LISTA_DUPLAMENTE_LIGADA *lista, ITEM *item){
NO *noNovo = (NO*)malloc(sizeof(NO));//cria um novo nó
if(noNovo != NULL){
noNovo->item = *item; 
noNovo->prox = NULL;
noNovo->ant = lista->fim; 
if(lista->fim != NULL)
lista->fim->prox = noNovo;
else
lista->inicio = noNovo;
lista->fim = noNovo; 
return 1; 
} 
return 0;
}
Implementação Dinâmica
int removeInicio(LISTA_DUPLAMENTE_LIGADA *lista){
NO* noAux;
if(!vazia(lista)){
noAux = lista->inicio;
if(lista->inicio == lista->fim){
lista->inicio = NULL;
lista->fim = NULL;
}
else{ 
lista->inicio->prox->ant = NULL;
lista->inicio = lista->inicio->prox;
} 
free(noAux); 
return 1; 
} 
return 0;
}
Implementação Dinâmica
int removeFim(LISTA_DUPLAMENTE_LIGADA *lista){
if(!vazia(lista)){
NO* noAux = lista->fim;
if(lista->inicio == lista->fim){
lista->inicio = NULL;
lista->fim = NULL;
}
else{ 
lista->fim->ant->prox = NULL;
lista->fim = lista->fim->ant;
}
free(noAux); 
return 1; 
} 
return 0;
}
Implementação Dinâmica
int inserePosicao(LISTA_DUPLAMENTE_LIGADA *lista, ITEM *item, int pos){
if(!vazia(lista)){
NO *noNovo = (NO*)malloc(sizeof(NO));//cria um novo nó
if(noNovo != NULL){
noNovo->item = *item; 
if(pos == 0){
noNovo->prox = lista->inicio;
lista->inicio->ant = noNovo;
lista->inicio = noNovo;
} else{
NO *noAux = lista->inicio;
for(int i=0; i<pos; i++){
if(noAux != lista->fim) noAux = noAux->prox;
else return 0; 
} 
noNovo->prox = noAux;
noNovo->ant = noAux->ant;
noAux->ant->prox = noNovo;
noAux->ant = noNovo; 
} 
return 1; }
} return 0;
}
Exercícios
• Implementar o método remove(posição) e imprime.