Singly linked list various questions

[nowy20180820]

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

struct node
{
    int key;
    struct node *next;
};

typedef struct node node;

void ListInit(node **head)
{
    (*head) = NULL;
}

int ListIsEmpty(node *head)
{
    return head == NULL;
}

void ListPrint(node *head)
{
    node *p = head;
    int counter = 0;
    while(p != NULL)
    {
        printf("%d -> ",p->key);
        p = p->next;
        counter++;
    }
    printf("NULL \n");
    printf("Liczba wezlow listy : %d \n",counter);
}

void ListPush(node **head,int k)
{
    node *x = (node *)malloc(sizeof(node));
    x->key = k;
    x->next = (*head);
    (*head) = x;
}

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

node *ListSearch(node *head,int k)
{
    node *x = head;
    while(x != NULL && x->key != k)
        x = x->next;
    return x;
}

void ListInsertNode(node **head,int k)
{
    node *x,*y,*z;
    x = (node *)malloc(sizeof(node));
    x->key = k;
    y = (*head);
    z = NULL;
    while(y != NULL && x->key > y->key)
    {
        z = y;
        y = y->next;
    }
    x->next = y;
    if(z != NULL)
        z->next = x;
    else
        (*head) = x;
}

void ListDeleteNode(node **head,int k)
{
    node *x = (*head);
    node *y = NULL;
    while(x != NULL && x->key != k)
    {
        y = x;
        x = x->next;
    }
    if((*head) != NULL && x != NULL)
    {
        if((*head) == x)
            (*head) = x->next;
        else
            y->next = x->next;
        free(x);
    }
}

void ListInsertNodeBefore(node **head,int k1,int k2)
{
    node *x = (node *)malloc(sizeof(node));
    node *y = (*head);
    node *z = NULL;
    x->key = k2;
    while(y != NULL && y->key != k1)
    {
        z = y;
        y = y->next;
    }
    x->next = y;
    if(z != NULL)
        z->next = x;
    else
        (*head) = x;
}

void ListInsertNodeAfter(node **head,int k1,int k2)
{
    node *x = (node *)malloc(sizeof(node));
    node *y = (*head);
    x->key = k2;
    while(y != NULL && y->key != k1)
        y = y->next;
    if(y != NULL)
    {
        x->next = y->next;
        y->next = x;
    }
}

void ListReverse(node **head)
{
    node *p = NULL;
    node *q = (*head);
    node *r;
    while(q != NULL)
    {
        r = q->next;
        q->next = p;
        p = q;
        q = r;
    }
    (*head) = p;
}

node *getTail(node *head)
{
    node *tail = head;
    while(tail != NULL && tail->next != NULL)
        tail = tail->next;
    return tail;
}

void tailins(node *rec,node **head,node **tail)
{
       if((*head) == NULL)
            (*head) = rec;
        else
            (*tail)->next = rec;
        (*tail) = rec;
}


node *quickSort(node *r,node **last)
{
    node *result;
    node *lowf,*lowl,*midf,*midl,*highf,*highl;

    if(r == NULL)
    {
        (*last) = NULL;
        result = r;
    }
    else
    {
        lowf = NULL;
        midf = NULL;
        highf = NULL;
        tailins(r,&midf,&midl);
        r = r->next;
        while(r != NULL)
        {
            if(r->key < midf->key)
                tailins(r,&lowf,&lowl);
            else if(r->key == midf->key)
                tailins(r,&midf,&midl);
            else
                tailins(r,&highf,&highl);
            r = r->next;
        }
        if(lowf != NULL)
        {
            lowl->next = NULL;
            result = quickSort(lowf,last);
            (*last)->next = midf;
        }
        else
            result = midf;
        if(highf != NULL)
            highl->next = NULL;
        midl->next = quickSort(highf,last);
        if((*last) == NULL)
            (*last) = midl;
    }
    return result;
}

int main()
{
    node *head, *tail,*found;
    int ch;
    int k,k1,k2;
    ListInit(&head);
    do
    {
        printf("0. Wyjdz \n");
        printf("1. Wstaw element na poczatek listy \n");
        printf("2. Usun element z poczatku listy \n");
        printf("3. Wyszukaj element na liscie \n");
        printf("4. Wstaw element w sposob uporzadkowany \n");
        printf("5. Wstaw element przed wybranym elementem \n");
        printf("6. Wstaw element za wybranym elementem \n");
        printf("7. Usun wybrany element z listy \n");
        printf("8. Posortuj liste przez podzial \n");
        printf("9. Odwroc kolejnosc elementow listy \n");
        printf("10. Wyswietl elementy listy \n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 0:
            {
                while(!ListIsEmpty(head))
                    ListPop(&head);
                break;
            }
        case 1:
            {
                printf("Podaj element jaki chcesz wstawic \n");
                scanf("%d",&k);
                ListPush(&head,k);
                break;
            }
        case 2:
            {
                ListPop(&head);
                break;
            }
        case 3:
            {
                printf("Podaj element jaki chcesz wyszukac \n");
                scanf("%d",k);
                found = ListSearch(head,k);
                if(found == NULL)
                    printf("Wezla nie znaleziono na liscie \n");
                else
                    printf("Wezel znaleziono na liscie \n");
                break;
            }
        case 4:
            {
                printf("Podaj element jaki chcesz wstawic \n");
                scanf("%d",&k);
                ListInsertNode(&head,k);
                break;
            }
        case 5:
            {
                printf("Podaj element przed jakim chcesz wstawic element \n");
                scanf("%d",&k1);
                printf("Podaj element jaki chcesz wstawic \n");
                scanf("%d",&k2);
                ListInsertNodeBefore(&head,k1,k2);
                break;
            }
        case 6:
            {
                printf("Podaj element za jakim chcesz wstawic element \n");
                scanf("%d",&k1);
                printf("Podaj element jaki chcesz wstawic \n");
                scanf("%d",&k2);
                ListInsertNodeAfter(&head,k1,k2);
                break;
            }
        case 7:
            {
                printf("Podaj element jaki chcesz usunac \n");
                scanf("%d",&k);
                ListDeleteNode(&head,k);
                break;
            }
        case 8:
            {
                tail = getTail(head);
                head = quickSort(head,&tail);
                break;
            }
        case 9:
            {
                ListReverse(&head);
                break;
            }
        case 10:
            {
                ListPrint(head);
                break;
            }
        default:
                printf("Brak operacji , podaj inny numer \n");
        }

    }
    while(ch != 0);
    return 0;
}
 

