Problem with Linked Lists - values passing/insertion

[Maartin]

Task is to put Linked List 'l1' content into Linked List 'l2' at any position.
For instance, l1 list: 1->2->3 l2 list: 4->5 I want to insert l2 values after '2'. Output: 1->2->4->5->3

MY WHOLE CODE for the moment:

#include <iostream>
using namespace std;
class Node
{
    public:
        int num;
        Node *next;
        Node (int n) { num = n; next = NULL; };
};

class List
{
    protected:
        Node *first, *last;
    public:
        Node *current;
    public:
        List () { first = last = current = NULL; };
        void add_element (int n);  
        void delete_element ();  
        void print();  

        bool is_empty () { return (first == NULL); };
        void start () { current = first; };
        bool end () { return (current == NULL); };
        void next(){if (!end())current = current -> next;};

         
        Node* find(int i); // Finds node address:
        Node* addAfter(int i, List *l2); // Inserts List l2 content after 'i' element. 

        ~List();  



};

int main()
{
     List l, l2;
 int k, i;
 cout << "Type number: (0,to stop):\n";
 cin >> k;
 while (k!=0)
 {
 l.add_element (k);
 cout << "Type number: (0, to stop):\n";  
 cin >> k;
 };
 cout << endl;

 cout << "Type 2nd list numbers: (0,to stop):\n";
 cin >> k;
 while (k!=0)
 {
 l2.add_element (k);
 cout << "Type 2nd list numbers: (0,to stop):\n";   
 cin >> k;
 };
 cout << endl;


 l.print();
 l2.print();

 cout << "After which element do you want to insert second list?" << endl;
 cin >> i;



    l.addAfter(i, &l2); // Not sure if I'm passing l2 values correctly.



    return 0;
}

void List::add_element (int n)
{
     Node *p = new Node (n);
     if (first == NULL) first = last = p;
     else last = last -> next = p;
     current = p;
};
void List::delete_element ()
{
     Node *p = first;
     if(!is_empty())
        { if (current == first) current = first-> next;
         first = first -> next;
         delete p;
         if(is_empty())last = NULL;
        }
};
void List::print()
{
    for (start(); !end(); next())
     {
        cout << current->num << endl;
     }
        cout << endl;
};

Node* List::find(int i)
{
   for (start();!end();next())
            if(current->num==i) return current;

   return NULL;
};

Node* List::addAfter(int i, List *l2)
{
 int sk;
 Node* p = NULL;
 current = find(i);

 for (start(); !end(); next())
 {
    sk = current->num; //Passing in all values, clearly doesn't work(?)



    if (current != NULL)
    {
        p = new Node(sk);
        p->next = current->next;
        current->next = p;
    }

    if (last == current) last = p;
}
    current = p;

 return p;

};

List::~List()
{
    while (!is_empty())
 {
   delete_element();
 };
 cout << "Deleted!"<< endl;
};

1. I'm not sure if I'm passing Linked list 'l2' values correctly into function addAfter as parameters.
2. I'm not sure if addAfter function works correctly. I don't get any errors, but program just stops and doesn't do what it should. Maybe someone could help me?

[D80DSL3A]

Your addAfter() function looks quite wonky. I'm not sure it does anything useful.
It should perform these tasks:

//  Find the ith node in l1
Node* p = first;
for(int k=1; k<i && p != NULL; ++k)
    p = p->next;

// link l2 into l1 here
if( p != NULL )// still pointing to valid Node
{
    l2.last->next = p->next;// rest of l1 follows l2
    p->next = l2.first;//l2 follows 1st part of l1

    l2.first = l2.last = NULL;// l2 now empty
}

Done!

edit: I missed a case. calling L1.addAfter(N, L2) for a list with N nodes means to insert L2 after L1 tail, ie. concatenate L2 to L1.
This code following line 10 above should correct:

if( l2.last->next == NULL )// there is no "rest of" l1 and l1 has a new last node
    l1.last = l2.last;

edit2: Looking at your code for addAfter() more closely I see a disaster caused by lines 126-128.
since current is never NULL in the for loop, lines 126-128 are executed every iteration of the for loop
Lines 126-128 allocate a new node and insert it in the list after the current node.
In the next iteration current points to the node newly allocated in the last iteration.
Another node is inserted, current doesn't advance through the list. The for loop never ends and the list expands forever following node #i. This is your program "stopping".

edit3: I realize you probably want to copy L2 into L1 (leaving L2 intact), not move it there (leaving L2 empty). This more closely matches what your code is attempting.
Ahem...
Start as before. Find the node to insert after:

Node* p = first;
for(int k=1; k<i && p != NULL; ++k)
    p = p->next;

Then insert new nodes as copies from L2. Your code doesn't advance through L2 at this point:

