Implementation of stackoverflow answer http://stackoverflow.com/a/36086098/16582

so36086098.cpp

// Implementation of stackoverflow answer http://stackoverflow.com/a/36086098/16582

#include <iostream>

using namespace std;

class cList
{

public:
    struct Node
    {
        Node *prev;
        Node *next;
        int value;
    };

    /** Special cases for placing a new node */
    enum class eFind
    {
        list_empty,         // the list was empty
        before_first,       // the new node goes before the first node in list
        before_node,        // the new node goes before the specified node
        after_last,         // the new node goes after the last node in the list
    };

    /** constructor */
    cList()
        : head( 0 )
        , tail( 0 )
    {
    }

    /** Insert a value in its sorted position in the list */
    void InsertIt( int value )
    {
        if( InsertFirstNode( value ))
            return;
        eFind place;
        Node * n = FindSmallestGreaterThan( place, value );
        InsertBefore( place, n, value );
    }

    /** Insert first node with value
        @return true if list empty */
    bool InsertFirstNode( int value )
    {
        if( head )
            return false;

        head = new Node;
        tail = head;
        head->next = 0;
        head->value = value;

        return true;
    }

    /** Find node with smallest value greater than given

        @param[out] place eFind enumeration, one of list_empty,before_first,before_node,after_last
        @param[in] value being inserted

        @return n node before which value should be placed

        Assumes sorted list exist.
    */
    Node * FindSmallestGreaterThan( eFind & place, int value )
    {
        if( ! head )
        {
            place = eFind::list_empty;
            return 0;
        }

        if( head->value > value )
        {
            place = eFind::before_first;
            return 0;
        }

        Node * t = head;
        while( t )
        {
            if( t->value > value )
            {
                place = eFind::before_node;
                return t;
            }
            t = t->next;
        }
        place = eFind::after_last;
        return 0;
    }

    /** Insert new value before a node

        @param[in] place eFind enumeration, one of list_empty,before_first,before_node,after_last
        @param[in] n node after which to place value
        @param[in] value
        */
    void InsertBefore( eFind place, Node * n, int value )
    {
        Node * created = new Node;
        created->value = value;
        switch( place )
        {

        case eFind::before_first:
            created->prev = 0;
            created->next = head;
            head->prev = created;
            head = created;
            break;

        case eFind::before_node:
            n->prev->next = created;
            created->prev = n->prev;
            created->next = n;
            n->prev = created;
            break;

        case eFind::after_last:
            tail->next = created;
            created->prev = tail;
            created->next = 0;
            tail = created;
            break;

        default:
            break;

        }
    }

    void Print()
    {
        Node * t = head;
        while( t )
        {
            std::cout << t->value <<" ";
            t = t->next;
        }
        cout << std::endl;
    }


private:

    Node *head;
    Node *tail;

};

int main()
{
    cList L1;
    L1.InsertIt( -1);
    L1.InsertIt( 0);
    L1.InsertIt( 7);
    L1.InsertIt( 1);
    L1.InsertIt( 2);
    L1.InsertIt( 2);
    L1.Print();

    cList L2;
    L2.InsertIt( 2);        // this isn't the smallest!
    L2.InsertIt( -1);
    L2.InsertIt( 7);
    L2.InsertIt( 1);
    L2.InsertIt( 2);
    L2.InsertIt( 2);
    L2.Print();


    return 0;
}