removing elements & memory management in linked lists in c-CodePudding

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;
}

CodePudding user response：

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;
}

CodePudding user response：

Here is ANOTHER brief example of the four non-trivial functions in your OP. While it is apparent that the code (and comments) is struggling to get things happening correctly, the long variable and function names make it difficult to read. This "less verbose" version may bring some clarity to seeing/thinking about what operations are being performed and in what sequence.

The first two functions below deal with the "head" of the linked list. They are somewhat easier and "set the mood" before reading the second two functions that deal with the "tail".

// Use typedefs and short conventional names
typedef struct node {
    int value;
    struct node *next;
} node_t;

typedef struct {
    node_t *first;
    node_t *last;
} ll_t;

// Short names!
void LLprepend( ll_t *p, int element ) {
    node_t *nn = calloc( 1, sizeof *nn ); // omitting verification
    nn->value = element;

    nn->next = p->first; // Always
    p->first = nn;
    if( p->last == NULL ) // first node on list
        p->last = nn;
}

int LLtrimhead( ll_t *p ) {
    if( p->first == NULL )
        return -1;

    node_t *pDel = p->first; // target node being removed
    p->first = p->first->next; // advance ptr (may be NULL)

    free( pDel ); // <<===

    if( p->first == NULL ) // list now empty??
        p->last = NULL;

    return 0;
}

// Short names!
void LLappend( ll_t *p, int element ) {
    // calloc initializes all bytes to NULL
    node_t *nn = calloc( 1, sizeof *nn ); // omitting verification
    nn->value = element; // store data

    if( p->last == NULL )
        p->first = p->last = nn; // first node on list
    else
        p->last = p->last->next = nn; // appended & adjusted
}

int LLtrimtail( ll_t *p ) {
    if( p->last == NULL )
        return -1;

    node_t *pPen = p->first; // "Penultimate" node

    // traverse to penultimate node
    while( pPen->next && pPen->next->next )
        pPen = pPen->next;

    if( pPen == p->first ) { // Only 1 node on list
        free( pPen ); // <<===
        p->first = p->last = NULL;
        return 0;
    }
    free( pPen->next ); // <<===
    p->last = pPen; // last becomes what was 2nd last
    return 0;
}