if( p != NULL )// still in list
{
   const Node* it2 = L2.first;
    while( it2 != NULL )
    {
        Node* newNode = new Node( it2->num );
        newNode->next = p->next;
        p->next = newNode;
        p = newNode;// to insert after next iteration
        it2 = it2->next;// next node in L2
    }

    if( !it2->next == NULL )
        tail = it2;// new tail
}

I've been testing this on a doubly linked list class of mine, and it's all working there.
Now, you'd think the code for this on a doubly linked list would be more complicated but due to a constructor definition in the node class, it's actually simpler.
From my dnode class:

// make all assignments required to splice this node into list
dnode( int X, dnode* Prev, dnode* Next ): x(X), prev(Prev), next(Next)
    {
        if(prev) prev->next = this;
        if(next) next->prev = this;
    }

So my code in the while loop is:

while( it2 )
        {
            new dnode( it2->x, it, it->next );// I don't even need to catch the returned address!!
            it = it->next;
            it2 = it2->next;
        }

My dList class has 2 new functions, addListAfter_move() and addListAfter_copy() now.
Thank you!

edit4: Finally, I've combined approaches for the copy version.
1. Create a copy of L2 in the function.
2. Splice this copy into L1 as in the 1st move approach.

[Maartin]

Hey @fun2code. I want to stick to Single-node linked list for now, so I understand it myself as well.
Basically, what I need is: after using addAfter() function, I can freely get rid of the L2 and just get the new L1.

Node* List::addAfter(int i, List *l2)
{
  //  Find the ith node in l1
Node* p = first;
for(int k=1; k<i && p != NULL; ++k)
    p = p->next;

// link l2 into l1 here
if( p != NULL )// still pointing to valid Node
{
    l2.last->next = p->next;// rest of l1 follows l2
    if( l2.last->next == NULL )// there is no "rest of" l1 and l1 has a new last node
            l1.last = l2.last;
    p->next = l2.first;//l2 follows 1st part of l1

    l2.first = l2.last = NULL;// l2 now empty
}
};

I'm getting error @line 11. I guess that's because my 'last' node is protected and I can't access it by l2.last (which would work, if it would be a public node?) I certainly can't change 'last' to public, because then I would ignore my teachers instructions, haha. Is there any way I can get rid of this problem?

[D80DSL3A]

I am confused by that error because last and next are used freely in your own code (in starting post).
Even if last is private (or protected) it can be referenced freely in List class member functions. The access restriction only applies outside member functions (hence the need for friend functions).

If access to next is restricted in the Node class (protected or private) then you would have to use getter functions in the List class member functions.eg line 14 above would be: p->getNext() = l2.first; where getNext() must return next by reference.

I wish you had posted some error data. I suspect the errors actually concern how L2 is dereferenced. I pass L2 by reference in my own code hence L2.last, but you passed a pointer to L2 so in your code the "indirect member reference operator" -> must be used L2->last.

Otherwise, I think your new code is good, aside from the need to return a Node* from the function as you've declared it will do. You should be getting error messages about this too.
Purpose in returning a value? I see in your code line 71 the return value isn't saved when addAfter() is called.
Mine returns void.

[D80DSL3A]

I keep forgetting you're passing a pointer to L2.
This code should be right.

void List::addAfter(int i, List *L2)const
{
Node* p = first;
for(int k=1; k<i && p != NULL; ++k)
    p = p->next;

if( p != NULL )// still pointing to valid Node
{
    // create copy of L2 here
//    List L3(*L2);  <= this would be great, but you would need to define a custom copy nstructor.
    List L3;
    for( const Node* it = L2->first; it != NULL; it = it->next )
        L3.addElement( it->num );

   // splice L3 into *this List after Node *p
    L3.last->next = p->next;
    if( L3.last->next == NULL )
            last = L3.last;// no l-> here
    p->next = L3.first

    L3.first = L3.last = NULL;
}

}

If you have a copy constructor

List::List( const List& L ): first(NULL), last(NULL)
{
    for( const Node* it = L.first; it != NULL; it = it->next )
       addElement( it->num );
}

you can create the needed copy just by passing L2 by value.
I think the best signature for this function is therefore:

// L2 passed by value. Copy needed is created for us automatically.
void List::addAfter(int i, List L2)const
{
Node* p = first;
for(int k=1; k<i && p != NULL; ++k)
    p = p->next;

if( p != NULL )
{
   // splice L2 into *this List after Node *p
    L2.last->next = p->next;
    p->next = L2.first
    if( L2.last->next == NULL )
            last = L2.last;// new last node

    L2.first = L2.last = NULL;// prepare for call to ~List(). L2 will be destroyed now.
}
    
}