Linked list in C cannot add a node in the beginning

Question

I'm having trouble adding an element to the beginning in my linked list.

#include <conio.h>
#include "list.h"

int main () {

nodePtr L;
L = createList();
L = makeNode(20);
display(L);
addFront(L,25);
display(L);

return 0;
}

and This is my library, it just prints NODE INSERTED instead of being really inserted at the front.

#include <stdlib.h>
#include <stdio.h>
#ifndef list_h
#define list_h


typedef int itemType;
typedef struct node *nodePtr;

struct node{
    itemType item;
    nodePtr next;
};

nodePtr createList();                                   //init list
nodePtr makeNode(itemType x);                           //allocate node 
void display(nodePtr L);                                //print output
void addFront(nodePtr L, itemType x);                   //add as first element

nodePtr createList() {      
    nodePtr L;
    L= (nodePtr) malloc(sizeof(struct node));
    L->next= NULL;
    return L;
}

nodePtr makeNode(itemType x) {
    nodePtr temp = (nodePtr) malloc(sizeof(struct node));
    temp->item=x;
    temp->next=NULL;
    return temp;
}

void display(nodePtr L) {
    nodePtr temp;
    temp = L;
    while (temp!=NULL) {
        printf("%d", temp->item);
        temp = temp->next;
    }
}

void addFront(nodePtr L, itemType x) {
    nodePtr newNode = (nodePtr) malloc(sizeof(struct node));
    if(newNode == NULL) {
        printf("Unable to allocate memory.");
    }
    else {
    newNode->item = x;
    newNode->next = L;
    L=newNode;
    printf("NODE INSERTED");
    }   
}

#endif

I don't really understand what is wrong, I'm trying to follow the format which initializes typedef nodePtr and itemType from my teacher but I can actually understand the concept of adding the element at the front without following my teacher's format, I just need to understand how her format works as an alternative.

Vlad from Moscow · Accepted Answer · 2022-10-16T17:14:52.270

This function

nodePtr createList() {      
    nodePtr L;
    L= (nodePtr) malloc(sizeof(struct node));
    L->next= NULL;
    return L;
}

does not make sense. It leaves the data member item uninitialized.

These two calls

L = createList();
L = makeNode(20);

produce a memory leak.

The function addFront accepts the pointer to a node by value. That is the function deals with a copy of the original pointer used as an argument. So changing the copy of the pointer within the function

    L=newNode;

does not influence on the value of the original pointer. You need to pass the pointer by reference through a pointer to it.

void addFront(nodePtr *L, itemType x) {
    nodePtr newNode = (nodePtr) malloc(sizeof(struct node));
    if(newNode == NULL) {
        printf("Unable to allocate memory.");
    }
    else {
    newNode->item = x;
    newNode->next = *L;
    *L=newNode;
    printf("NODE INSERTED");
    }   
}

And the function is called like

addFront( &L,25 );

Pay attention to that the function should output neither message. It is the caller of the function that will decide whether to output a message based on the returned value from the function.

So it will be better to define it the following way

int addFront( nodePtr *L, itemType x ) 
{
    nodePtr newNode = malloc( sizeof( struct node ) );
    int success = newNode != NULL;

    if ( success )
    {
        newNode->item = x;
        newNode->next = *L;
        *L = newNode;
    }

    return success;   
}

Another approach to define the function is when the function returns the new value of the pointer to the head node as for example

nodePtr addFront( nodePtr L, itemType x ) 
{
    nodePtr newNode = malloc( sizeof( struct node ) );

    if ( newNode != NULL )
    {
        newNode->item = x;
        newNode->next = L;
    }

    return newNode;   
}

But such an approach is not flexible. Before assigning the returned pointer to the pointer to the head node in the caller you need to check whether the returned pointer is not equal to NULL as for example

nodePtr tmp = addFront( L,25 );

if ( tmp != NULL ) L = tmp;

score 0 · Answer 2 · answered Oct 16 '22 at 11:54

I believe the code of addFront is not 'wrong', however you are missing the return value. The way your code is written now, you are creating a new anchor element, but you are not returning it, meaning that your anchor variable still points to the now second element.

Either:

Return (and assign) your new pointer to anchor.
Pass a pointer to your anchor variable and manipulate that.
Create a new node, copy the value (and next) to that new node and overwrite the value/next of the current node with the new value. (Anchor location stays the same)

Here's the function with a return value.

nodePtr addFront(nodePtr L, itemType x) {
    nodePtr newNode = (nodePtr) malloc(sizeof(struct node));
    if(newNode == NULL) {
        printf("Unable to allocate memory.");
    }
    else {
        newNode->item = x;
        newNode->next = L;
        printf("NODE INSERTED");
    }
    return newNode;
}

Naturally to be called (with due caution) as:

anchor = addFront(anchor, 5);

If memory allocation should fail, this will make the entire linked list inaccessible, because anchor now points to NULL, hence a temporary variable may be in order.

Alternatively:

void addFront(nodePtr *L, itemType x) {
    nodePtr newNode = (nodePtr) malloc(sizeof(struct node));
    if(newNode == NULL) {
        printf("Unable to allocate memory.");
    }
    else {
        newNode->item = x;
        newNode->next = *L;
        *L = newNode;
        printf("NODE INSERTED");
    }
}

This version will only overwrite the anchor if allocating the memory was successful. However it will obviously fail, if the passed L is NULL.

Linked list in C cannot add a node in the beginning

2 Answers2