LinkedList adding Element

Question

We have a problem with our LinkedList in C. When I count how many nodes should be in the list, I always get 1

LL count: 1

This is the Add, count and get last element of the list code:

void addLL(LL * head)
{
LL *newNode;
LL *tail = getLastNode(head);

newNode = malloc(sizeof(LL));
if(newNode != DEF_NULL)
{
    newNode->ID=-1;
    newNode->TCB=-1;
    newNode->next = DEF_NULL;

    if(!head) head = newNode;
    else tail->next = newNode;      
}   
}

LL * getLastNode(LL * head)
{
    LL *temp = head;
    while(temp->next != DEF_NULL)
    {
        temp = temp->next;
    }
    return temp;
}

CPU_INT32U countLL(LL * head)
{
    CPU_INT32U elements = 0;
    LL * temp = head;
    while(temp->next != DEF_NULL)
    {
        temp = temp->next;
        elements++;
    }
    return elements;
}

It's called in this way:

addLL(list);
temp = countLL(list);       
Debug_LOG("LL count: %i", temp);

where LL * list; is a global variable, and temp is in local scope. I hope anyone can see where I went wrong

Greetings, Sjaak and Gerrit

Answer 1

I see several issues in your code :

• you should always protect your linked list operations by testing if the list pointer is valid (i.e. not null)
• you cannot allocate a first item to an empty list due to the way you allocate the first new item : you change head but the modification won't be propagated outside of the function. You should pass a "pointer to a list pointer" (i.e. a LL**) that is equivalent to "the address of a LL*"; See how I call addLL() and how I have modified its prototype and the head assignment
• if your list is only one block long, it won't be counted as you count only if there is a successor, see how I have modifed the order of the do / while condition

I propose the modified code that works for 1, 2 or any list length (I have just changed the CPU_INT32U to int to compile quickly with MinGW, I could have typedef'ined):

#include <stdio.h>

#define DEF_NULL 0

typedef struct tagL {
    int ID;
    int TCB;
    struct tagL *next;
} LL;

void addLL(LL ** head);
LL * getLastNode(LL * head);
int countLL(LL * head);

void addLL(LL ** head)
{
    LL *newNode;
    LL *tail = getLastNode(*head);

    newNode = malloc(sizeof(LL));
    if(newNode != DEF_NULL)
    {
        newNode->ID=-1;
        newNode->TCB=-1;
        newNode->next = DEF_NULL;

        if(!*head) 
            *head = newNode;
        else 
            tail->next = newNode;      
    }   
}

LL * getLastNode(LL * head)
{
    LL *temp = head;
    if (head){
        while(temp->next != DEF_NULL)
        {
            temp = temp->next;
        }
    }
    return temp;
}

int countLL(LL * head)
{
    int elements = 0;
    LL * temp = head;
    if (head){
        do {
            temp = temp->next;
            elements++;
        } while(temp != DEF_NULL);
    }
    return elements;
}

int main(int argc, char *argv[]){
    LL *list = 0;

    printf("LL test\n");
    addLL(&list);
    printf("length = %d\n", countLL(list));
    addLL(&list);
    printf("length = %d\n", countLL(list));
    addLL(&list);
    printf("length = %d\n", countLL(list));
}

Output :

LL test
length = 1
length = 2
length = 3

Answer 2

On Windows nothing's wrong whit this function - strange ...

ideone also shows good output.

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

typedef struct LL{
    struct LL *next;
}LL;

LL * getLastNode(LL * head)
{
    LL *temp = head;
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    return temp;
}

void addLL(LL * head)
{
LL *newNode;
LL *tail = getLastNode(head);

newNode = malloc(sizeof(LL));
if(newNode != NULL)
{
    newNode->next = NULL;

    if(!head) head = newNode;
    else tail->next = newNode;      
}   
}

int countLL(LL * head)
{
    int elements = 0;
    LL * temp = head;
    while(temp->next != NULL)
    {
        temp = temp->next;
        elements++;
    }
    return elements;
}

int main() {
    LL *h = malloc(sizeof(*h));
    addLL(h);
    addLL(h);
    addLL(h);
    printf("%d\n", countLL(h)); // prints 3 as expected
}

Answer 3

CPU_INT32U countLL(LL * head){CPU_INT32U elements = 0;LL * temp = head;while(temp->next != DEF_NULL){temp = temp->next;elements++;}return elements;}

in this function you are declaring elements variable as auto so its storage gets deallocated as soon as function exits , as memory now free to allocate to different variable, so may be overwritten hence previous cvalue gets lost

so to avoid this please use static in declaring variable..... as static variables memory gets deallocated only after execution of whole program please try....

Answer 4

void addLL(LL * head)
{
LL *newNode;
LL *tail = getLastNode(head);

There is a problem here, if (the global) head happens to be NULL, it will be dereferenced by the getLastNode() function:

LL * getLastNode(LL * head)
{
    LL *temp = head;
    while(temp->next != DEF_NULL)

Here temp->next != ... will cause temp to be dereferenced. That would cause NULL pointer dereferences if temp happens to be NULL. (as in the call by the insert function. You could add an extra test (or use pointers to pointers which is cleaner):

while(temp && temp->next != DEF_NULL)

Update (to show that the pointer to pointer version is cleaner)

#include <stdlib.h>
#include <stdio.h>
#define DEF_NULL NULL
#define CPU_INT32U unsigned

typedef struct link {
        struct link *next;
        } LL;

LL *globhead=NULL;
LL **getTailPP(LL **ppHead);
CPU_INT32U countLL(LL * ptr);
void addLL(LL **ppHead);

void addLL(LL **ppHead)
{
ppHead = getTailPP(ppHead);

*ppHead = malloc(sizeof **ppHead);
    if(*ppHead != DEF_NULL)
    {
        // newNode->ID=-1;
        // newNode->TCB=-1;
        (*ppHead)->next = DEF_NULL;
    }
}

LL **getTailPP(LL **ppHead)
{
    for( ; *ppHead; ppHead = &(*ppHead)->next ) {;}
    return ppHead;
}

CPU_INT32U countLL(LL * ptr)
{
    CPU_INT32U elements = 0;
    for(; ptr != DEF_NULL; ptr=ptr->next) { elements++; }
    return elements;
}

int main()
{
unsigned count;

addLL( &globhead);
count = countLL (globhead);
printf("count = %u\n", count);

addLL( &globhead);
count = countLL (globhead);
printf("count = %u\n", count);

return 0;
}