Sorting linked list while inserting a node

When iterating over the list to find the position to insert a new node, you do:

  tail = tail -> prev;

But the tail variable is passed by a reference, that is you modify the tail member of yout List object, thus destroying its consistency.

Use another temporary variable, named, say current or position to walk along the list, and don't modify tail unless you're appending a new node at the end of the list.

EDIT example approach

struct Node {
    Node(int val);

    Node *prev;
    Node *next;
    int value;
};

struct List{
    List() : head(nullptr), tail(nullptr) {}
    void insert(int value);

    Node *head;
    Node *tail;
};

Node::Node(int val) :
    value(val), next(nullptr), prev(nullptr)
{
}

void List::insert(int value) {
    Node *tmp = new Node(value);

    if(head == nullptr) {
        head = tmp;
        tail = tmp;
        return;
    }

    Node *pos;  // find the node greater or equal to 'value'
    for(pos = head; pos && pos->value < value; pos = pos->next)
        ;

    if(pos) {    // appropriate pos found - insert before
        tmp->next = pos;
        tmp->prev = pos->prev;
        tmp->next->prev = tmp;
        if(tmp->prev)       // there is some predecessor
            tmp->prev->next = tmp;
        else
            head = tmp;     // making a new first node
    } else {     // pos not found - append at the end
        tmp->next = nullptr;
        tmp->prev = tail;
        tail->next = tmp;
        tail = tmp;
    }
}

You want to do two things: find position in list where new node belongs AND insert new node at a position. So, write two functions, one to do each task. Then you can test and debug them separately before integrating. This will be much more straight forward. Further reccomendation: write unit tests for each function, before implementing the functions.

/** Find node with largest value less than given 
    Assumes sorted list exist.  If empty, throws exception
*/
Node & FindLessThan( int value );

/** Inset new node after given with value */
InsertAfter( Node& n, int value );

It will also be handy to have a function to insert the first node, if the list is empty,

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

The point is that you should hide all the pointer twiddling in functions that can be tested, so you can write a comprehensible mainline that will work first time:

if( ! InsertFirstNode( value ) )
   InsertAfter( FindLessThan( value ), value );

Since you are using C++, make your list a class and the functions members.

Implementation details: You have to worry about special cases: new value goes before head or after tail. So I suggest using an enumeration to handle these.

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

It also turns out to be slightly easier ( less code ) to do an InsertBefore rather than InsertAfter. You can see the code running at cpp.sh/4xitp or the github gist

1. You can't initialize members inside a structure :

struct List
{
    Node *head;
    Node *tail;
};

2.(a) Prototypes of functions insertIt and insertNode are wrong.You are passing head and tail using pass by reference.It should be as follows :

void insertIt(Node * head ,Node * tail ,int value)

void insertNode(Node * head,Node * tail,int value)

2.(b) When you create a node in else part you should set the next and prev pointers of your new node to NULL :

tmp->prev=NULL;
tmp->next=NULL; 

2.(c) As you have passed tail using pass by reference whatever changes you make inside while loop on tail are reflected in program.Hence use temporary pointer of type Node.

3. Also the design you are using is not good.Hence I would advice you to change it.This is my implementation of linked list :

main()
{
    struct List Q;
    Initialize_list(&Q);
    Insert_it(&Q,12);
}
void Initialize_list(struct List *L)
{
    L->head=NULL;
    L->tail=NULL;
}

The problem is the check value < tail->prev->value in the while loop head. This does not check that tail->prev != nullptr is true. This is a problem for the case that head == tail and value < head->value. If head != tail, your code would indeed work, because the first time value < tail->prev->value is evaluated, tail->prev != nullptr is true and the case head->next == tail would be caught by the code in the loop body. The correct check would be tail->prev != nullptr && value < tail->prev->value. This first checks that tail->prev can be derefenced.

Then you may end with tail->prev == nullptr after finishing the while loop (due to the new condition). The check for that can be moved out of the loop, leading to the following code:

while (tail->prev != nullptr && value < tail->prev->value) {
    tail = tail->prev;
}
if (tail->prev == nullptr) {
    // Prepend node to the list
    return;
}
// Insert node in front of tail

EDIT: You can still check the condition tail->prev == nullptr within the loop; the check after the loop would then only be useful to catch the case head == tail && value < head->value. Not doing the check in the loop has the benefit of a shorter and (in my opinion) mode readable code.

This might be the code you're looking for ;-) You can run it as-is in VS2013. It simplifies your insert function to just a few if-statements. And that can be further simplified with use of terminal elements for head & tail.

I hope this helps :-)

struct Node
{
    int value; Node *prev, *next;
};

struct DoublyLinkedSortedList
{
    Node *head = nullptr, *tail = nullptr;

    void insert(int value)
    {
        // Find first node bigger then the new element, or get to the end of the list
        Node* node = head;
        while (node && node->value <= value) { node = node->next; }

        // Once found, insert your new element before the currently pointed node, or at the end of the list
        node = new Node{ value, node?node->prev:tail, node };
        if (node->prev) node->prev->next = node; else head = node;
        if (node->next) node->next->prev = node; else tail = node;
    }
};

#include <climits>
#include <iostream>

using namespace std;

int main()
{
    cout << "This is a DoublyLinkedList test." << endl << endl;

    // test the list
    DoublyLinkedSortedList list;
    list.insert(234);
    list.insert(INT_MIN);
    list.insert(17);
    list.insert(1);
    list.insert(INT_MAX);
    list.insert(-34);
    list.insert(3);
    list.insert(INT_MAX);
    list.insert(INT_MIN);
    list.insert(9);
    list.insert(7);

    // print nodes in order;
    cout << "This are the contents of the linked list front to back" << endl << endl;
    for (Node* curr = list.head; curr != nullptr; curr = curr->next) { cout << curr->value << "; "; }
    cout << endl << endl << "This are the contents of the linked list back to front" << endl << endl;
    for (Node* curr = list.tail; curr != nullptr; curr = curr->prev) { cout << curr->value << "; "; }
    cout << endl << endl;

    system("pause");
}