C++ Creating a linked list using recursive function

Question

Hi I am a beginner learning c++ I am trying to create a linked list using recursive function I though I got more or less pointer, linked list, data structure etc but I am stuck for 2 days.

Here's my entire code.

What I am basically trying to do is like I said creating a linked list using only recursive function. The problem is my pointer variable 'head' is always pointing to NULL and I can't figure out why and i guess i misunderstood a lot of things but i simply don't know what ... and more i try more i am getting confused.

It must be quite newbie question but Id really appreciate if someone can help me.

#include <iostream>

using namespace std;

struct linkedlist
{
    int value;
    linkedlist *next;
};

void insertNode(linkedlist* temp)
{
    if (temp->next != NULL)
    {
        insertNode(temp->next);
    }
    else
    {
        temp->next = new linkedlist;
        temp->next->value = 0;
        temp->next->next = NULL;
    }

}


linkedlist *addNode(linkedlist *temp)
{ 
    if (temp == NULL)
    {
        linkedlist *newelement = new linkedlist;
        newelement->value = 0;
        newelement->next = NULL;
        temp = newelement;

        return newelement;
    }
    else
    {
        insertNode(temp);
    }
}

void displaylist(linkedlist *temp)
{
    while (temp != NULL)
    {
        cout << temp->value << endl;
        temp = temp->next;
    }
}

int main()
{
    linkedlist *head = NULL;

    linkedlist *element1 = addNode(head);
    linkedlist *element2 = addNode(head);
    linkedlist *element3 = addNode(head);
    linkedlist *element4 = addNode(head);
    linkedlist *element5 = addNode(head);

    cin.ignore();
    cin.get();
}

Please keep in mind, that recursion will cause strict size limits to your list. If you have too many elements in your list you will get a StackOverflowException. Consider avoiding recursion. — slartidan
– slartidan, Commented Jul 1, 2015 at 8:13

TartanLlama · Accepted Answer · 2015-07-01 07:58:00Z

3

You are trying to modify the pointer you pass in to addNode, but the pointer is passed by-value, so you won't see the modification at the call site.

To fix this, take in the pointer by reference:

linkedlist *addNode(linkedlist*& temp)

answered Jul 1, 2015 at 7:58

TartanLlama

66.2k13 gold badges167 silver badges203 bronze badges

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

5 Comments

Hwabum Kim Over a year ago

This was exactly what i was missing that i couldnt find anywhere actually ... I am super beginner for now but i hope one day i can program like you !

Hwabum Kim Over a year ago

It helped me a lot thank you so much . I would have eventually a question about this pointer by reference. it solved perfectly my problem and I see that if i use this 'head' variable again on other function to print out my list it works fine. My question is that how possibly this variable is pointing to starting element of list since i don't see any code making it point to it ... Voila another very newbie question

Hwabum Kim Over a year ago

(I wanted to enter to make space it just entered my comment) I mean it's cool everything is working perfectly but i would like to know how it is pointing to starting element.

Hwabum Kim Over a year ago

After all I was stuck in this chapter since at least 3 days actually you wouldn't know how much you helped me ! Thank you ^^ !

TartanLlama Over a year ago

It is pointing to the beginning of the list, because the first call to addNode allocates a node into head, then subsequent calls append nodes onto the end of that node.

Vlad from Moscow · Accepted Answer · 2015-07-01 08:24:51Z

1

Your code does not make great sense. For example function addNode should have a parameter for the value that is added to the list. Also there is no need to have two functions addNode and insertNode because they do the same (at least in your functions' implementations). If you want to have some function insertNode then it should have a different semantic.

Here is a demonstrative program that shows how function addNode can be written. You can use it as a template for your program. In this demonstrative program function displayList is also recursive. Of course you need to write also the function that will delete all nodes. It also can be recursive.

#include <iostream>

struct linkedlist
{
    int value;
    linkedlist *next;
};

linkedlist * addNode( linkedlist *head, int value )
{
    return head == nullptr 
           ? ( new linkedlist { value, nullptr } )
           : ( head->next = addNode( head->next, value ), head );
}

void displayList( linkedlist *head )
{
    if ( head == nullptr )
    {
        std::cout << std::endl;
    }
    else
    {
        std::cout << head->value << ' ';
        displayList( head->next );
    }
}

int main()
{
    linkedlist *head = nullptr;

    for ( int x : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ) head = addNode( head, x );
    displayList( head );
}

The program output is

0 1 2 3 4 5 6 7 8 9

edited Jul 1, 2015 at 8:24

answered Jul 1, 2015 at 8:18

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

3 Comments

Hwabum Kim Over a year ago

Thank you so much for your reply ! I changed some of my code with your advice and actually yes i didnt need 2 function for 'addNode'.

Hwabum Kim Over a year ago

But i haven't learned yet about some of codes you've written like nullptr and those below it like '?' and ':' but I really appreciate your advice. I hope I could use your help again ^^

Vlad from Moscow Over a year ago

@Hwabum Kim You may substitute nullptr for NULL. As for ? and : then it is the so-called conditional operator. It is equivalent to the following statements if ( head == NULL ) { return new linkedlist { value, NULL }; } else { head->next = addNode( head->next, value ); return head; }

Collectives™ on Stack Overflow

C++ Creating a linked list using recursive function

2 Answers 2

5 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related