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