# Recursively insert a node in an ordered Linked List

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
{

}

//special case 2: end of list
{

}

//base case
{
Node* newNode = create_node(val);

return newNode;
}

}

• 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

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;

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

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

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


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

• 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