Keeping track of initial value of linked list

Question

Iterating through a linked list seems to be tricky for me sometimes (as I am learning).

I keep doing stuff recursively, but I want to do this one iteratively.

The next function adds the values from a list l to a list mx, if its value is greater than x:

typedef struct slist *Lint;

typedef struct slist {
    int value;
    Lint next;
} Nodo;

void split(Lint l, int x, Lint *mx){
    Lint mxtmp=NULL;

    while (l!=NULL){
        if(l->value > x){
            *mx = (Lint) calloc(1,sizeof(Nodo));
            (*mx)->value = l->value;
            (*mx)->next = NULL;
            mxtmp = *mx;
            *mx = (*mx)->next;
        }

        l = l->next;
    }

    *mx = mxtmp;

}

Printing *mx instead of a list gives me a single value (using a proper cycle to go through a list).

The thing is, it seems that I lose track of the start of a list; in this case, I can't seem to keep track of the pointer to the start of the list *mx , which is the list I am changing.

What should I do?

Another doubt I have about this function is, how could I not attribute the values to a new list, but instead make the new mx list, just point to the structs at the main list l?

Answer 1

typedef struct slist *Lint;

typedef struct slist {
    int value;
    Lint next;
    } Nodo;

void split(Lint l, int x, Lint *mx){
     Lint mxtmp=NULL;
     int i = 0;
     while (l!=NULL){
         if(l->value > x){
             *mx = (Lint) calloc(1,sizeof(Nodo));
             (*mx)->value = l->value;
             (*mx)->next = NULL;
             if(!i) //mxtmp will keep track of the first allocated Nodo item
             {
               mxtmp = *mx;
               i++;
             }
             mx = &((*mx)->next); // with this, next( so *mx) will be initialized to point to a new Nodo item in the next loop
         }

         l = l->next;
     }

     mx = &mxtmp; //finally we make mx point to the first allocated Nodo item
}

I did the following code to test it:

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

typedef struct slist *Lint;

typedef struct slist {
    int value;
    Lint next;
    } Nodo;

void recurs_free(Lint f)
{
   if(!f)return;
   if(f->next)recurs_free(f->next);
   free(f);
}

void recurs_printf(Lint f)
{
   if(!f)return;
   printf("%d\n", f->value);
   if(f->next)recurs_printf(f->next);
}

void split(Lint l, int x, Lint *mx){
     Lint mxtmp=NULL;
     int i = 0;
     while (l!=NULL){
         if(l->value > x){
             *mx = (Lint) calloc(1,sizeof(Nodo));
             (*mx)->value = l->value;
             (*mx)->next = NULL;
             if(!i) //mxtmp will keep track of the first allocated Nodo item
             {
               mxtmp = *mx;
               i++;
             }
             mx = &((*mx)->next); // with this, next( so *mx) will be initialized to point to a new Nodo item in the next loop
         }

         l = l->next;
     }
     mx = &mxtmp; //finally we make mx point to the first allocated Nodo item
}

int main()
{
    void recurs_printf(Lint f);
    void recurs_free(Lint f);
    void split(Lint l, int x, Lint *mx);
    Lint t = NULL;
    Nodo a = {1, NULL}, b = {2, &a}, c = {3, &b}, d = {4, &c}, e = {5, &d};
    split(&e, 3, &t);
    recurs_printf(t);
    recurs_free(t);
    return 0;
}

Answer 2

Diagnosis

Your problem is in this code:

