Home > OS >  C free linked list
C free linked list

Time:12-26

I need to know how to modify the free function to remove the first element of the list (last added). I must not interfere with the main function. This is how the last element added to me remains in the list.

typedef struct TEmployee
{
    struct TEmployee *m_Next;
    struct TEmployee *m_Bak;
    char *m_Name;
} TEMPLOYEE;


TEMPLOYEE *newEmployee (const char *name, TEMPLOYEE *next)
{
    TEMPLOYEE *n = (TEMPLOYEE*) malloc(sizeof(*next));
    
    n->m_Name = (char*) malloc(sizeof(char)*100);
    strcpy(n->m_Name, name);
    n->m_Bak = NULL;
    
    n->m_Next = next;
    
    return n;
    
}


void freeList ( TEMPLOYEE *q )
{
    TEMPLOYEE *x = q;
    
    while( x != NULL)
    {
        TEMPLOYEE *tmp = x->m_Next;
        free(x);
        x = tmp;
    }
    free(x);
    x=NULL;
}

CodePudding user response:

Currently, the freeList method deletes all the elements in the linked list.

To just delete the first element of a linked list, the algorithm should be as follows:

  1. Given the head as the input.
  2. It could be possible that the head itself is NULL meaning the list is already empty, in that case we can simply return.
  3. In the other case, we can simply set head = head->m_Next.
  4. Now, since we also have previous pointers, we need to update the previous pointer for the current head, i.e. head->m_Back = NULL.

Please try to use the above algorithm and write the updated freeList method.

CodePudding user response:

It cannot reliably be done without modifying the caller.

In it's basic form, you just have to free the node and trust that nobody uses it anymore:

void freeFirst ( TEMPLOYEE *q )
{
    if (q) {
        free(q->m_Name);
        free(q);
    }
}

Now to make this a bit more reliable, you should also modify the queue head node. This can be done by passing a double pointer to allow modification of the head node pointer:

void freeFirst ( TEMPLOYEE **q )
{
    TEMPLOYEE *x = *q;

    if (*q) {
        *q = (*q)->m_Next;
        free(*x->m_Name);
        free(*x);
    }
}

Now it's important that the caller is modified, instead of freeList(list) you would now need freeList(&list).

Not that I have also freed the m_Name member, because otherwise you will leak the memory.

You should also use strdup instead of your combination of malloc of arbitrary length and strcpy, that could cause a buffer overflow.

  • Related