Inserting data into a double linked list and sorting the data

Question

I would like to insert the data in a sorted manner in a sorted linked list. I am able to insert the data but it is not sorted. Can anyone help me as to what i am doing wrong? Here is my function:

typename SortedList<T>::iterator SortedList<T>::insert(const T& data) {


if (data < front_->data_) {
    Node* n = new Node(data, front_, nullptr);

    //if empty
    if (front_ == nullptr) {
        //make back pt to node
        back_ = n;
    }
    else {
        //make front's previous point to node
        front_->prev_ = n;
    }
    //make front point at node
    front_ = n;
    return SortedList<T>::iterator(n);
}
else {
    Node* nn = new Node(data, nullptr, back_);

    //if empty
    if (front_ == nullptr) {
        //make front_ pt to node
        front_ = nn;
    }
    else {
        //make back's next point to node
        back_->next_ = nn;
    }
    //make back point at node
    back_ = nn;
    return SortedList<T>::iterator(nn);
}

And here is my class

class SortedList{

struct Node {
    T data_;
    Node* next_;
    Node* prev_;
    Node(const T& data = T{}, Node* nx = nullptr, Node* pr = nullptr) {
        data_ = data;
        next_ = nx;
        prev_ = pr;
    }
};

Node* front_;
Node* back_;
int sizelist;

}

Answer 1

You are not checking front_ for nullptr before accessing front_->data.

But more importantly, you are not trying to insert the data in any kind of sorted position. You are inserting only at the very front or very back of the list. To insert in the middle, you have to scan through the list looking for the correct place to insert at.

Try something more like this instead:

class SortedList{

    struct Node {
        T data_;
        Node* prev_;
        Node* next_;

        Node(const T& data = T{}, Node* pr = nullptr, Node* nx = nullptr)
            : data_(data), prev_(pr), next_(nx)
        {
        }
    };

    Node* front_;
    Node* back_;
    int size_;

    ...

    iterator insert(const T& data);
};

typename SortedList<T>::iterator SortedList<T>::insert(const T& data)
{
    Node *nn = front_;
    while ((nn) && (data >= nn->data_)) {
        nn = nn->next_;
    }

    Node *n = new Node(data);
    if (nn)
    {
        n->prev_ = nn->prev_;
        n->next_ = nn;
        if (nn->prev_) nn->prev_->next = n;
        nn->prev = n;
    }
    else
    {
        n->prev_ = back_;
        if (back_) back_->next_ = n;
        back_ = n;
    }

    if (front_ == nn) front_ = n;

    ++size_;

    return iterator(n);
}