Add element to ordered doubly linked list using recursive

Question

I want to add new node to my ordered doubly linked list by using recursive function. I wrote function like this, but it doesnt work. I think the problem is with a pointer on previous elemen.

int create_and_add_node(struct dll_node **front, int number){
    struct dll_node *new_node = (struct dll_node *)malloc(sizeof(struct dll_node));

    if(!new_node)
        return -1;
    new_node->data = number;
    new_node->next = (*front);
    new_node->prev = (*front)->prev;
    *front = new_node;
    return 0;
}

int add_node(struct dll_node **front, int number){
    if(*front != NULL && (*front)->data < number)
        return add_node(&(*front)->next, number);
    else
        return create_and_add_node(front, number);
}

The definition of struct dll_node is

struct dll_node {
    int data;
    struct dll_node *prev, *next;
};

Answer 1

The task is not simple as it seems at the first glance.

If you defined a doubly-linked list then such a list shall have two pointers: the first one that points to the head node of the list and the second one that points to the last node of the list. Otherwise there is no great sense to define a doubly linked list.

So the recursive function that inserts nodes in order in the list shall deal with two pointers to update the list correctly.

Below there is a demonstrative program that shows how such a recursive function can be implemented for a double-linked list.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct dll_node
{
    int data;
    struct dll_node *next;
    struct dll_node *prev;
};

struct dll_list
{
    struct dll_node *head;
    struct dll_node *tail;
};

int add_node( struct dll_node **head, struct dll_node **tail, int number )
{
    if ( *head == NULL )
    {
        *head = malloc( sizeof( struct dll_node ) );
        int success = *head != NULL;

        if ( success )
        {
            ( *head )->data = number;
            ( *head )->next = NULL;
            ( *head )->prev = *tail == NULL ? NULL : *tail;
            *tail = *head;
        }

        return success;
    }
    else if ( number < ( *head )->data )
    {
        struct dll_node *new_node = malloc( sizeof( struct dll_node ) );
        int success = *head != NULL;

        if ( success )
        {
            new_node->data = number;
            new_node->next = *head;
            new_node->prev = ( *head )->prev;
            ( *head )->prev = new_node;
            *head = new_node;
        }

        return success;
    }
    else
    {
        return add_node( &( *head )->next, tail, number );
    }
}

int add_data( struct dll_list *list, int number )
{
    return add_node( &list->head, &list->tail, number  );
}

void display( struct dll_list *list )
{
    for ( struct dll_node *current = list->head; current != NULL; current = current->next )
    {
        printf( "%d -> ", current->data );
    }

    puts( "null" );
}

void reverse_display( struct dll_list *list )
{
    for ( struct dll_node *current = list->tail; current != NULL; current = current->prev )
    {
        printf( "%d -> ", current->data );
    }

    puts( "null" );
}

int main(void) 
{
    struct dll_list list = { .head = NULL, .tail = NULL };

    const int N = 10;

    srand( ( unsigned int )time( NULL ) );

    for ( int i = 0; i < N; i++ )
    {
        add_data( &list, rand() % N );
    }

    display( &list );
    reverse_display( &list );

    return 0;
}

The program output might look like

0 -> 4 -> 5 -> 6 -> 6 -> 6 -> 7 -> 8 -> 9 -> 9 -> null
9 -> 9 -> 8 -> 7 -> 6 -> 6 -> 6 -> 5 -> 4 -> 0 -> null