CODEWITHSUNDEEP
cpointersmemorylinked-list
BlaqICE
BlaqICE

Reputation: 309

C implementation of a linked list remove element function

I was reading a textbook and came across the following function to remove an element from a linked list. The CELL type is defined as follows;

typedef struct CELL CELL;
struct CELL {
    int element;
    CELL* next;
};

void delete(int x, CELL** pL) {
    if ((*pL) != NULL) {
        if (x == (*pL)->element)
            (*pL) = (*pL)->next;
        else
            delete(x, &((*pL)->next));
    }
}

Now suppose I have a linked list with the following elements starting at 5;

5->10->3->21->15->7

Now suppose I delete element 10. My question is what happens to the CELL containing 10 when the delete function returns now that this CELL is unreferenced? Isn't it still taking up space in memory?

Upvotes: 0

Views: 586

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 311048

For starters some remarks about the function itself. It would be better to declare the function the following way

int delete( CELL **pL, int x );

In fact the function does two things. It searches a node with the value equal to x. And it unlinks a node if such is found.

So it is desirable that the function would report whether such a node is found.

Another way to declare the function in case when the function does not free the removed node pointed to by @IanAbbott in a comment is

CELL * delete( CELL **pL, int x );

That is the function returns pointer to the removed node or NULL if such a node with the value equal to x is not found.

Secondly it is better to declare the first parameter as a reference to node and the second parameter as searched value. That is at first what you are dealing with and then how you are dealing with the list.

As for your question then the function as I already said unlinks a node. The node itself is not removed from memory and is not changed. If it was allocated dynamically then you have to keep a copy of the pointer pointing to the node. Otherwise there will be a memory leak because you will be unable to free it without having a pointer to the node.

Upvotes: 1

jotik
jotik

Reputation: 17910

Since you're not freeing any memory in your code, it should still be there somewhere. You just unlink that element from the linked list.

Depending on how you manage the memory for these elements this might or might not be a problem (memory leak). For example, if each element is allocated using malloc and the linked list has the only pointer to that element then you most likely have a memory leak (and using free is required). But if the nodes are allocated on the stack (e.g. using alloca) or in some memory pool which is freed later, then there might not be a leak. So it really comes down to how you handle the memory and when do you deallocate it.

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726809

what happens to the CELL containing 10 when the delete function returns now that this CELL is unreferenced? Isn't it still taking up space in memory?

Absolutely! Once the function returns, the CELL containing 10 becomes a memory leak, unless there is another pointer referencing it, or the CELL is not allocated dynamically.

If other functions for manipulating the list (creating, inserting, etc.) are implemented in such a way that they assume list's ownership of its cells, add a call to free in the branch that re-points *pl to (*pL)->next. Make a temporary variable, store the address of *pl in it, do the re-pointing, and call free on the temporary.

Upvotes: 2

Related Questions