c - How to get the pointer of an item from a linked list

Question

It is not complicated to search for an item in a linked list and return it: just browse a copy of the list and return the item that matches the search predicate. However, I was wondering if there was a way to retrieve the pointer of the element we are looking for in the list, which implies a difficulty I have not been able to overcome: there can be no copy of the original list (otherwise the pointer would be invalid or would not match an item in the original list).

I chose the structure of the linked list because I need a lot of additions and deletions, which an array allows to do, but in a less efficient way. Nevertheless, I would like to be able to modify some elements of my list; to do this I had imagined such a function:

struct Item
{
    char* str;
    int value;
};

typedef struct Node
{
    struct Item item;
    struct Node *next;
} Node;

Node *push(Node *head, const struct Item)
{
    Node *new_node;
    new_node = malloc(sizeof(*new_node));
    new_node->item = item;
    new_node->next = head;
    head = new_node;
    return head;
}

Node *remove(Node *head, char* str)
{
    if (head == NULL)
        return NULL;

    if (!strcmp(head->item.str, str))
    {
        Node *tmp_next = head->next;
        free(head);
        return tmp_next;
    }

    head->next = remove(head->next, str);
    return head;
}

struct Item *get_item_ptr(const Node *head, char* str)
{
    // I would get the pointer of the structure Item that refers to the string `str`.
    ...
    return NULL; // I return `NULL` if no item meets this predicate.
}

I don't know how to do that while keeping the original linked list intact and I'm not sure it's a good idea, in which case I'd be reduced to a simple array (or another more suitable data structure?).

标签： cpointersstructlinked-listsingly-linked-list

Answer 1

It seems the function should be defined something like

struct Item * get_item_ptr( const Node *head, const char *str )
{
    while ( head != NULL && strcmp( head->item.str, str ) != 0 )
    {
        head = head->next;
    }

    return head == NULL ? ( struct Item * )NULL : &head->item; 
}