C++链表节点删除方法,如何合适的释放内存

Aaron_Zhou
  • 9

让我先描述下……

实现这样一个方法,删除不带头单链表中与val值相同的结点
方法签名:

ListNode* removeElements(ListNode* head, int val);

ListNode类声明

class ListNode {
public:
    ListNode(int x) : val(x), next(NULL) {}
    int val;
    ListNode *next;
};

逻辑很简单,当

// ...
pre->next = p->next;
// ...

之后,一般的做法是

delete p;

但这时,有个问题。当主调函数中写如下调用时,会出内存问题

ListNode n0(0), n1(1), n2(2);
n0.next = &n1;
n1.next = &n2;
// ...
removeElements(&n0, 2);

n2结点的内存是不可delete的……

另外,如果在removeElements方法中不写delete逻辑,如果主调函数中,链表结点是new出来的,则不delete会内存泄露

So… 我想问一下,在实现类似的C++函数时,有什么一般的做法,或者业内默认规定?
或者,有没有更nice的处理方式?能让方法比较安全且避免内存泄露

多谢 :-)

回复
阅读 14.1k
5 个回答
✓ 已被采纳

既然有ListNode ,就应该有List类,将removeElements封装到List类中,由List类负责内存的分配和释放;
这样责任就清晰了。

再就是结点的分配一般都是在堆上申请,在栈上连接起来的结点当然无法删除;
如果非得需要按照你这样的实现,在栈上应用list,那么只用更改结点指针就好了,不用delete,栈上的即结点在退出程序逻辑范围时自动删除了;

最不动脑子的方法,用shared_ptr,当然在你这个问题中这样显得有点傻。
所以你应该把所有要删除的节点放到另外一个list里,等到真的不用的时候统一删掉就好。

你这种写法,不只是n2删除有问题,n0也有问题。
考虑在removeElements中对表头和表尾做特殊处理,双链表

可以考虑removeElements接口传入一个回调函数,让用户自己决定是否释放

谁提供的内存, 谁负责释放. 比如如果 Node是在你的类库代码里 分配的内存, 那么你的类库代码负责释放; 如果是用户 传入的内存, 则用户负责.

宣传栏