Doubly Linked List in C: Fixed Implementation and Code Review
Doubly Linked List (LDE) in C
This document contains the implementation of a doubly linked list (LDE) in C, with functions for allocation, insertion, removal, traversal, and modification of elements.
Header and Includes
#include "LDE.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>Displaying the List in Reverse Order
The function mostra_invertido displays the list from the last element to the first. It first advances to the tail, then prints each element while moving backward.
void mostra_invertido(LDE l, void (*mostra)(void*)) {
if (lista_vazia(l)) {
printf("A lista está vazia\n");
} else {
ElementoDuplo *p = l.cabeca;
printf("Dados da lista invertida:\n");
printf("\n");
while (p->suc != NULL) {
p = p->suc;
}
while (p->ant != NULL) {
mostra(p->info);
printf("\n");
p = p->ant;
}
mostra(p->info);
}
}Display Callback for Floats
void mostra_float(void *info) { // callback
printf("%.1f\n", *(float *)info);
}Checking if the List Is Empty
int lista_vazia(LDE l) {
return l.cabeca == NULL;
}Allocating an Element
The function aloca_elemento allocates a node and copies the information into it. It checks both allocations to avoid memory leaks.
ElementoDuplo *aloca_elemento(int tamInfo, void *info) {
ElementoDuplo *p = malloc(sizeof(ElementoDuplo));
if (p == NULL)
return NULL;
p->info = malloc(tamInfo);
if (p->info == NULL) {
free(p);
return NULL;
}
memcpy(p->info, info, tamInfo);
return p;
}Initializing the List
void inicializa_lista(LDE *l, int t) {
l->tamInfo = t;
l->cabeca = NULL;
}Inserting at the Beginning
int insereNoInicio(LDE *l, void *info) {
ElementoDuplo *p = aloca_elemento(l->tamInfo, info);
if (p == NULL)
return 0; /* Erro na alocação. */
p->suc = l->cabeca;
p->ant = NULL;
if (l->cabeca != NULL) {
l->cabeca->ant = p;
}
l->cabeca = p;
return 1;
}Removing from the Beginning
int removeNoInicio(LDE *l, void *info) {
if (lista_vazia(*l)) {
return ERRO_LISTA_VAZIA;
}
ElementoDuplo *p = l->cabeca;
l->cabeca = p->suc; /* equivalente a l->cabeca = l->cabeca->proximo; */
memcpy(info, p->info, l->tamInfo);
free(p->info);
free(p);
if (l->cabeca != NULL) {
l->cabeca->ant = NULL;
}
return 1;
}Inserting at the End
int insereNoFim(LDE *l, void *info) {
if (lista_vazia(*l)) {
return insereNoInicio(l, info);
}
ElementoDuplo *p = aloca_elemento(l->tamInfo, info);
if (p == NULL) {
return 0;
}
ElementoDuplo *aux = l->cabeca;
while (aux->suc != NULL) {
aux = aux->suc;
}
p->suc = NULL;
aux->suc = p;
p->ant = aux;
return 1;
}Removing from the End
int removeNoFim(LDE *l, void *info) {
if (lista_vazia(*l))
return ERRO_LISTA_VAZIA;
if (l->cabeca->suc == NULL) // somente quando a lista tem um elemento
return removeNoInicio(l, info);
ElementoDuplo *p = l->cabeca;
while (p->suc->suc != NULL)
p = p->suc;
memcpy(info, p->suc->info, l->tamInfo);
free(p->suc->info);
free(p->suc);
p->suc = NULL;
return 1;
}Displaying the List
void mostra_lista(LDE l, void (*mostra_info)(void *)) {
if (lista_vazia(l))
printf("A lista está vazia\n");
else {
ElementoDuplo *p = l.cabeca;
printf("Dados da Lista:\n");
while (p != NULL) {
mostra_info(p->info);
p = p->suc;
}
}
printf("\n");
}Clearing the List
void limpa_lista(LDE *l) {
ElementoDuplo *p = l->cabeca;
while (p != NULL) {
ElementoDuplo *aux = p->suc;
free(p->info);
free(p);
p = aux;
}
l->cabeca = NULL;
}Inserting at a Given Position
int insereNaPosicao(LDE *l, void *info, int pos) {
if (pos < 0) {
return ERRO_POS_INVALIDA;
}
if (pos == 0) {
return insereNoInicio(l, info);
}
ElementoDuplo *p = l->cabeca;
int cont = 0;
while (cont < pos - 1 && p->suc != NULL) {
p = p->suc;
cont++;
}
if (cont != pos - 1) {
return ERRO_POS_INVALIDA;
}
ElementoDuplo *novo = aloca_elemento(l->tamInfo, info);
if (novo == NULL) {
return 0; // ERRO DE ALOCAÇÃO.
}
novo->suc = p->suc;
novo->ant = p;
if (p->suc != NULL) {
p->suc->ant = novo;
}
p->suc = novo;
return 1; // sucesso.
}Removing from a Given Position
int removeNaPosicao(LDE *l, void *info, int pos) {
if (lista_vazia(*l)) {
return ERRO_POS_INVALIDA;
}
if (pos < 0) {
return ERRO_POS_INVALIDA;
}
if (pos == 0) {
return removeNoInicio(l, info);
}
ElementoDuplo *p = l->cabeca;
int cont = 0;
while (cont < pos - 1 && p->suc != NULL) {
p = p->suc;
cont++;
}
if (cont != pos - 1 || p->suc == NULL) {
return ERRO_POS_INVALIDA;
}
ElementoDuplo *aux = p->suc;
memcpy(info, aux->info, l->tamInfo);
p->suc = aux->suc;
if (aux->suc != NULL) {
aux->suc->ant = p;
}
free(aux->info);
free(aux);
return 1;
}Modifying an Element
int modifica(LDE *l, void *info, int pos) {
if (pos < 0) {
return ERRO_POS_INVALIDA;
}
ElementoDuplo *p = l->cabeca;
int cont = 0;
while (cont < pos && p != NULL) {
p = p->suc;
cont++;
}
if (p == NULL) {
return ERRO_POS_INVALIDA;
}
memcpy(p->info, info, l->tamInfo);
return 1;
}Reading a Value at a Position
int leValor(LDE *l, void *info, int pos) {
if (pos < 0) {
return ERRO_POS_INVALIDA;
}
ElementoDuplo *p = l->cabeca;
int cont = 0;
while (cont < pos && p != NULL) {
p = p->suc;
cont++;
}
if (p == NULL) {
return ERRO_POS_INVALIDA;
}
memcpy(info, p->info, l->tamInfo);
return 1;
}Inserting in Sorted Order
int insereEmOrdem(LDE *l, void *info, int (*compara)(void *, void *)) {
int cont = 0;
ElementoDuplo *p = l->cabeca;
while (p != NULL && compara(info, p->info) > 0) {
cont++;
p = p->suc;
}
return insereNaPosicao(l, info, cont);
}