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;

}

unrelated: You may get some performance advantages by taking advantage of the [Member Initializer List](http://en.cppreference.com/w/cpp/language/initializer_list). It will eliminate the need to default construct `T` before assigning in the constructor's body. — user4581301, Oct 18 '17 at 20:36
I'd probably use [`std::list`](http://en.cppreference.com/w/cpp/container/list) and [`std::upper_bound`](http://en.cppreference.com/w/cpp/algorithm/upper_bound). — Fred Larson, Oct 18 '17 at 20:37
Related: `if (data < front_->data_)` does not check that `front_` is not `nullptr` before dereferencing it. The `if (front_ == nullptr)` that follows hints that this is a very strong, and fatal, possibility. — user4581301, Oct 18 '17 at 20:38
Strongly consider using a loop to iterate through the list and determine where the new item has to go. A single `if` statement isn't going to cut it. You want something like `while (front_ && data < front_->data)`, but if you take advantage of and adapt [the advice given here](https://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list), you can chop down the amount of code required dramatically. — user4581301, Oct 18 '17 at 20:45
@FredLarson `upper_bound` isn't terribly efficient if you don't have random access iterators. It might be better than a linear search, might not. If you are inserting a large number of items relative to the existing size of the list, it would be better to put them at the head or tail and sort afterwards. — Mark Ransom, Oct 18 '17 at 21:11
@MarkRansom: Valid point. Thank you. In any event, I wouldn't be likely to roll my own container and sort algorithm. — Fred Larson, Oct 18 '17 at 21:13

Remy Lebeau · Accepted Answer · 2017-10-18T22:33:16.330

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

score 0 · Answer 2 · answered Oct 18 '17 at 20:59

I did not see any code that searches the list to find where to insert the element. You have not specified the number of elements you expect to have; the performance of a linear insertion into a sorted list is on the average O(n/2), which leads to the conclusion that you will overall have O(n^2/2) [that's n-squared over 2] which is intolerable if n is, say, 10,000 and irrelevant if n < 10. I faced this problem 20 years ago with n > 200, on an 8088. There is a solution that is approximately O(log2(n)), but without knowing n I don't want to spend the time to explain it if it is not relevant.

This is not really an answer, please comment to the question instead next time. — jpcgt, Oct 18 '17 at 21:50

R Sahu · Answer 3 · 2017-10-19T15:33:23.463

Your code points to lack of clarity in your thinking.

You have to deal with the following cases:

The list is empty.
The new data is less than the values of all the items in the list.
The new data is greater than the values of all the items in the list.
The new data is in between the lowest and highest values of the items in the list.

Also, your use of "prev" and "next" seems a bit strange to me. When I think of a doubly linked list, I think of it as:

          front -> next -> next -> next -> nullptr
nullptr <- prev <- prev <- prev <- back

You seem to be using:

          front -> prev -> prev -> prev -> nullptr
nullptr <- next <- next <- next <- back

My answer corresponds to what I think you are using, the second version. If that is incorrect, the usages of "next" and "prev" need to be updated in a few places.

Case 1

Add the following at the start of your function:

if ( front_ == nullptr )
{
   Node* n = new Node(data, nullptr, nullptr);
   front_ = n;
   back_ = n;
   return SortedList<T>::iterator(n);
}

Case 2

You need:

if ( data < front_->data_ )
{
   Node* n = new Node(data, front_, nullptr);
   front_->prev_ = n;
   return SortedList<T>::iterator(n);
}

Case 3

You need:

if ( data > back_->data_ )
{
   Node* n = new Node(data, nullptr, back_);
   back_->next_ = n;
   return SortedList<T>::iterator(n);
}

Case 4

You need:

// Find the place where to insert the new Node.
Node* iter = front_;
for ( ; iter != nullptr && data < iter->data_; iter = iter->prev_ );

// Insert the new Node.
Node* prev = iter->prev_
Node* n = new Node(data, iter, prev);
prev->next_ = n;
iter->prev_ = n;
return SortedList<T>::iterator(n);

Putting it together:

typename SortedList<T>::iterator SortedList<T>::insert(const T& data)
{
   // Case 1
   if ( front_ == nullptr )
   {
      Node* n = new Node(data, nullptr, nullptr);
      front_ = n;
      back_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 2
   if ( data < front_->data_ )
   {
      Node* n = new Node(data, front_, nullptr);
      front_->prev_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 3
   if ( data > back_->data_ )
   {
      Node* n = new Node(data, nullptr, back_);
      back_->next_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 4

   // Find the place where to insert the new Node.
   Node* iter = front_;
   for ( ; iter != nullptr && data < iter->data_; iter = iter->prev_ );

   // Insert the new Node.
   Node* prev = iter->prev_
   Node* n = new Node(data, iter, prev);
   prev->next_ = n;
   iter->prev_ = n;
   return SortedList<T>::iterator(n);
}

Inserting data into a double linked list and sorting the data

3 Answers3

Case 1

Case 2

Case 3

Case 4

Putting it together: