How to work with this singly linked list?

user_12993040 0
Viewed 80

I have a strange linked list (code is not mine):

struct _P_NEXT
{ P_NEXT* p_el; };

As you can see, there is no data field. However, the list must contain complex structures. For illustration, I give a method of adding an item to the end of the list:

void in_tail(P_NEXT* head_list, P_NEXT* el_list) {

    el_list->p_el = NULL;

    P_NEXT* el;
    el = head_list->p_el;

    if (el) {
        while (el->p_el)
            el = el->p_el;

        (el->p_el) = el_list;
    }
    else {
        head_list->p_el = el_list;
    }
}
linked-list struct c c++
1 Answers

This kind of structure is usually used as intrusive list

this is usually useful in C where there is no type polymorphism and but you want to have common function for maintenance and utility.

Usage example:

struct node {
    struct _P_NEXT list; // must be the first member of the structure
    int data; 
    // and so on ....
};

and you can still use in_tail with the defined struct node above, because the way the stucture is layed out in memory, the address of an node would be the same address of its first member (a struct _P_NEXT).

example:

struct node head;
head.list.p_el = NULL;
// init head data
for(int i=0; i < 10; ++i) {
    struct node node = malloc(sizeof(struct node));
    // set node data
    in_tail((struct _P_NEXT*)&head, (struct _P_NEXT*)node);
}

You can have a cleanup list function written the same way:

void cleanup_list(P_NEXT* list) {
    while(list !=NULL) {
        P_NEXT* current = list;
        list = current -> p_el;
        free(current);
    }
}

and invoked the same:

cleanup_list((P_NEXT*)head.list.p_el);
user_1051040
Related