why do I need to use strdup()?

Viewed 279
typedef struct Node {
    char *word;
    struct Node *next;
} Node;

Node* newNode(char *word) {

    Node *n = malloc(sizeof(Node));
    n->word = word;
    n->next = NULL;
    return n;
}

In this code (Singly Linked List), If I create many Nodes they all have the name of the last Node and I need to understand why in the newNode function I need to use strdup() function, when I searched for a solution, in this line of code n->word = strdup(word); and create a copy of word in the heap.

If I use malloc(sizeof(Node)); that means to reserve a place in the heap for this node so every node should be independent why than they share the name of the last Node?

5 Answers

This line doesn't do what you think:

n->word = word

You need to use strdup() (which by the way is not a standard function as of C18, but might be in C2x) to allocate memory for the string separately. The above line simply copies the address of the string, so n->word and word point to the same string. This line creates a new string with the same contents:

n->word = strdup(word);

Or, to be compliant with the standard:

n->word = malloc((strlen(word) + 1) * sizeof(char));
strcpy(n->word, word);

Your nodes only contains a pointer and that pointer needs to point to somewhere in memory where your actual word is stored.

Maybe this example will help you understand.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char *word;
    struct Node *next;
} Node;

Node* newNode(char *word) 
{
    Node *n = malloc(sizeof(Node));
    n->word = word;
    n->next = NULL;
    return n;
}

Node* insertNode(Node* head, Node* n) 
{
    n->next = head;
    return n;
}

void printList(Node* head)
{
    while(head)
    {
        printf("%s\n", head->word);
        head = head->next;
    }
}

int main(void) {

    // Step 1: Create a list that "works" due to use of string literals
    Node* head1 = NULL;
    head1 = insertNode(head1, newNode("world"));
    head1 = insertNode(head1, newNode("hello"));
    head1 = insertNode(head1, newNode("test"));
    printList(head1);

    printf("------------------------------------------------\n");

    // Step 2: Create a list that "fails" due to use of a char array
    Node* head2 = NULL;
    char str[20];
    strcpy(str, "test");
    head2 = insertNode(head2, newNode(str));
    strcpy(str, "hello");
    head2 = insertNode(head2, newNode(str));
    strcpy(str, "world");
    head2 = insertNode(head2, newNode(str));
    printList(head2);

    printf("------------------------------------------------\n");

    // Step 3: Change the value that head2 nodes points to
    strcpy(str, "What!!");
    printList(head2);

    return 0;
}

Output:

test
hello
world
------------------------------------------------
world
world
world
------------------------------------------------
What!!
What!!
What!!

Step 1:

The head1 list works as expected because each node is initialized with a pointer to a string literal which is stored somewhere in memory. Each string literal is stored in different memory. Consequently it's working fine.

Step 2:

The head2 list doesn't work as you expected. This is because each node is intialized with str so all nodes simply points to the str array. Consequently, all nodes points to "world", i.e. the last word copied into str.

Step 3:

Then a new word, i.e. "What!!" is copied into the str array and again every node will now print the contents of str, i.e. "What!!".

Conclusion:

It all depends on how you call newNode.

If you call it with a pointer to some new memory every time, you don't need to copy the word to a new location (or use strdup).

But if you reuse a buffer when calling newNode you'll need to make a copy to some other memory inside newNode (and strdup is one way to do that copy)

Because word is a pointer to a string, so when malloc(sizeof(Node)) you are only allocating space for the pointer, but not for the string itself.

That is why you have to initialize n->word separately (note that strdup() does two things for you: It allocates memory and copies the string into it, then returns the pointer).

It means that you are passing to the function newNode

Node* newNode(char *word) {

    Node *n = malloc(sizeof(Node));
    n->word = word;
    n->next = NULL;
    return n;
}

a pointer to the first character of the same character array the content of which is being changed in the code that calls the function but the address of the array is not changed that is you are using the same array.

You need to make a copy of the string the pointer to which is passed to the function. In this case the function will look more complicated the following way

Node* newNode( const char *word ) 
{
    Node *n = malloc( sizeof( Node ) );
    int success = n != NULL;

    if ( success )
    {
        n->word = malloc( strlen( word ) + 1 );
        success = n->word != NULL;

        if ( success )
        {
            strcpy( n->word, word ); 
            n->next = NULL;
        }
        else
        {
            free( n );
            n = NULL;
        }
    }

    return n;
}

The caller of the function should check whether the obtained pointer is equal to NULL or not equal to NULL.

Here is a simple demonstrative program that shows how you can append new nodes to the list using the function. Pay attention to that the function strdup is not a standard C function.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char *word;
    struct Node *next;
} Node;

Node* newNode( const char *word ) 
{
    Node *n = malloc( sizeof( Node ) );
    int success = n != NULL;

    if ( success )
    {
        n->word = malloc( strlen( word ) + 1 );
        success = n->word != NULL;

        if ( success )
        {
            strcpy( n->word, word ); 
            n->next = NULL;
        }
        else
        {
            free( n );
            n = NULL;
        }
    }

    return n;
}

int append( Node **head, const char *word )
{
    Node *new_node = newNode( word );
    int success = new_node != NULL;

    if ( success )
    {
        while ( *head != NULL ) head = &( *head )->next;

        *head = new_node;
    }

    return success;
}

void display( Node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "\"%s\" -> ", head->word );
    }

    puts( "null" );
}

int main(void) 
{
    Node *head = NULL;
    const char *word = "Hello";

    append( &head, word );

    word = "World";

    append( &head, word );

    display( head );

    return 0;
}

The program output is

"Hello" -> "World" -> null

Basically, in C++ there is no type "String". String is a bunch of chars that are aligned in an array. It means that string is a pointer. So strdup let you copy the content of the string and do not duplicate the address of that string.

Related