Can this code be simplified f.e. by elimination extra variables
Is there memory leaks or other surprises

I would like to have void *
as data type

How can i rewrite this code to get it


If everything whith this linked list will be OK
i will try to write C++ class with these functions

[Jaybob66]

malloc() returns a void*

void ListInsertNodeBefore(node **head,int k1,int k2)
{
   void *newMem = malloc(sizeof(node));
    node *x = (node *)newMem;

Its only tiny usage, but its there :)

[Thomas1965]

If everything whith this linked list will be OK i will try to write C++ class with these functions

Are you aware that C++ has a std::list and std::forward_list already?

BTW your code has 2 errors + 4 warning VS 2017 CE /W4

Warning	C4477	'scanf' : format string '%d' requires an argument of type 'int *',
but variadic argument 1 has type 'int' main.cpp 255	
Warning	C4701	potentially uninitialized local variable 'lowl' used main.cpp 197
Error	C4703	potentially uninitialized local pointer variable 'lowl' used main.cpp 197	
Warning	C4701	potentially uninitialized local variable 'highl' used main.cpp 204	
Error	C4703	potentially uninitialized local pointer variable 'highl' used main.cpp 204	
Warning	C4701	potentially uninitialized local variable 'k' used main.cpp 255	

[nowy20180820]

"Are you aware that C++ has a std::list and std::forward_list already?"

Yes but i would like write it just for exercise

Strange I have gcc downloaded with code::blocks ver 17.12
and quite old borland compiler and dont have these errors
gcc on ideone.com also compiled it after i had deleted line with conio. h
Yes there was & missing in line 255 and input may be other then expected
Have you any suggestions to to fix it

If we prefer merge sort than partition sort we can write it with tailins
as auxiliary function

node *merge(node *A,node *B)
{
      node *headS = NULL;
      node *tailS =NULL;
      while(A != NULL && B != NULL)
      {
           if(A->key <= B->key)  
           {
                  tailins(A,&headS,&tailS);
                  A = A->next;         
           }
           else
           {
                 tailins(B,&headS,&tailS);
                 B = B->next;
           }
      }
      while(A != NULL)
      {
            tailins(A,&headS,&tailS);
            A = A->next;
      }
      while(B != NULL)
      {
             tailins(N,&headS,&tailS);
             B = B->next
      }
      return headS       
}

void mergeSort(node **head)
{
    node *h1 = NULL;
    node *h2 = NULL;
    if((*head) != NULL && (*head)->next != NULL)
    {
          split((*head),&h1,&h2);
          mergeSort(&h1);
          mergeSort(&h2);
          (*head) = merge(h1,h2);
    }
}

void split(node *head,node **front,node **back)
{
/* 
   1.
         We search for the middle node which will be tail of the first sublist
         Here we have two options 
             a) left sublist can be one node shorter for odd length lists
             b) left sublist can be one node longer for odd length lists
    2.
    We  set heads for our lists which we will get after splitting
    3.
    We break the left sublist    
*/
}

How can i change the code to have void * as data type ?

[jonnin]

you should not do that.
malloc returns a void * and you immediately cast it to the type you want (in c++, which probably should avoid use of malloc anyway) to cover c++'s strong typing requirements.

node* is what you want, apart from that one place where you get memory and immediately cast it back.

if you want flexibility, make node a template type that can accept a variety of types as the data that your container will store.

you might also want to move from malloc to new.

[nowy20180820]

I asked how to write functions for the structure like this

struct node
{
    void  *data;
    struct node *next;
};

Now i have structure with int data type

struct node
{
    int  data;
    struct node *next;
};

How much differs functions to operate on these structures

[Thomas1965]

In C you should not cast the return type from malloc.
https://bytes.com/topic/c/answers/215856-why-casting-malloc-bad-thing

So this should work.
node *x = malloc(sizeof(node));

struct node
{
    void  *data;
    struct node *next;
};

You could assign anything to data like to an int. The problem would be the lifetime of data which makes it dangerous.
Another option would be to add a member size to the node, allocate the memory and use them memcpy.

struct node
{
    void  *data;
    size_t data_size;
    struct node *next;
};

A way to check for memory leaks is to use functions to create and delete the nodes, where these function manage a global var node_count. At the end of the program node_count should be zero.

Manually managing memory is necessary in C, but in C++ you have much better options like the containers and smart pointers.