如何改进单链表插入函数 - C++

Question

我正在使用带有递归插入功能的单链表制作字典，目前它正在做这件事。我有两个来自社区的请求：

我想知道是否有人可以检查我的代码并告诉我是否存在任何内存泄漏，如果有我应该如何删除它们。
看其他列表我发现它们都使用尾节点。为什么这是必要的？

void dictionary::insert(Key k, Item i)
{
    if (head == nullptr)
    {
        head = new Node(k, i);
    }
    else insertRec(k, i, head);
}
void dictionary::insertRec(Key k, Item i, Node* current)
{
    Node* temp;

    if (current->key == k)
    {
        current->item = i;
    }

    else if(current->nextNode != nullptr)
    {
        insertRec(k, i, current->nextNode);
    }
    else if (current->nextNode == nullptr) {

        temp = new Node(k, i);
        current->nextNode = temp;
    }
}

Answer 1

我没有看到您在此处发布的代码中有任何内存泄漏。其他地方可能有一些（通常在您的析构函数或复制构造函数/赋值运算符中）。而且我不明白你为什么要将字典实现为链表。这似乎相当低效。
不需要指向列表中最后一个节点的指针。在这种情况下，它不会给您带来任何好处，因为您无论如何都要遍历整个列表（以找到匹配的键）。如果你不这样做，但你仍然想有效地插入到列表的末尾，那么尾指针就有意义了。

不过，你的代码可以简化很多：

void dictionary::insert(Key k, Item i)
{
    for (Node **pp = &head; *pp; pp = &(*pp)->nextNode) {
        if ((*pp)->key == k) {
            (*pp)->item = i;
            return;
        }
    }
    *pp = new Node(k, i);
}

这是一个简单的循环，不需要递归，也不需要对空指针进行两次单独的测试。

或者，如果您必须使用递归：

void dictionary::insert(Key k, Item i)
{
    insertRec(head, k, i);
}

void dictionary::insertRec(Node *&current, k, i)
{
    if (!current) {
        current = new Node(k, i);
    } else if (current->key == k) {
        current->item = i;
    } else {
        insertRec(current->nextNode, k, i);
    }
}

如何改进单链表插入函数 - C++

How to improve a singly linked list insert function - C++

c++

dictionary

singly-linked-list