Pointers to pointers - linked list mess

Question

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 1

There are many problems in your code:

• Hiding pointers behind typedefs is a bad idea, it leads to confusion for both the programmer and the reader.

• You must decide whether the initial node is a dummy node or if the empty list is simply a NULL pointer. The latter is much simpler to handle but you must pass the address of the head node to insert and delete so they can change the head node.

• printlist does not need an indirect pointer, especially starting from the address of the pointer passed as an argument. Simplify by using the Node pointer directly.

• in insert you correctly insert the new node before the next higher node but you should then return from the function. Instead, you break out of the switch and the code for appending is executed, replacing the inserted node with a new node with the same value and a NULL next pointer. This is the reason 5 gets removed and lost when you insert 4. Furthermore, you should pass the address of the head node so a node can be inserted before the first.

• delete starts from the address of the argument. It cannot delete the head node because the pointer in the caller space does not get updated. You should pass the address of the head node.

• You should avoid using C++ keywords such as new and delete in C code: while not illegal, it confuses readers used to C++, confuses the syntax highlighter and prevents compilation by C++ compilers.

Here is a simplified and corrected version:

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

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

Node *new_node(int value, Node *next_node) {
    Node *node = malloc(sizeof(*node));
    if (node != NULL) {
        node->value = value;
        node->next = next_node;
    }
    return node;
}

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

void insert_node(Node **p, int value) {
    while ((*p) != NULL && (*p)->value < value)
        p = &(*p)->next;

    *p = new_node(value, *p);
}

void delete_node(Node **p, int value) {
    while (*p != NULL) {
        if ((*p)->value == value) {
            Node *found = *p;
            *p = (*p)->next;
            free(found);
            // return unless delete() is supposed to remove all occurrences
            return;
        } else {
            p = &(*p)->next;
        }
    }
}

int main(void) {
    Node *n = NULL;
    insert_node(&n, 2);
    insert_node(&n, 3);
    insert_node(&n, 5);
    insert_node(&n, 4);
    insert_node(&n, 1);
    print_list(n);
    delete_node(&n, 3);
    print_list(n);
    delete_node(&n, 1);
    print_list(n);
    return 0;
}

Answer 2

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.

2. 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.