CODEWITHSUNDEEP
c++sortingtemplatespointerslinked-list
Alex
Alex

Reputation: 2299

Issue when adding element into sorted linked list C++

I'm having a strange issue in an assignment, where I am supposed to write a template method for insertion into a sorted linked list.

Here is the weird thing. If I have a linked list, and the value I'm adding is at the end of the linked list, when I add the value, every other value before the second to last, and newly inserted value get deleted. This is an illustration of what happens:

1->3->5->nullptr // starting linked list
add_ordered_i(list, 8); // add 8 to the linked list
5->8->nullptr // what ends up being output

Before I go into this issue here is the templated linked list class I am given.

#include <string>
#include <iostream>
#include <fstream>

template<class T>
class LN {
  public:
    LN ()                        : next(nullptr){}
    LN (const LN<T>& ln)         : value(ln.value), next(ln.next){}
    LN (T v, LN<T>* n = nullptr) : value(v), next(n){}
    T      value;
    LN<T>* next;
};

template<class T>
std::ostream& operator << (std::ostream& outs, LN<T>* l) {
  for (LN<T>* p = l; p != nullptr; p = p->next)
    std::cout << p->value << "->";
  std::cout << "nullptr";
  return outs;
}

template<class T>
void add_ordered_i (LN<T>*& l, T value)
{
}

And here is what my attempt was for the function add_ordered_i:

template<class T>
void add_ordered_i (LN<T>*& l, T value) {
    LN<T>*& cur = l;
    LN<T>* prev = new LN<T>();
    if(cur == nullptr)  {
        cur = new LN<T>(value);
        return;
    }
    while(cur->next != nullptr)
    {
        if(value < cur->next->value || cur->next == nullptr)
            break;
        cur = cur->next;
    }
    if(cur->next == nullptr) {
        if(value < cur->value) {
            cur = new LN<T>(value, cur);
            return;
        }
        cur->next = new LN<T>(value);
        return;
    } else {
        prev = cur->next;
        cur->next = new LN<T>(value,prev);
        return;
    }
}

I'm not sure why this is happening. Especially because in main() I can do:

while(list->next != nullptr)
    p = p->next
p->next = new LN<int>(5);

And it will insert the number 5 at the end of the list, no matter how many elements are currently in it. Am I doing something wrong when referencing the list in my function? Or what is causing it to delete almost every element except the previous and the newly added one?

Upvotes: 0

Views: 147

Answers (1)

justmscs
justmscs

Reputation: 756

That's because cur is a reference in add_ordered_i and you have cur = cur->next which also modify l.

I made a few changes and it works for me.

template<class T>
void add_ordered_i (LN<T>*& l, T value) {
    LN<T>* cur = l;//just a normal pointer will be fine
    if(cur == nullptr)  {
        l = new LN<T>(value);//a empty list
        return;
    }
    while(cur->next != nullptr)
    {
        if(value < cur->next->value)
            break;
        cur = cur->next;
    }
    if(cur == l) {
        l = new LN<T>(value, cur);//add to head of list
    } else {
        cur->next = new LN<T>(value,cur->next);
    }
}

Upvotes: 1

Related Questions