如何从链表中获取项目的指针

Question

在链表中搜索项目并不复杂 return 它：只需浏览列表的副本和 return 与搜索谓词匹配的项目。但是，我想知道是否有办法在列表中检索我们要查找的元素的指针，这意味着我无法克服的困难：不能有原始列表的副本（否则指针将无效或与原始列表中的项目不匹配）。

我选择链表结构是因为我需要大量的增删改查，数组可以做到，但效率较低。不过，我希望能够修改列表中的某些元素；为此我想象了这样一个功能：

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

我不知道如何在保持原始链表完好无损的情况下做到这一点，我不确定这是个好主意，在这种情况下，我会被简化为一个简单的数组（或另一个更合适的数据结构？）。

Answer 1

函数似乎应该定义为

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; 
}

如何从链表中获取项目的指针

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

c

struct

pointers

linked-list

singly-linked-list