maintaining sorted link list

Question

Hi again,

I'm trying to create and maintain a sorted link list. Every new element should be inserted in a way that the list remains sorted. I have been able to code it but am not too happy with my code.

Basically there are 4 conditions that need to be satisfied according to me and in my attempt to achieve all of them i think i have made the code more complicated that it should be.

Just want to know if anyone has coded it more efficiently and if you can tell me how to improve the insert function here. This is my working code below and the conditions in comments. For keeping it small I have not posted the functions to remove elements, destroy list etc.

#include <iostream>

    using namespace std;

    struct node{
        int _val;
        node* _next;
    };

    void printList(node **s){

        node *t = *s;
        while(t){
            cout << t->_val << endl;
            t = t->_next;
        }
    }

    void insertSortElement(node** s, int val){

        node* t = *s;
        if(t){
            if(t->_next == NULL || (t->_val > val)){
                node* p = new node();
                p->_val = val;
                if(t->_val > val){
                    //3. More than 1 element in the list but 1st element > val
                    p->_next = t;
                    *s = p;
                }
                else{
                    //2. Only 1 element in the list and < val
                    t->_next = p;
                }
            }
            else{
                //4. More than 1 element and 1st < val
                node* prev = 0;
                while(t){
                    if(t->_val > val)
                        break;
                    prev = t;
                    t = t->_next;
                }
                node* p = new node();
                p->_val = val;
                p->_next = t;
                prev->_next = p;
            }
        }
        else{

            //1. no element in the list
            node* p = new node();
            p->_val = val;
            p->_next = NULL;
            *s = p;
        }
    } 

    int main(){
        struct node* s = 0 ;

        insertSortElement(&s,5);
        insertSortElement(&s,6);
        insertSortElement(&s,4);
        insertSortElement(&s,2);
        insertSortElement(&s,8);
        insertSortElement(&s,1);
        printList(&s);
    }

EDIT:

Found another implementation, much simpler than mine and handles all cases

void insertSorted(node**s , int val){
        node* current = *s;

                if(current == NULL || current->_val >= val){
                        node* p = new node();
                        p->_val = val;
                        p->_next = current;
                        *s = p;
                }
                else{

                        while(current->_next != NULL || current->_next->_val < val)
                                current = current->_next;

                        node*  p = new node();
                        p->_val = val;
                        p->_next = current->_next;
                        current->_next = p;
                }
}

Answer 1

I think you should write a method insertElement and then rewrite insertSortedElement as "search for the position to insert and then just call insertElement there" - I think this would clean up the code and make it much more logical and readable.

This way, you can code more modular. All weird edge cases can be handled by insertElement and you can optimize the insertion and position search seperately which will lead to much less confusion.

Some pseudo-code:

insertElement(node old_node, value val)
  allocate memory for new node new_node
  new_node.val = val
  new_node.next = old_node
  new_node.prev = old_node.prev

insertSortedElement(value val)
  actnode = first node
  while actnode.next != NULL
    if (actnode.val >= val)
      insertElement(actnode, val)
      break;
    actnode = actnode.next

Should be that simple, hope I didn't forget anything...

Answer 2

A faster approach will be using the binary search to find the right place to insert. It is called "skip list".

Also you can use santinels to avoid checking special cases for first and last elements.

Answer 3

Err... why? Isn't this what std::multiset is for?

#include <set> //for std::multiset
#include <iterator> //for std::ostream_iterator
#include <algorithm> //for std::copy
#include <iostream> //for std::cout

int main()
{
    //Put things in sorted collection.
    std::multiset<int> collection;
    collection.insert(5);
    collection.insert(6);
    collection.insert(4);
    collection.insert(2);
    collection.insert(8);
    collection.insert(1);

    //Print them to show sort.
    std::copy(collection.begin(), collection.end(), std::ostream_iterator(std::cout, "\n"));
}