So in an attempt to solidify my understanding of pointers and memory management in general in C, I decided to do a basic implementation of a linked list.
I'm very suspicious of certain things in my code though, and was wondering if I could get some clarification. First, the code:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//Doubly-linked lists brah
typedef struct ll_int {
struct ll_int* prev;
int value;
struct ll_int* next;
} ll_int_t;
ll_int_t* newNode(int value) {
//Allocate the memory
ll_int_t* new = (ll_int_t*) malloc(sizeof(ll_int_t));
//If it was not successfully created, exit
if (new == NULL) {
fprintf(stderr, "Unable to allocate memory for new LL node\n");
exit(EXIT_FAILURE);
}
//Set up the node
new->value = value;
new->prev = NULL;
new->next = NULL;
return new;
}
void addElement(ll_int_t* head, int value) {
//Check if the head is in fact the end of the list
if (head->next == NULL) {
ll_int_t* new = newNode(value);
head->next = new;
new->prev = head;
} else {
addElement(head->next, value);
}
}
int lenList(ll_int_t* head) {
int i = 1;
ll_int_t* curr = head;
while ((curr = curr->next) != NULL) i++;
free(curr);
return i;
}
void delHead(ll_int_t** list) {
if (*list != NULL && lenList(*list) > 1) {
ll_int_t* dead = *list;
*list = (*list)->next;
(*list)->prev = NULL;
free(dead);
}
}
bool delElementAt(ll_int_t** list, int pos) {
if (pos == 0) {
delHead(list);
return true;
} else {
//TODO: Implement
}
}
void printLL(ll_int_t** list) {
//We could be clever and traverse back to the start if we're not
//given the head of the list... but that's /effort/
if ((*list)->prev != NULL) {
printf("That is not the head of the Linked List!\n");
return;
}
int i = 0;
ll_int_t* curr = *list;
do {
printf("(%d): %d\n", i++, curr->value);
} while((curr = curr->next) != NULL); //sneaky
free(curr);
}
int main (int argc, char** argv) {
ll_int_t* head = newNode(5);
addElement(head, 10);
printf("lenList: %d\n", lenList(head));
addElement(head, 15);
printf("lenList: %d\n", lenList(head));
addElement(head, 20);
printf("lenList: %d\n", lenList(head));
printLL(&head);
delElementAt(&head, 0);
printLL(&head);
return(EXIT_SUCCESS);
}
Let me pick out some sore points:
So initially, my addElement function looked like:
void addElement(ll_int_t* head, int value) {
//Attempt to create the new node
ll_int_t* new = newNode(value);
//Check if the head is in fact the end of the list
if (head->next == NULL) {
head->next = new;
new->prev = head;
} else {
ll_int_t* curr = head->next;
while (curr->next != NULL) curr = curr->next;
curr->next = new;
new->prev = curr;
}
}
But I was worried about that ll_int_t* curr because it felt like an unnecessary copy. So I changed it to use a tail recursion:
void addElement(ll_int_t* head, int value) {
//Check if the head is in fact the end of the list
if (head->next == NULL) {
ll_int_t* new = newNode(value);
head->next = new;
new->prev = head;
} else {
addElement(head->next, value);
}
}
Which made me feel happier, but I guess my question is, have I actually achieved anything here?
Furthermore, are my free()s in lenList and printLL actually necessary, or does the function scope take care of this for me?
