Linked List in C++ using Struct

Question

I am not getting the else part in create_node() function..
As you can see in the else part ,memory block is allocated for r and coeff and power are assigned...but when did they assign r node to the last of linkedlist.. when did they traverse to end of linked list
I mean how is it getting assigned at the last of linked list.


#include <bits/stdc++.h>
using namespace std;

struct Node {
    int coeff;
    int pow;
    struct Node* next;
};

// Function to create new node
void create_node(int x, int y, struct Node** temp)
{
    struct Node *r, *z;
    z = *temp;
    if (z == NULL) {
        r = (struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        *temp = r;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
    else {
        r->coeff = x;
        r->pow = y;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
}

// Display Linked list
void show(struct Node* node)
{
    while (node->next != NULL) {
        printf("%dx^%d", node->coeff, node->pow);
        node = node->next;
        if (node->coeff >= 0) {
            if (node->next != NULL)
                printf("+");
        }
    }
}

// Driver code
int main()
{
    struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;

    // Create first list of 5x^2 + 4x^1 + 2x^0
    create_node(5, 2, &poly1);
    create_node(4, 1, &poly1);
    create_node(2, 0, &poly1);

    // Create second list of -5x^1 - 5x^0
    create_node(-5, 2, &poly2);
    create_node(-5, 0, &poly2);

    printf("1st Number: ");
    show(poly1);

    printf("\n2nd Number: ");
    show(poly2);

    return 0;
}

Am I the only one who thinks that create_node() function should be more like this than the above code?

void create_node(int x, int y, struct Node** temp)
{

    struct Node *r, *z;
    z = *temp;
    if (z == NULL) {
       r = (struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        r->next=NULL;
        *temp = r;
    }
    else {
        r = (struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        r->next=NULL;
        while(z->next!=NULL)
        {
            z=z->next;
        }
        z->next=r;
    }
}

I really want to know how is it producing the right output, even without assigning newnode to last of linked list

We need to convene a council to determine whether you are the only one who thinks so. — Vlad from Moscow
– Vlad from Moscow, Commented Dec 26, 2021 at 10:31
First of all this is not C++ but C so the tag might be misleading here. And second the point of linked list is that you can insert/prepend/append to it at the same cost. The create_node takes a node and appends to it. The else branch is for when the node passed in as temp is not the last also called tail (or rather that it exists as per this implementation). — Resurrection
– Resurrection, Commented Dec 26, 2021 at 10:32

Vlad from Moscow · Accepted Answer · 2021-12-26 10:52:10Z

2

If you are going to write a C++ program then use the operator new to allocate memory instead of calling the C function malloc.

If you want to append a node to the list to its tail then it is better to use a two-sided singly-linked list.

The first function create_node does not make a sense due to appending a dummy node with uninitialized data members except the data member next.

    r->next = (struct Node*)malloc(sizeof(struct Node));
    r = r->next;
    r->next = NULL;

The function show can invoke undefined behavior because it does not check whether the passed pointer is equal to nullptr.

// Display Linked list
void show(struct Node* node)
{
    while (node->next != NULL) {
    //...

The functions as C++ functions can be declared and defined the following way without using a duplicated code.

void create_node( Node **head, int x, int y )
{
    Node *new_node = new Node { x, y, nullptr };

    while ( *head ) head = &( *head )->next;

    *head = new_node;
}

std::ostream & show( const Node *head, std::ostream &os = std::cout )
{
    for ( ; head != nullptr; head = head->next )
    {
        os << head->coeff << '^' << head->pow;

        if ( head->next != nullptr ) os << " + ";
    }

    return os;
}

answered Dec 26, 2021 at 10:52

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ruchita Wagh Over a year ago

Yeah, thank you for the explanation...it helped a lot..... But I am still curious about how the dummy node is getting automatically assigned to last of linked list without traversing to end??

Vlad from Moscow Over a year ago

@RuchitaWagh Without the dummy node the function show will not work correctly. For example if the list contains only one node and there is no dummy node then the condition of the while statement while (node->next != NULL) will evaluate to false and nothing will be outputted.

rturrado · Accepted Answer · 2021-12-26 12:43:10Z

I am not getting the else part in create_node() function.. As you can see in the else part ,memory block is allocated for r and coeff and power are assigned...but when did they assign r node to the last of linkedlist.. when did they traverse to end of linked list I mean how is it getting assigned at the last of linked list.

It is not. When you pass a null Node*, z will be null, and your else code is dereferencing r which hasn't even been initialized.

// Function to create new node
void create_node(int x, int y, struct Node** temp)
{
    struct Node *r, *z;
    z = *temp;
    if (z == NULL) {
        r = (struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        *temp = r;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
    else {
        r->coeff = x;
        r->pow = y;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
}

Am I the only one who thinks that create_node() function should be more like this than the above code?

This seems to solve above's code issues. Here you are creating a Node and assigning it to r, then appending it at the end of z (input Node*). Notice though that you are duplicating the code for creating r in both blocks of code. You could take at least that part out of the if-else.

void create_node(int x, int y, struct Node** temp)
{

    struct Node *r, *z;
    z = *temp;
    if (z == NULL) {
        r = (struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        r->next=NULL;

        *temp = r;
    }
    else {
        r = (struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        r->next=NULL;

        while(z->next!=NULL)
        {
            z=z->next;
        }
        z->next=r;
    }
}

Collectives™ on Stack Overflow

Linked List in C++ using Struct

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related