I created linked lists in C and a few functions to help me with them.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int value;
void *next;
} Node;
Node *NewNode(int value, Node *next) {
Node *new = malloc(sizeof(Node));
new->value = value;
new->next = next;
return new;
}
typedef struct {
Node *head;
} List;
List NewList() {
List lst = { .head = NULL };
return lst;
}
void Erase(List *lst) {
Node *current = lst->head;
while (current != NULL) {
Node *next = current->next;
free(current);
current = next;
}
lst->head = NULL;
}
void PrintList(List *lst) {
Node *temp = lst->head;
printf("[ ");
while (temp != NULL) {
printf("%d ", temp->value);
temp = temp->next;
}
printf("]\n");
free(temp); // this works wtf?
}
void Push(List *lst, int val) {
Node *new = NewNode(val, lst->head);
lst->head = new;
}
void Pull(List *lst) {
if (lst->head == NULL) {
return;
}
Node *firstNode = lst->head;
lst->head = lst->head->next;
free(firstNode);
}
int GetAtIndex(List *lst, int index) {
Node *temp = lst->head;
for (int i = 0; i < index; i++) {
temp = temp->next;
}
int val = temp->value;
return val;
}
int main() {
List lst = NewList();
Push(&lst, 6);
Push(&lst, 7);
Push(&lst, 8);
Push(&lst, 9);
PrintList(&lst); // [ 9 8 7 6 ]
PrintList(&lst);
int index = 2;
printf("lst[%d] = %d\n", index, GetAtIndex(&lst, index));
PrintList(&lst);
Erase(&lst);
return 0;
}
I think I understand how pointers work to a "decent" level. What I'm still confused with is when to free them and how. In theory it should be simple... Free them when they aren't needed anymore. However I encountered a really strange issue when trying to follow that principle.
More precisely, I tried to add a free(temp) line to the GetAtIndex function, like this:
int GetAtIndex(List *lst, int index) {
Node *temp = lst->head;
for (int i = 0; i < index; i++) {
temp = temp->next;
}
int val = temp->value;
free(temp); // over here
return val;
}
That didn't end well. It worked at first, when no other functions were invoked afterwards (like PrintList or another GetAtIndex). But when I did try invoking other functions the program either crashed or ended up in an infinite loop. The fact that a similar issue didn't occur when I added a free(temp) line to the PritList function is even weirder...
What's actually going on here? Why is freeing a pointer that are just tracking my linked list members resulting in such weird behavior? Or maybe that issue stems from other parts of the program? And lastly, how and when should one free pointers to prevent memory leaks?
free(temp); returns the memory that temp points to. In this case it's a node which is problematic as it's still part of the linked list. In PrintList() you read from memory that was fee'ed you have undefined behavior (UB). In Erase() you likely free one of the nodes again which is called a "double free" which is also UB.
Prefer struct Node * instead of void * for next.
malloc() returns NULL on failure. If you don't check it will segfault when you try to deference that pointer.
Node *NewNode(int value, Node *next) heap allocates a node but NewList() is stack allocated. It would be a more sensible design to be consist. As List just tracks a single head pointer I would eliminate the type in favor for a variable Node *lst. It does mean that when you want to change the caller's value of *lst then you need to pass in a Node **lst.
Prefer for-loops to while-loops for iteration. They are built for it.
Arguments are passed by value in C, so your eliminate the temporary variables and just use the argument (lst). See Erase(), PrintList(), GetAtIndex() (twice).
Push() is fine. An alternative interface is to return the new root node:
Node *Push(Node *lst, int val) {
return NewNode(val, lst);
}
// ...
lst = Push(lst, 6);
The only difference between Push() and NewNode() is the order of arguments. I would eliminate one of them and update callers. Alternatively you could #define one in terms of other if you don't want the wrapper function.
In the current implementation and the above consider using a temporary so you don't leak the tail of your list if malloc() fails.
GetAtIndex() will segfault if index is greater than number of elements. The current interface doesn't have a way to return an error so I changed it return the status of operation either EXIT_SUCCESS or EXIT_FAILURE and value in a new out param value. Consider using an unsigned type for indices otherwise you have to consider what happens what GetAtIndex(lst, -17, &value) means. You want to use the same type for the index variable or just eliminate it as I did below.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
Node *NewNode(int value, Node *next) {
Node *new = malloc(sizeof *new);
if(!new)
return NULL;
new->value = value;
new->next = next;
return new;
}
void Erase(Node *lst) {
while (lst) {
Node *next = lst->next;
free(lst);
lst = next;
}
}
void PrintList(Node *lst) {
printf("[ ");
for(; lst; lst = lst->next) {
printf("%d ", lst->value);
}
printf("]\n");
}
void Push(Node **lst, int val) {
Node *new = NewNode(val, *lst);
*lst = new;
}
int GetAtIndex(Node *lst, unsigned index, int *value) {
for (; index && lst; index--, lst = lst->next);
if(!lst)
return EXIT_FAILURE;
*value = lst->value;
return EXIT_SUCCESS;
}
int main() {
Node *lst = NULL;
Push(&lst, 6);
Push(&lst, 7);
Push(&lst, 8);
Push(&lst, 9);
PrintList(lst); // [ 9 8 7 6 ]
PrintList(lst);
unsigned index = 2;
int value;
if(GetAtIndex(lst, index, &value) == EXIT_SUCCESS)
printf("lst[%u] = %d\n", index, value);
else
printf("out of bounds\n");
PrintList(lst);
Erase(lst);
}