removing elements & memory management in linked lists in c

Question

there! I've been working on data structures & algorithms. One thing that has been bothering me a lot, is linked list.

I've check a lot of linked list code samples, but one thing that I have noticed in every single one of them, is how they create node structs & make the user link them together.

So I started searching ways of creating linked lists in different languages & porting them to C. I found a tutorial that worked with Java. After porting the code, insertion was working fine, but removing gives me seg faults.

I think it's working this way, since in Java, we have garbage collectors & the fact that after malloc() you need to free() the memory, but no matter, how much I thought about it, I couldn't wrap my head, to where I should put free(). So the struct is memory unsafe as well.

So my real problem is were I should use free() in this code(maybe the seg fault is for a completely different reason, who knows).

#include <stdlib.h>

struct node {int value; struct node* next;};

typedef struct {struct node* first; struct node* last;} linkedList;

void initializeLinkedList(linkedList* list)
{
    list->first = list->last = NULL;
}

// O(1)
void addLastLinkedList(linkedList* list, int element)
{
    // create a new node
    struct node* insertionNode = malloc(sizeof(struct node));
    insertionNode->value = element;

    // check if the linked list is empty
    if (list->first==NULL) list->first = list->last = insertionNode;
    else
    {
        // make last node point to this node
        list->last->next = insertionNode;
        // make the last node, this node
        list->last       = insertionNode;
    }
}

// O(1)
void addFirstLinkedList(linkedList* list, int element)
{
    // create a new node
    struct node* insertionNode = malloc(sizeof(struct node));
    insertionNode->value = element;

    // check if the linked list is empty
    if (list->first==NULL) list->first = list->last = insertionNode;
    else
    {
        // make node point to the first node
        insertionNode->next = list->first;
        // make it the first node
        list->first = insertionNode;
    }
}

// O(n)
int removeLastLinkedList(linkedList* list)
{
    // check if the linked list is empty
    if (list->first==NULL) return -1;
    // check if the linked list only has a single item
    if (list->first==list->last) list->first = list->last = NULL;
    // get the last to second node
    struct node* currentNode = list->first;
    while (currentNode != NULL)
    {
        if (currentNode->next == list->last) break;
        currentNode = currentNode->next;
    }
    // set the last node to the second to last node
    list->last       = currentNode;
    list->last->next = NULL;
}

// O(1)
int removeFirstLinkedList(linkedList* list)
{
    // check if the linked list is empty
    if (list->first==NULL) return -1;
    // check if the linked list only has a single item
    if (list->first==list->last) list->first = list->last = NULL;
    // get the second node
    struct node* secondNode = list->first->next;
    // remove the pointer of first node
    list->first->next = NULL;
    // make the second node, the first node
    list->first = secondNode;
    return 0;
}

Answer 1

Within the both functions addLastLinkedList and addFirstLinkedList you forgot to initialize to NULL the data member next of the new node. Add statement

insertionNode->next = NULL;

The function removeLastLinkedList invokes undefined behavior when the list contains only one node because after this if statement

if (list->first==list->last) list->first = list->last = NULL;

the control is passed further to this code snippet

struct node* currentNode = list->first;
//...
// set the last node to the second to last node
list->last       = currentNode;
list->last->next = NULL;

where there is used the null pointer list->last to access data member next.

Also the function produces a memory leak because the removed node is not freed.

And the function returns nothing if the list was not empty.

At least rewrite the function like

int removeLastLinkedList(linkedList* list)
{
    // check if the linked list is empty
    if (list->first==NULL) return -1;

    // check if the linked list only has a single item
    if ( list->first == list->last ) 
    {
        free( list->first );
        list->first = list->last = NULL;
    }
    else
    {
        // get the last to second node
        struct node *currentNode = list->first;
        while ( currentNode->next != list->last )
        {
            currentNode = currentNode->next;
        }

        free( currentNode->next );
        // set the last node to the second to last node
        list->last       = currentNode;
        list->last->next = NULL;
    }

    return 0;
}

Similar problems exist in the function removeFirstLinkedList

Rewrite the function like

int removeFirstLinkedList(linkedList* list)
{
    // check if the linked list is empty
    if (list->first==NULL) return -1;

    // check if the linked list only has a single item
    if ( list->first == list->last ) 
    {
        free( list->first );
        list->first = list->last = NULL;
    }
    else
    {
        // get the second node
        struct node *secondNode = list->first->next;
        free( list->first );
        // make the second node, the first node
        list->first = secondNode;
    }

    return 0;
}