inserting a node at the end of linked list recursivly

Question

typedef struct node
{
    int a;
    struct node *next;
}node;
void generate(struct node **head)
{
    int num = 10, i; //the num here is the length
    struct node *temp;

    for (i = 0; i < num; i++)
    {
        temp = (struct node*)malloc(sizeof(struct node));
        temp->a = 10-i;
        if (*head == NULL)
        {
            *head = temp;  //each time add another node to the start
            (*head)->next = NULL;
        }
        else
        {
            temp->next = *head;
            *head = temp;
        }
    }
}
void addSpecific(node* head,int n)
{
    node* temp = NULL;
    if (head->next == NULL)
    {
        temp = (node*)malloc(sizeof(node*)); //allocating memory
        (temp)->a = n;  //adding the wanted value
        (temp)->next = NULL; //making the new node to point to the end
        head->next = temp; //and the previous one to point to temp
    }
    else
    {
        addSpecific(head->next, n); //if this is not the wanted node we need to move to the next node
    }
}
void deleteNode(struct node **head)
{
    struct node *temp;
    while (*head != NULL)
    {
        temp = *head;
        *head = (*head)->next; //going to the next node
        free(temp); //free the allocated memory
    }
}
int main()
{
    struct node *head = NULL;

    generate(&head);
    addSpecific(head, 7);
    display(head);
    deleteNode(&head);
    system("PAUSE");
    return 0;
}

I was trying to insert new node at the end using recursion, but the free memory (delete) function make an expansion, and I couldn't find the problem. I tried the generating function and adding the node at the end and it worked but the complier alert me for "heap corruption".

Answer 1

# For reference:
#
# SinglyLinkedListNode:
#     int data
#     SinglyLinkedListNode next


def insertNodeAtTail(node, data):
    if node is None:
        last = SinglyLinkedListNode(node_data=data)
        last.next = None
        return last
    
    if node.next is None:
        last = SinglyLinkedListNode(node_data=data)
        last.next = None
        node.next = last
        return node
    
    node.next = insertNodeAtTail(node.next, data)

    return node

Answer 2

The function can look the following way as it is shown in the following demonstrative program

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

typedef struct node
{
    int a;
    struct node *next;
} node;

void addSpecific( node **head, int n )
{
    if ( *head == NULL )
    {
        *head = malloc( sizeof( node ) ); //allocating memory
        ( *head )->a    = n;  //adding the wanted value
        ( *head )->next = NULL; //making the new node to point to the end
    }
    else
    {
        addSpecific( &( *head )->next, n ); //if this is not the wanted node we need to move to the next node
    }
}

void display( node *head )
{
    for ( ; head != NULL; head = head->next ) printf( "%d ", head->a );
    printf( "\n" );
}

int main( void ) 
{
    const int N = 10;
    node *head = NULL;

    for ( int i = 0; i < N; i++ ) 
    {
        addSpecific( &head, i );

        display( head );
    }

    return 0;
}

The program output is

0 
0 1 
0 1 2 
0 1 2 3 
0 1 2 3 4 
0 1 2 3 4 5 
0 1 2 3 4 5 6 
0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7 8 
0 1 2 3 4 5 6 7 8 9 

As for the function deleteNode then it can look for example the following way

void deleteNode( node **head )
{
    for ( node *current = *head; current != NULL; )
    {
        node *temp  = current;
        current = current->next; //going to the next node
        free( temp ); //free the allocated memory
    }

    *head = NULL;
}

As for this implementation of the function

void deleteNode( node **head )
{
    while ( *head != NULL )
    {
        node *temp  = *head;
        head = &( *head )->next; //going to the next node
        free( temp ); //free the allocated memory
    }
}

then it has undefined behavior because it tries to access a data member of the structure object that was already deleted.

Or you can make the function recursive. For example

void deleteNode( node **head )
{
    if ( *head != NULL )
    {
        deleteNode( &( *head )->next );
        free( *head );
        *head = NULL;
    }
}

Answer 3

A bit off-topic, but it is quite convenient to maintain single-linked lists with two pointers, rather than one. This way you can prepend and append the list in O(1) without having to use recursion. E.g.:

struct Node
{
    struct Node* next;
};

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

void List_init(struct List* list) {
    list->head = 0;
    list->tail = &list->head;
}

void List_append(struct List* list, struct Node* node) {
    node->next = 0;
    *list->tail = node;
    list->tail = &node->next;
}

void List_prepend(struct List* list, struct Node* node) {
    node->next = list->head;
    list->head = node;
    if(list->tail == &list->head)
        list->tail = &node->next;
}

void List_remove(struct List* list, struct Node* node) {
    struct Node *cur = list->head, **prev = &list->head;
    while(cur && cur != node) {
        prev = &cur->next;
        cur = cur->next;
    }
    if(cur) {
        if(!(*prev = node->next))
            list->tail = prev;
    }
}