Circular linked list in C not giving desired output

Question

I am trying to make a circular linked list in C, but i'm having some trouble. I'm pretty sure it's a pointer issue (I am learning C and pointers are a weakness). here is the code:

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

nodeptr add_to_end(nodeptr head, int val)
{
    if (head == NULL)
    {
        nodeptr new_node = (nodeptr)malloc(sizeof(node));
        new_node->data = val;
        new_node->next = NULL;
        return new_node;
    } else {
        head->next = add_to_end(head->next,val);
        return head;
    }
}


void print_piles(nodeptr nodeHead)
{
    if (nodeHead == NULL)
        return;
    printf("%d\n ",nodeHead->data);
    print_piles(nodeHead->next);
}



int main(int argc, char *argv[])
{
    nodeptr head = NULL;
    nodeptr tail = NULL;
    int i = 0;

    head = add_to_end(head,i);
    i++;
    tail = add_to_end(tail,i);
    head->next = tail;
    i++;
    tail = add_to_end(tail,i);
    tail->next = head;

    printf("%d\n ",head->data);
    printf("%d\n ",tail->data);
    tail = tail->next;
    printf("%d\n ",tail->data);
    return 0;
}

and from cl.h:

// create struct for cards in piles
;typedef struct node
{
    int data;
    struct node *next;
}node, *nodeptr;

the output is:

0
1
0

What I expect to get is:

0
1
2

What do I need to change?

Answer 1

Not a pointer issue! You are getting defined behavior. But your steps to link circularly are wrong. read below I explained your steps in main() function:

Step-1:

i = 0;
head = add_to_end(head,i);

So created a head node (suppose node address is 201):

head: 201
[ 0, NULL]

Step-2:

i++;
tail = add_to_end(tail,i);

So created a tail node (suppose node address is 304):

tail: 304
[ 1, NULL]

Step-3:
After assignment: head->next = tail;: linked list is something like:

head: 201     tail: 304 
[ 0, 304] --► [1, NULL]

Step-4: After following two code sequences:

i++;
tail = add_to_end(tail,i);

You have created a new node and appended node with value 2 (suppose is address 349) in linked list, list is something like this:

head: 201     tail: 304         : 349
[ 0, 304] --► [ 1, 349] --► [ 2, NULL]

Step-5:
Now mistake: tail value is still 304 according to your add function, so after last assigned tail->next = head; you got something like below:

head: 201     tail: 304         : 349
[ 0, 304] --► [ 1, 349]    [ 2, NULL]
   ▲             |
   +-------------+  

So next of tail is head and that is why your are getting 0, 1, 0 as output.

Note also you have memory leak!

Why it is so? The add function appends a node at last and return head that is pass to the function your are passing tail (I am commenting).

nodeptr add_to_end(nodeptr head, int val)
{                     //    ^ is tail at third call
    if (head == NULL)// if first node is NULL
    {
        nodeptr new_node = (nodeptr)malloc(sizeof(node));
        new_node->data = val;
        new_node->next = NULL;
        return new_node; <-- "return only if new node is first node"
    } else {
        head->next = add_to_end(head->next,val);
        return head; <--- "Return `head` that is passed to function at calling"
    }
}

So when you call tail = add_to_end(tail, i); where tail is not NULL then function add_to_end returns older tail (in my example address is 304).

You should correct tail->next = head; as tail->next->next = head; and you will get the excepted result.

Answer 2

int main(int argc, char *argv[])
{
    nodeptr head = NULL;
    nodeptr tail = NULL;
      nodeptr tail1 = NULL;

    int i = 0;

    head = add_to_end(head,i);
    i++;
    tail = add_to_end(tail,i);
    head->next = tail;
    i++;
    tail1 = add_to_end(tail1,i);
    tail->next = tail1;
    tail1->next= head;

    printf("%d\n ",head->data);
    printf("%d\n ",tail->data);
    tail = tail->next;
    printf("%d\n ",tail->data); 

    return 0;
}

Answer 3

If you intend to learn C, by implementing a Circular Linked List, you should try to implement it correctly, and not forcing a not circular list into a circular list, by doing tail->next = header, since if you try to add an item to the list after that, you'll get and infinite recursion hang, kinda infinite loop, since your algorithm checks for a NULL as termination condition.

A Circular list, has a pointer to the head and tail, and you end when you reach the last node by comparing current node to the tail.

Answer 4

You need to add
tail = tail->next in between these two lines :

tail = add_to_end(tail,i);
tail->next = head;

and use tail->next to get the new node.

So, update the main code to -

int main(int argc, char *argv[])
{
    nodeptr head = NULL;
    nodeptr tail = NULL;
    int i = 0;

    head = add_to_end(head,i);
    i++;
    tail = add_to_end(tail,i);
    head->next = tail;
    i++;

    // Add new node to current tail's next
    tail->next = add_to_end(tail,i);
    // Change tail to point to latest added node
    tail = tail->next
    tail->next = head;

    printf("%d\n ",head->data);
    printf("%d\n ",tail->data);
    tail = tail->next;
    printf("%d\n ",tail->data);
    return 0;
}