面试题：C++ std::shared_ptr引用计数在复杂数据结构中的应用

Question

假设有一个自定义的链表结构，节点使用std::shared_ptr管理。请编写代码实现链表节点的插入和删除操作，并阐述在这些操作过程中，std::shared_ptr的引用计数是如何正确维护的，以避免内存泄漏。

Answer 1

代码实现

#include <iostream>
#include <memory>

// 定义链表节点结构
struct ListNode {
    int val;
    std::shared_ptr<ListNode> next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 插入节点到链表头部
void insertNode(std::shared_ptr<ListNode>& head, int val) {
    std::shared_ptr<ListNode> newNode = std::make_shared<ListNode>(val);
    newNode->next = head;
    head = newNode;
}

// 删除链表中值为target的节点
void deleteNode(std::shared_ptr<ListNode>& head, int target) {
    if (!head) return;
    if (head->val == target) {
        head = head->next;
        return;
    }
    std::shared_ptr<ListNode> current = head;
    while (current->next && current->next->val != target) {
        current = current->next;
    }
    if (current->next) {
        current->next = current->next->next;
    }
}

std::shared_ptr引用计数维护说明

1. 插入操作：
   • 使用std::make_shared创建新节点newNode，此时newNode的引用计数为1。
   • newNode->next = head，若head不为空，head指向的节点引用计数加1，因为newNode->next也指向了它。
   • head = newNode，head指向新节点，新节点引用计数再增加1（因为head也指向它了）。这样就确保了新节点和其后续节点的内存不会被错误释放，避免了内存泄漏。
2. 删除操作：
   • 当删除头节点时，head = head->next，原头节点的引用计数减1（因为head不再指向它），如果此时原头节点的引用计数变为0，它所占用的内存会被自动释放。
   • 当删除非头节点时，current->next = current->next->next，被删除节点的引用计数减1（因为current->next不再指向它），如果引用计数变为0，该节点内存被自动释放。同时，current->next->next所指向节点的引用计数会加1（因为current->next现在指向它了），确保该节点内存不会因误操作被释放，从而正确维护引用计数，避免内存泄漏。