void split(Lint l, int x, Lint *mx){
    Lint mxtmp=NULL;

    while (l!=NULL){
        if(l->value > x){
            *mx = (Lint) calloc(1,sizeof(Nodo));

Your assignment to *mx means you've lost your original pointer, and can't update your list properly. There are few platforms where using calloc() won't set the pointer to null, but there's no point in using calloc() when your code explicitly sets the content of the structure.

You probably need something more like:

void split(Lint l, int x, Lint *mx)
{
    Lint mxtmp = NULL;

    while (l != NULL)
    {
        if (l->value > x)
        {
            mxtmp = (Lint) malloc(sizeof(*mxtmp));
            if (mxtmp == 0)
                …report error and do not continue…
            mxtmp->value = l->value;
            mxtmp->next = *mx;
            *mx = mxtmp;
        }
        l = l->next;
    }
}

This inserts the items on *mx in the reverse of the order that they appeared in l because it always inserts at the front of the list. You can arrange to append to the end of the *mx if you prefer.

If you need to remove entries from the source list, l, and transfer them to *mx, then you need to pass Lint *l to the function so that the head of the list can be updated if the first item in l (or *l with the revised signature) needs to be transferred to *mx.

Explanation

This does the job very well. Do you mind explaining what happens with the *mx? Because I don't seem to understand how the *mx is "increased"; it seems that the *mx is always in the same pointer value.

I'm relieved it works because I hadn't had a chance to test it before this update.

Let's suppose we're given a call like this:

Lint list1 = 0;
…populate list1…
Lint list2 = 0;
split(list1, 10, &list2);

The pointer list2 has its own address. It holds a value, initially the null pointer. The address of the list2 pointer is passed to split(), which means that split() can modify the pointer contents (just like if you have int i = 0; some_func(&i);, then some_func() can modify the value in i).

As split() traverses the list, l, when it finds a value that needs to be copied, it creates a new node pointed at by mxtmp, and fills in the value. It makes the new node's next pointer point to what is currently at the head of the list (mxtmp->next = *mx;), then it modifies the address that *mx — which is effectively list1 in the calling function in the example call — points at so that it contains the address of the new node (*mx = mxtmp;).

Testing

This is the test code I came up with, which runs cleanly under valgrind:

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

typedef struct slist *Lint;

typedef struct slist
{
    int value;
    Lint next;
} Nodo;

static void error(const char *msg)
{
    fprintf(stderr, "%s\n", msg);
    exit(EXIT_FAILURE);
}

static void split(Lint l, int x, Lint *mx)
{
    // Note minor change compared to original suggested code.
    while (l != NULL)
    {
        if (l->value > x)
        {
            Lint mxtmp = (Lint) malloc(sizeof(*mxtmp));
            if (mxtmp == 0)
                error("Out of memory");
            mxtmp->value = l->value;
            mxtmp->next = *mx;
            *mx = mxtmp;
        }
        l = l->next;
    }
}

static void print_list(const char *tag, Lint list)
{
    printf("%s:", tag);
    while (list != NULL)
    {
        printf(" --> %d", list->value);
        list = list->next;
    }
    putchar('\n');
}

static void insert(Lint *list, int value)
{
    Lint node = malloc(sizeof(*node));
    if (node == 0)
        error("Out of memory");
    node->value = value;
    node->next = *list;
    *list = node;
}

static void destroy(Lint list)
{
    while (list != NULL)
    {
        Lint next = list->next;
        free(list);
        list = next;
    }
}

int main(void)
{
    Lint list1 = NULL;
    insert(&list1, 2);
    insert(&list1, 10);
    insert(&list1, 11);
    insert(&list1, 23);
    print_list("List 1", list1);

    Lint list2 = NULL;
    split(list1, 10, &list2);
    print_list("List 1", list1);
    print_list("List 2", list2);

    destroy(list1);
    destroy(list2);
    return 0;
}

Compilation

The source file was called nodo.c, so the program was called nodo, and I have a makefile configured with lots of compiler warning options enabled. There were no warnings (from GCC 5.1.0 on Mac OS X 10.10.3):

$ gcc -O3 -g -std=c11 -Wall -Wextra -Werror nodo.c -o nodo
$

I regard that as about the bare minimum requirement; I don't usually even run the code until it compiles that quietly.

Example output:

List 1: --> 23 --> 11 --> 10 --> 2
List 1: --> 23 --> 11 --> 10 --> 2
List 2: --> 11 --> 23

Printing list1 twice is paranoia, checking that it was not damaged during the split operation. Note that the split() function should be written to use the insert() function.

A debugging print would also print the addresses of the node and the next pointer:

static void print_list(const char *tag, Lint list)
{
    printf("%s:\n", tag);
    while (list != NULL)
    {
        printf("--> %3d  (%p, next %p)\n", list->value, (void *)list, (void *)list->next);
        list = list->next;
    }
    putchar('\n');
}

Yielding, for example:

List 1:
-->  23  (0x10081f410, next 0x10081f3c0)
-->  11  (0x10081f3c0, next 0x10081f370)
-->  10  (0x10081f370, next 0x10081f320)
-->   2  (0x10081f320, next 0x0)

List 1:
-->  23  (0x10081f410, next 0x10081f3c0)
-->  11  (0x10081f3c0, next 0x10081f370)
-->  10  (0x10081f370, next 0x10081f320)
-->   2  (0x10081f320, next 0x0)

List 2:
-->  11  (0x10081f4b0, next 0x10081f460)
-->  23  (0x10081f460, next 0x0)

Parting comments

I didn't reorganize the data types, but left to my own devices I would probably have used something like:

typedef struct List List;
struct List
{
    int   value;
    List *next;
};

And then passed List * and List ** around. This uses the tag name as the type name, which is something C++ does automatically without the explicit typedef.