CODEWITHSUNDEEP
cpointersmemory-leakslinked-listsingly-linked-list
Impasse
Impasse

Reputation: 105

In a linked list delete function, is it necessary to use free to delete a node?

I saw this node delete function and compared it to my book's. It's (almost) totally different, I would guess the latter is useful for learning matters...? but then I can't understand why free is even used if all it takes is to move the pointer forward. Maybe I'm missing something.

For reference, here's my book's delete node function:

char delete(ListNodePtr *sPtr, char value){
  if(value == (*sPtr)->data){
    ListNodePtr tempPtr = *sPtr; 
    *sPtr = (*sPtr)->nextPtr; 
    free(tempPtr); 
    return value;
  }
  else{
    ListNodePtr previousPtr = *sPtr;
    ListNodePtr currentPtr = (*sPtr)->nextPtr;

  while(currentPtr != NULL && currentPtr->data != value){
    previousPtr = currentPtr; 
    currentPtr = currentPtr->nextPtr;
  }
  
    if(currentPtr != NULL){
      ListNodePtr tempPtr = currentPtr;
      previousPtr->nextPtr = currentPtr->nextPtr;
      free(tempPtr);
      return value;
    }
  }

  return '\0';
}

I also tried completely removing both the temp variable and the free call and the function still (apparently) works, as in the print function doesn't print the "deleted" value.

Been checking out other sources on linked lists and many of those show usage of the free function, odd.

Upvotes: 1

Views: 1365

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 311058

For starters the code is very and very bad. Firstly there are duplicate code. And secondly the function is made too complicated.

It can be written much simpler. For example

char delete( ListNodePtr *sPtr, char value )
{
    while ( *sPtr != NULL && ( *sPtr )->data != value )
    {
        sPtr = &( *sPtr )->nextPtr;
    }

    char result = *sPtr == NULL ? '\0' : value;

    if ( *sPtr != NULL )
    {
        ListNodePtr tempPtr = *sPtr;
        *sPtr = ( *sPtr )->nextPtr;
        free( tempPtr );
    }

    return result;
}

Also it is a bad idea to use a typedef for pointers as in your program where ListNodePtr is evidently is such a typedef. For example this type specifier

const ListNodePtr

does not mean that data pointed to by a pointer of the type ListNodePtr is a constant data and may not be changed. It means that the pointer itself is constant.

Consider the following demonstrative program

#include <stdio.h>

typedef int * IntPtr;

int main(void) 
{
    int x = 10;
    const IntPtr p = &x;

    *p = 20;

    printf( "x = %d\n", x );

    return 0;
}

Its output is

x = 20

As for your question

In a linked list delete function, is it necessary to use free to delete a node?

then the reference to the deleted node will be lost after exiting the function and if the node will not be deleted there will be a memory leak provided that the node was allocated dynamically.

Upvotes: 1

Deduplicator
Deduplicator

Reputation: 45674

Linus describes lists as used in the Linux kernel there. And the one interesting thing is that those are intrusive lists, meaning the list-management-code is not responsible for freeing nodes, as the list doesn't own them.

Also, the code on that site is not a complete function for deleting nodes, but only the lines for unlinking them.

Your own list will probably be an owning list though, using malloc()-ed memory, right?

Upvotes: 2

Imran Rana
Imran Rana

Reputation: 11899

If you don't use free then you are causing memory leak. If you move your pointer without freeing the memory then it will cause memory leak.

Upvotes: 0

Related Questions