/* 

Insere no fim da lista

*/

celula * insereNoFim (celula * inicio, item x) {
  celula *novo = malloc(sizeof (celula));
  celula *atual, *ant; 
  novo->info = x;
  novo->prox = NULL; 
  for (atual = inicio, ant = NULL; atual != NULL;
       ant = atual, atual = atual->prox);
  if (ant != NULL)
    ant -> prox = novo;
  else
    inicio = novo;
  return (inicio);
}


celula * insereNoFimRec (celula * inicio, item x) {
  if (inicio == NULL) {
    inicio = malloc (sizeof(celula));
    inicio->info = x;
    inicio->prox = NULL;
  } 
  else inicio->prox = insereNoFimRec (inicio->prox, item x);
  
  return inicio;
} 

  
/* 

celula * insereOrdenado (celula *inicio, item x); 

*/

celula * insereOrdenado (celula * inicio, item x) {
  celula * aux; 
  if (inicio == NULL || inicio->info >= x) {
    aux = inicio; 
    inicio = malloc(sizeof(celula));
    inicio->info = x;
    inicio->prox = aux;
  }
  else inicio->prox = insereOrdenado (inicio->prox, x);
  return inicio;
}

celula * insereOrdenadoIter (celula * inicio, item x) {
  celula *atual, *ant, *novo;
  for (ant = NULL, atual = inicio; atual != NULL && atual->info < x;
       ant = atual, atual = atual ->prox);
  novo = malloc(sizeof(celula));
  novo->info = x;
  novo->prox = atual;
  if (ant != NULL)
    ant->prox = novo;
  else
    inicio = novo;
  return inicio;
} 
  
  


 
/* 

celula * removePrimeiro (celula * inicio); 


*/

celula * removePrimeiro (celula * inicio) {
  celula * aux = inicio; 
  if (inicio != NULL){
    inicio = inicio->prox;
    free (aux);
  } 
  return inicio;
} 


/* 

Remove uma ocorrência de x da lista apontada por inicio

celula * remove (celula * inicio, item x); 

*/


celula * remove (celula * inicio, item x) {
  celula * aux = inicio; 
  if (inicio == NULL) return inicio;
  if (inicio->info == x){
    inicio = inicio->prox;
    free (aux);
  }
  else  inicio->prox = remove(inicio->prox, x); 
  return (inicio);
} 

celula * removeIter (celula * inicio, item x) {
  celula *ant, *atual;
  for (ant = NULL, atual = inicio; atual != NULL && atual->info != x;
       ant = atual, atual = atual->prox);
  if (atual == NULL) return inicio;
  if (ant != NULL)
    ant->prox = atual->prox;
  else
    inicio = atual->prox;
  free (atual);
  return inicio;
} 


/* 

Implementar uma pilha usando listas ligadas: 

topo é um ponteiro para o inicio da lista; 

empilha: insere no início

desempilha: removePrimeiro

pilha está vazia se topo == NULL

*/


/* 

Implementar uma fila usando listas ligadas: exercício!!

Pense em usar dois ponteiros, um para o inicio e outro para o 
fim da fila

*/