Deleting head node of a linked list in C where every node knows its headlist-CodePudding

typedef struct node {
    int x;
    struct node *next;
    struct node **head;
} node;

Considering this struct, I've implemented a push function:

node *push(node *nodo, node *top) {
    nodo->next = top;
    top = nodo;
    nodo->head = &top;
    return top;
}

so that every node is aware of who is the current head list. But I have some problems when I have to delete the head of the list:

node *delete(node *top, int x) {
    if (top->x == x)
        return pop(top);
    else
        return *other function*;
}

node *pop(node *top) {
    node *tmp = top;
    top = tmp->next;
    free(tmp);
    return top;
}

When printing head content, this will give me segmentation fault:

void print(node *top) {
    node *tmp = top;
    printf("List:\n");
    while (tmp != NULL) {
        printf("%d\n", (*((tmp)->head))->x);
        tmp = tmp->next;
    }
    printf("\nEnd\n");
}

CodePudding user response：

But I have some problems when I have to delete the head of the list

You have much worse and more pervasive problems.

Here ...

node* push(node* nodo, node* top){
  nodo->next=top;
  top = nodo;
  nodo->head = &top;
  return top;
}

You set nodo->head to point to a parameter of the function. The lifetime of that parameter ends when the function returns, at which time the node's head pointer becomes invalid. Undefined behavior results from any subsequent attempt to use the node's head pointer in any way.

I suppose that you have defined node.head as a double pointer so as to be able to change the head node in one place for all nodes. In that case, you need to choose a "one place" that is in fact the same for every node and whose lifetime does not end before that of the overall list does. Having chosen such a location, you would pass it itself to push:

node* push(node* nodo, node** top){
  nodo->next=*top;
  *top = nodo;
  nodo->head = nodo;
  return *top;
}

Of course, all callers would need to be updated appropriately.

However, if you want to have this kind of association between nodes and the list to which they belong, then you should consider creating a separate data structure for the list itself, and giving the nodes a poiunter to that. That would solve several problems for you.

Example:

typedef struct node{
  int x;
  struct node* next;
  struct list* list;
}node;

struct list {
    node *head;
    // maybe other whole-list information, too, such as the tail node
    // or an element count
};

The struct list objects then provide the place for head node pointers to be recorded, and nodes can access their lists' head node via the list.