Bauer Bauer - 28 days ago 16
C Question

Pointers to pointers - linked list mess

I'm writing a simple C program to manage a linked list defined as follow:

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


I reviewed the code and it seems okay but when printing results something is not working well.

My main, with problems on comments:

int main(void) {
List n = list_create(1);
insert(n, 2);
insert(n, 3);
insert(n, 5);
insert(n, 4);
//something here does not work properly. It produces the following output:
//Value: 1
//Value: 2
//Value: 3
//Value: 4
//where is value 5?
print_list(n);
delete(n, 3);
print_list(n);
return 0;
}


I don't know where am I destroying list structure. These are my functions, to debug, if you are too kind.

List list_create(int value) {
List new = malloc(sizeof(struct node));
new->value = value;
new->next = NULL;
return new;
}

List new_node(int value, List next_node) {
List new = malloc(sizeof(struct node));
new->value = value;
new->next = next_node;
return new;
}

void print_list(List l) {
List *aux;
for (aux = &l; (*aux) != NULL; aux = &((*aux)->next))
printf("Valor: %d\n", (*aux)->value);
}

void insert(List l, int value) {
List *p;
for (p = &l; (*p) != NULL; p = &((*p)->next))
if ((*p)->value > value) {
List tmp = *p;
List new = new_node(value, tmp);
*p = new;
break;
}
*p = new_node(value, NULL);
}

void delete(List l, int value) {
List *p;
for (p = &l; (*p) != NULL; p = &((*p)->next))
if ((*p)->value == value) {
List del = (*p);
(*p) = ((*p)->next);
free(del);
break;
}
}

Answer

This code has (at least) two bugs:

  1. The line

    if ((*p)->value > value){

means that if you start the list with 1 as the first value and then try to insert 2,3,4..., the body of the 'if' statement never runs, so nothing ever gets inserted.

  1. If you insert a value below the starting value, you have to modify the list pointer itself. However, as @EOF alluded, you are trying to modify a value passed to a function by taking its address. This won't work. &l does not give you the address of the List you passed, it gives you the address of the local copy on insert()'s stack. You are better off modifying the values of first element of the list 'in place'. If you really want to make the List parameter mutable, you'll need to pass it as a List *, and call the function with the address of the list (e.g. insert(&n,2); ) Your delete() function suffers from the same problem - try deleting the first element of the list.

Try this for your insert function:

void insert(List l, int value)
{
  List p;

  // Find end of list or highest item less than value
  for(p = l; p->next != NULL && p->next->value < value; p = p->next);

  if (p->value >= value) {
    // Over-write p with new value, and insert p as a new one after.
    // This saves having to modify l itself.
    int tmpval = p->value;
    p->value = value;
    p->next = new_node(tmpval, p->next);
  } else {
    // Insert new item after p
    p->next = new_node(value, p->next);
  }
}

A comment: it is possible the way you are using pointers is not helping the debugging process.

For example, your print_list() could be re-written like this:

void print_list(List l){
  List aux;
  for(aux = l; aux != NULL; aux = aux->next)
    printf("Valor: %d\n", aux->value);
}

and still behave the same. It is generally good practice not to 'hide' the pointer-like nature of a pointer by including a '*' in the typedef. For example, if you define your list like this:

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

And pass it to functions like this:

my_func(List *l, ...)

then it'll make some of these issues more apparent. Hope this helps.

Comments