Home > OS >  Problem in output regarding insertion at end of circular linkedlist in c programming
Problem in output regarding insertion at end of circular linkedlist in c programming

Time:09-21

This is my code for insertion in the end of a circular linkedlist for whch i am getting correct result

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

struct node
{
    int data;
    struct node *next;
};
struct node *head;

void insert(int val)
{
    struct node *temp;
    struct node *tail;

    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;

    if (head == NULL)
    {
        head = temp;
        tail = temp;
        temp->next = head;
    }
    else
    {
        tail->next = temp;
        tail = temp;
        tail->next = head;
    }
}

void printlist()
{
    struct node *temp = head;
    printf("The elements of the linked list area \n ");
    while (temp->next != head)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("%d ", temp->data);
    printf("%d", temp->next->data);
}
int main()
{
    int n, i, val;
        printf("Enter how many elements in a circular likedlist you want \n");
        scanf("%d",&n);
    head = NULL;

        for(i=0;i<n;i  )
        {
            // printf("Enter the value\n");
            // scanf("%d,&val");
    
    insert(i);
   
        }
    printlist();
}

for which the output is

Enter how many elements in a circular likedlist you want 
10
The elements of the linked list area 
 0 1 2 3 4 5 6 7 8 9 0

however for the same code when i try to take values from the user it gives me incorrect output.here in this code i just changed a part of main function inside the for loop where i am taking input for the val instead of passing an integer in function insert

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

struct node
{
    int data;
    struct node *next;
};
struct node *head;

void insert(int val)
{
    struct node *temp;
    struct node *tail;

    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;

    if (head == NULL)
    {
        head = temp;
        tail = temp;
        temp->next = head;
    }
    else
    {
        tail->next = temp;
        tail = temp;
        tail->next = head;
    }
}

void printlist()
{
    struct node *temp = head;
    printf("The elements of the linked list area \n ");
    while (temp->next != head)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("%d ", temp->data);
    printf("%d", temp->next->data);
}
int main()
{
    int n, i, val;
        printf("Enter how many elements in a circular likedlist you want \n");
        scanf("%d",&n);
    head = NULL;

        for(i=0;i<n;i  )
        {
            printf("Enter the value\n");
            scanf("%d,&val");
    
    insert(val);
   
        }
    printlist();
}

for this program the output i am getting is

Enter how many elements in a circular likedlist you want 
5
Enter the value
1
The elements of the linked list area 
 0 0

can anyone suggest me where my code is going wrong?

CodePudding user response:

The easiest fix is probably to make tail a global variable like head. I also refactored insert() to reduce duplication, added error checking for malloc() and scanf(), tweaked printlist() to not print the head twice:

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

struct node {
    int data;
    struct node *next;
};
struct node *head;
struct node *tail;

void insert(int val) {
    struct node *temp = malloc(sizeof(*temp));
    if(!temp) {
        printf("malloc failed\n");
        exit(1);
    }
    temp->data = val;

    if (head == NULL) {
        head = temp;
    } else {
        tail->next = temp;
    }
    tail = temp;
    tail->next = head;
}

void printlist() {
    printf("The elements of the linked list area \n ");
    for(struct node *temp = head; temp; ) {
        printf("%d ", temp->data);
        temp = temp->next;
        if(temp == head) break;
    }
    printf("\n");
}

int main(void) {
    printf("Enter how many elements in a circular likedlist you want \n");
    int n;
    if(scanf("%d", &n) != 1) {
        printf("scanf failed\n");
        return 1;
    }
    head = NULL;
    for(int i=0; i<n; i  ) {
        insert(i);
    }
    printlist();
}

and it the output is now:

The elements of the linked list area 
 0 1 2 3 4 5 6 7 8 9

You could eliminate the head pointer (tail->next == head) if you want.

CodePudding user response:

