Issue when adding element into sorted linked list C++

Question

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?

Because l and cur are references, you end up changing the caller's pointer to the start of the linked list. Accept l by value instead.... — Tony Delroy
– Tony Delroy, Commented Jan 20, 2015 at 2:48
@TonyD yeal, but since l can be an empty list, just accept l by value is not enough I think.. — justmscs
– justmscs, Commented Jan 20, 2015 at 2:56
if you are doing serious code, name it add_ordered_erase_2before this is highly unexpected that something will get deleted from an add function. Secondly, I hope you don't intend to use this seriously, because of KISS principle and basic performance principles (vector + sort usually outperforms anything). But otherwise OK for academic purpose or training. — v.oddou
– v.oddou, Commented Jan 20, 2015 at 5:28

justmscs · Accepted Answer · 2015-01-20 03:14:53Z

1

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);
    }
}

edited Jan 20, 2015 at 3:14

answered Jan 20, 2015 at 2:52

justmscs

7564 silver badges13 bronze badges

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

1 Comment

Alex Over a year ago

Thanks for this :) I didn't realize I needed to just use a normal pointer. As for the bug, yeah if something is inserted into the beginning of the list, like 0->1->2 where 0 is the thing getting inserted, it ends up coming out like 1->0->2. I'm also working on trying to fix that.

Collectives™ on Stack Overflow

Issue when adding element into sorted linked list C++

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related