insertion function to insert elements in a linked list at tail

Question

I want to implement insertion of element at tail of linked list, I want to do it using member function, currently I'm able to do it by creating a function outside of struct, please help me what should be modified to implement it as member function.

my conventional approach:

#include<iostream>
using namespace std;
struct node{
    int data;
    node *next;
};
node * Insert(int v,node *head){
    if(head==NULL){
        node *temp=new node;
        head=temp;
        temp->data=v;
        temp->next=NULL;
         return head;
    }
    else{
        node *temp=head;
        while(temp->next!=NULL){
            temp=temp->next;
        }
        node *temp_new=new node;
        temp_new->data=v;
        temp_new->next=NULL;
        temp->next=temp_new;
        return head;
    }
}

Is there anything in particular about member functions tripping you up? — , Jul 26 '21 at 14:18
In my opinion, it would make more sense to create a class which represents the linked list as a whole, instead of only a single node, and to add the member function to that class instead. — Andreas Wenzel, Jul 26 '21 at 14:19
What happens if you copy your function into the struct and build? — Lajos Arpad, Jul 26 '21 at 14:25
your free function works in a way a member fucntion cannot. You can pass a `nullptr` to your insert and it will create a `node` as the new `head`. But you cannot call a member `insert` before you have a `node`. If you write a class that represents the whole list (not only a single node) the transition will be much simpler — 463035818_is_not_an_ai, Jul 26 '21 at 14:25
@Lajos Arpad it doesn't work, i tried to also modify and implement all the concept i know related to member function. — def __init__, Jul 26 '21 at 14:27
@def__init__ " implement all the concept i know related to member function." Can you show us what you tried please? What you are asking is the absolute bare minimum definition of a member function, so it's important for the answer to be tailored to your current understanding of it. — , Jul 26 '21 at 14:30
@def__init__ can you post your try and the error you received? — Lajos Arpad, Jul 26 '21 at 14:32
@Frank actually earlier i have implemented member function for class having members as double data type or arrays but this feels difficult for me to implement and to get desired result. — def __init__, Jul 26 '21 at 14:33

francesco · Accepted Answer · 2021-07-26T17:04:21.077

This is a working example. The idea is that, from the member function, you recursively call node::Insert until you reach the last element, and then only there you create the next one.

#include <iostream>

struct node{
    int data;
    node *next = nullptr;
    node *Insert(int v);
};

node *node::Insert(int v)
{
    if (next == nullptr)
    {
        next = new node;
        next->data = v;
        return next;
    }
    else
    {
        return next->Insert(v);
    }
}

int main()
{
    node a{3};
    a.Insert(2);
    a.Insert(5);
    std::cout << a.data << ' ' << a.next->data << ' ' << a.next->next->data << ' ' << std::endl;
    
    return 0;
}

See it live on Coliru.

Also: avoid using namespace std.

Addition

As noted in the comment, it is probably a good idea to unroll the recursion. Here is a nonrecursive version of the above code:

#include <iostream>

struct node{
    int data;
    node *next = nullptr;
    node *Insert(int v);
};

node *node::Insert(int v)
{
    if (next == nullptr)
    {
        next = new node;
        next->data = v;
        return next;
    }
    else
    {
        auto p = next;
        while (p->next != nullptr)
            p = p->next;
        p->next = new node;
        p = p->next;
        p->data = v;
        return p;
    }
}

int main()
{
    node a{3};
    a.Insert(2);
    a.Insert(5);
    std::cout << a.data << ' ' << a.next->data << ' ' << a.next->next->data << ' ' << std::endl;
    
    return 0;
}

See it live on Coliru.

Hmm: recursion is a very bad idea here. Why not do it iteratively? But anyway, finding the last element before each insertion is becoming more and more inefficient the longer the list gets. Hint: google _"Schlemiel the painter's algorithm"_ — Jabberwocky, Jul 26 '21 at 16:28

463035818_is_not_an_ai · Answer 2 · 2021-07-26T15:05:07.553

Just by looking at what your insert currently does, it does not make sense to make it a member of node. You can call your insert like this:

 node* root = nullptr;
 root = Insert(42,root);

to create a list with a single element. On the other hand, you cannot call a member function of node before you have an instance of type node.

The transition is simpler if you write a class that represents the list, not only a single node. Start with this:

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

Now the above two lines could look like this:

linked_list l;
l.insert(42);

All you need to do is to move the free function into the class and instead of using the parameter head you use the member head. Also there is no need to return the head anymore:

#include<iostream>
using namespace std;
struct node{
    int data;
    node *next;
};
struct linked_list {
    node* head = nullptr;
    void Insert(int v){
        if(head==nullptr){
            head =new node;
            head->data=v;
            head->next=nullptr;
        }
        else{
            node *temp=head;
            while(temp->next!=nullptr){
                temp=temp->next;
            }
            node *temp_new=new node;
            temp_new->data=v;
            temp_new->next=nullptr;
            temp->next=temp_new;
        }
    }
};

Note that I did not change anything on the implementation (only NULL -> nullptr and void return, if it had a bug then it still has a bug now ;). You should also provide appropriate constructors for node and linked_list and destructors, because currently this leaks all allocated memory. And last but not least you need to read about the rule of 3/5: What is The Rule of Three?

insertion function to insert elements in a linked list at tail

2 Answers2