current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite

I've written this and it works great. Is there any shorter or simpler way to achieve the same result without distinguish between cases?

Node* recursive_ordered_insert(Node* head, int val)
{
    //special case: first elem is null
    if (!head)
    {
        head = create_node(val);

        return head;
    }

    //special case 2: end of list
    if (!head->next)
    {
        head->next = create_node(val);

        return head->next;
    }

    //base case
    if (head->next && head->next->data > val)
    {
        Node* newNode = create_node(val);
        newNode->next = head->next;

        head->next = newNode;

        return newNode;
    }

    return recursive_ordered_insert(head->next, val);
}
share|improve this question
    
Just so it's said: (1) Lists are inherently ordered. What you have is a sorted list. (2) Ordered collections (like lists, and especially linked lists) are going to fight you on the sorting issue -- particularly if you're preferring recursion over iteration. A tree would be a better option overall, if you want the entries to have an ordering independent of insertion order. – cHao May 4 '15 at 16:44
up vote 5 down vote accepted

In my opinion your function is too complicated.

The function can be written simpler. I suppose that you wrote the list in C style.

Node* recursive_ordered_insert( Node *node, int value )
{
    if ( ( node == nullptr ) || !( node->value < value ) )
    {
        return create_node( value, node );
    }

    node->next = recursive_ordered_insert( node->next, value );

    return node;
}

Here is a demonstrative program. All you need is to add a recursive function that will free all allocated memory

#include <iostream>
#include <cstdlib>
#include <ctime>

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

Node * create_node( int value, Node *next = nullptr )
{
    return new Node { value, next };
}

Node* recursive_ordered_insert( Node *node, int value )
{
    if ( ( node == nullptr ) || !( node->value < value ) )
    {
        return create_node( value, node );
    }

    node->next = recursive_ordered_insert( node->next, value );

    return node;
}

std::ostream & recursive_print( Node* node, std::ostream &os = std::cout )
{
    return node == nullptr 
        ? os << std::endl 
        : ( os << node->value << ' ', recursive_print( node->next, os ) );
}

int main() 
{
    const size_t N = 10;
    Node *head = nullptr;

    std::srand( ( unsigned int )std::time( nullptr ) );

    for ( size_t i = 0; i < N; i++ )
    {
        head = recursive_ordered_insert( head, std::rand() % ( 2 * N ) );
        recursive_print( head );
    }

    return 0;
}

The program output might look like

3 
3 6 
3 6 17 
3 6 15 17 
3 6 13 15 17 
3 6 13 15 15 17 
3 6 6 13 15 15 17 
3 6 6 12 13 15 15 17 
3 6 6 9 12 13 15 15 17 
1 3 6 6 9 12 13 15 15 17
share|improve this answer
up vote 6 down vote

The assumptions your code makes are... odd. Why do you have to use recursion. In reality, your code will overflow the stack for long lists, unless you ramp up the compiler optimization, and your compiler performs tail-call optimization on the recursion.

So, yes, you can do a recursive insert, and, assuming this is some sort of educational process, your implementation appears to be reasonable, with some caveats:

  1. I don't like the "create if the list does not exist" logic in the first block. Using the head as an "output-parameter" is ugly. head should not be modified. The new head is returned anyway. The calling code should be able to tell if the head is null before it calls the insert method, and instead call a 'create' method of some sort. Additionally, that check is only ever needed once for the entire list, so it is a waste of time to check it for each level of recursion.
  2. you cannot insert at the beginning of the list. If you are intending to insert the values {4, 3, 2, 1} and your first node starts as 4 at the 'head', well, you can't insert before that..... Your code requires that the first node is always the minimum value in order for the sort-order to be maintained.

Bottom line, is your code only works for limited use-cases.

I would much rather your code had a 'sentinel' head node, which was never null, and then your actual data follows from that head position. That would reduce your code, and make the insertion process simpler, and also fix both issues above. Note that the 'head' node would be kept as part of the class fields somewhere, not passed in as an argument to the (recursive) method... in fact, the method should not be recursive

share|improve this answer
    
I agree with you when you say that the method should not be recursive, this is for educational purposes. – user1365914 May 4 '15 at 12:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.