In the insert function, the else branch is dereferencing pointer variable tail that has not been initialized. (The variable tail has automatic storage class, i.e. it is a "stack" variable, so it's value is not preserved between calls to the function.) The tail variable needs to point to the last element on the list.

The function can be changed to search for the last element of the list like this:

void insert(int val)
{
    struct node *temp;
    struct node *tail;

    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;

    if (head == NULL)
    {
        head = temp;
    }
    else
    {
        /* find last element */
        for (tail = head; tail->next != head; tail = tail->next)
            ;
        tail->next = temp;
    }
    temp->next = head;
}

(However, it probably makes more sense to store the tail statically outside the function as in Allan Wind's answer so that the function does not have to waste time finding the last element of the list each time it is called. It should also check for memory allocation failure, as in that answer.)


The printList function does not currently work if the list is empty. It will dereference head even if it is NULL, leading to undefined behavior. That can be fixed by moving the all code that accesses the elements of the list inside a if (head != NULL) { } block:

void printlist(void)
{
    struct node *temp = head;
    printf("The elements of the linked list are \n ");
    if (head != NULL)
    {
        while (temp->next != head)
        {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        printf("%d ", temp->data);
        printf("%d", temp->next->data);
    }
    printf("\n");
}

CodePudding user response:

If you want to be respected as a coder, you don't use global variables, and then compound the mistake with adding more globals or 'scanning' what could be millions of nodes to find the tail of a LL.

The code below declares an ordinary node, and a special header node that are compatible. My old compiler does not provide "nameless structs" inside a struct. (ie: There are two lines (traversing the list) that could be more seamless with a modern compiler.)

The testing in main() uses two LLs; one for some integer values, and one that grows with only the odd numbered integer values.

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

typedef struct node {
    int data;
    struct node *next;
} node_t;

typedef struct {
    node_t n; // MUST BE at start of struct!
    node_t *tail;
    int cnt; // meta-information becomes simple to implement
    int id;
} head_t;

head_t *append( head_t *ph, int n ) {
    static int take_a_number = 0;
    node_t *nn = (node_t *)calloc( 1, ph ? sizeof(node_t) : sizeof(head_t) );
    /* omitting check */

    nn->data = n;
    nn->next = nn; // for now, a 'ringlet'

    if( ph == NULL ) {
        ph = (head_t*)nn; // notice the casting of compatible struct entities
        ph->tail = nn;
        ph->id =   take_a_number;
    } else {
        nn->next = (node_t*)ph;
        ph->tail = ph->tail->next = nn;
    }
    ph->cnt  ;

    // debug traversal showing results
    printf( "list #%d - %d nodes: %d ", ph->id, ph->cnt, ph->n.data );
    for( node_t *p = ph->n.next; p != (node_t*) ph; p = p->next )
        printf( "%d ", p->data );
    puts( "" );

    return ph;
}

int main() {
    int i;

    // two lists. Could be 100, or an array of them...
    head_t *p1 = NULL, *p2 = NULL;
    for( i = 7; i <= 49; i  = 7 ) {
        p1 = append( p1, i );
        if( i%2 )
            p2 = append( p2, i );
    }

    printf( "Two laps around first list: " );
    node_t *pFun = (node_t*)p1;
    for( i = 2*p1->cnt   1; i; i-- )
        printf( "%d ", pFun->data ), pFun = pFun->next;
    puts( "" );

    /* omitting `free()` of heap */

    return 0;
}

Output

list #1 - 1 nodes: 7
list #2 - 1 nodes: 7
list #1 - 2 nodes: 7 14
list #1 - 3 nodes: 7 14 21
list #2 - 2 nodes: 7 21
list #1 - 4 nodes: 7 14 21 28
list #1 - 5 nodes: 7 14 21 28 35
list #2 - 3 nodes: 7 21 35
list #1 - 6 nodes: 7 14 21 28 35 42
list #1 - 7 nodes: 7 14 21 28 35 42 49
list #2 - 4 nodes: 7 21 35 49
Two laps around first list: 7 14 21 28 35 42 49 7 14 21 28 35 42 49 7

And not one global variable in use. This is part of structured programming.

  •  Tags:  
  • c
  • Related