C实现链表删除元素功能

I was reading a textbook and came across the following function to remove an element from a linked list. The CELL type is defined as follows;

我正在阅读一本教科书并遇到以下函数从链表中删除一个元素。 CELL类型定义如下;

typedef struct CELL CELL;
struct CELL {
    int element;
    CELL* next;
};

void delete(int x, CELL** pL) {
    if ((*pL) != NULL) {
        if (x == (*pL)->element)
            (*pL) = (*pL)->next;
        else
            delete(x, &((*pL)->next));
    }
}

Now suppose I have a linked list with the following elements starting at 5;

现在假设我有一个链接列表,其中包含从5开始的以下元素;

5->10->3->21->15->7

Now suppose I delete element 10. My question is what happens to the CELL containing 10 when the delete function returns now that this CELL is unreferenced? Isn't it still taking up space in memory?

现在假设我删除了元素10.我的问题是当删除函数返回此CELL未被引用时,包含10的CELL会发生什么?是不是还占用了记忆中的空间?

3 个解决方案

#1

what happens to the CELL containing 10 when the delete function returns now that this CELL is unreferenced? Isn't it still taking up space in memory?

当删除函数返回此CELL未被引用时,包含10的CELL会发生什么?是不是还占用了记忆中的空间?

Absolutely! Once the function returns, the CELL containing 10 becomes a memory leak, unless there is another pointer referencing it, or the CELL is not allocated dynamically.

绝对!一旦函数返回,包含10的CELL就会变成内存泄漏,除非有另一个指针引用它,或者CELL没有动态分配。

If other functions for manipulating the list (creating, inserting, etc.) are implemented in such a way that they assume list's ownership of its cells, add a call to free in the branch that re-points *pl to (*pL)->next. Make a temporary variable, store the address of *pl in it, do the re-pointing, and call free on the temporary.

如果用于操作列表(创建,插入等)的其他函数以这样的方式实现,即它们假定列表对其单元格的所有权,则在分支中添加一个空闲调用,将* pl重新指向(* pL) - >未来。创建一个临时变量,将* pl的地址存储在其中,重新指向,并在临时变量上*调用。

#2

Since you're not freeing any memory in your code, it should still be there somewhere. You just unlink that element from the linked list.

由于你没有释放代码中的任何内存,它应该仍然存在于某个地方。您只需将该元素与链接列表取消链接即可。

Depending on how you manage the memory for these elements this might or might not be a problem (memory leak). For example, if each element is allocated using malloc and the linked list has the only pointer to that element then you most likely have a memory leak (and using free is required). But if the nodes are allocated on the stack (e.g. using alloca) or in some memory pool which is freed later, then there might not be a leak. So it really comes down to how you handle the memory and when do you deallocate it.

根据您管理这些元素的内存的方式,这可能是也可能不是问题(内存泄漏)。例如,如果使用malloc分配每个元素,并且链接列表只有指向该元素的指针,那么您很可能有内存泄漏(并且需要使用free)。但是如果节点在堆栈上分配(例如使用alloca)或者在稍后释放的某个内存池中,则可能没有泄漏。所以它真正归结为你如何处理内存以及何时解除分配。

#3

For starters some remarks about the function itself. It would be better to declare the function the following way

对于初学者来说,有关函数本身的一些评论。最好以下列方式声明函数

int delete( CELL **pL, int x );

In fact the function does two things. It searches a node with the value equal to x. And it unlinks a node if such is found.

实际上这个功能做了两件事。它搜索值等于x的节点。如果发现这样,它会取消链接节点。

So it is desirable that the function would report whether such a node is found.

因此,希望该函数报告是否找到了这样的节点。

Another way to declare the function in case when the function does not free the removed node pointed to by @IanAbbott in a comment is

如果函数没有释放@IanAbbott在注释中指向的已删除节点,则声明该函数的另一种方法是

CELL * delete( CELL **pL, int x );

That is the function returns pointer to the removed node or NULL if such a node with the value equal to x is not found.

即,如果找不到值等于x的节点,则函数返回指向已删除节点的指针或NULL。

Secondly it is better to declare the first parameter as a reference to node and the second parameter as searched value. That is at first what you are dealing with and then how you are dealing with the list.

其次,最好将第一个参数声明为节点的引用,将第二个参数声明为搜索值。这首先是你正在处理的事情,然后是你如何处理清单。

As for your question then the function as I already said unlinks a node. The node itself is not removed from memory and is not changed. If it was allocated dynamically then you have to keep a copy of the pointer pointing to the node. Otherwise there will be a memory leak because you will be unable to free it without having a pointer to the node.

至于你的问题,那么我已经说过的函数取消了一个节点的链接。节点本身不会从内存中删除,也不会更改。如果它是动态分配的,那么你必须保留指向节点的指针的副本。否则会出现内存泄漏,因为如果没有指向节点的指针,您将无法释放它。

#1