使用链表的 malloc() 和 free 的正确方法

Question

当谈到链表时，我试图更好地理解 malloc() 。这会为指向列表的指针及其内部的字段创建内存吗？如：

  SomeStruct * someStructPtr = (SomeStruct *) malloc(sizeof(SomeStruct));

除此之外，如果我试图释放该节点及其内部的字段。我是否需要遍历所有字段（请参阅下面的代码）。这只是释放指针（从上面的行创建）还是释放指针和字段。

free(someStructPtr);

举个更直接的例子。我有一个 List 结构，我正在尝试为此结构分配 space 并且它是创建时的字段。我想确保我正确地创建、删除和使用 stdrup()。我的代码如下：

结构声明：

typedef struct ListNode_st
{
    char * str;
    struct ListNode_st * next;
} List;

创建节点：

List * List_createNode(const char * str){
  List * listPointer = (List *) malloc(sizeof(List));

  //make sure there was enough memory
  if(listPointer == NULL)
    return NULL;

  //malloc for next
  listPointer.next = (List *) malloc(sizeof(List *));
  if(listPointer.next == NULL)
    return NULL;
  listPointer.next = NULL;

  //malloc for str
  listPointer.str = strdup(str);
  //make sure enough space for the string to be copied
  if(listPointer.str == NULL)
    return NULL;

  //return value
  return listPointer;
}

删除节点：

void List_destory(List * list){
  //base case -- (last item)
  if(list == NULL)
    return;
  //recurse case -- (there are more items)
  List_destroy(list->next);
  if(list->str != NULL)
    free(list->str);
  if(list->next != NULL)
    free(list->next);

  free(list);
}

Answer 1

List * List_createNode(const char * str){
  List * listPointer = (List *) malloc(sizeof(List));

  if(listPointer == NULL)
    return NULL;

  listPointer->next = NULL;

  listPointer->str = strdup(str);
  if(listPointer->str == NULL){
    free(listPointer);
    return NULL;
  }

  return listPointer;
}

void List_destory(List * list){
  if(list == NULL)
    return;
  List_destroy(list->next);
  free(list->str);
  free(list);
}

Answer 2

在解决您的问题之前让我们先热身一下。

int x = 42;

x的记忆从何而来？分配了吗？在哪里？如果这一行在函数内部，答案是：它是一个 "automatic" 变量，它使用的内存在堆栈上。

int * y = NULL;

现在 y 的内存来自哪里？这里没有调用 malloc()，但是 y 存在。

现在，您应该能够回答问题的第一部分了。在这种情况下，malloc() 没有为您的指针分配内存。

struct Node
{
    struct Node * next;
    int value;
};

void InitNode( Node *node, int value )
{
    if(NULL != node)
    {
        node->next = NULL;
        node->value = value;
    }
}

// Not on HEAP, not on stack! Where? 
// This one gets its memory from "initvars" section.
int foo = 69; 

int main( int argc, const char * argv[] )
{
     struct Node n1; // instance located on stack...
     InitNode(&n1); // no malloc() to be seen... 

     // Instance located on HEAP, but n2, the pointer is located on stack,    
     // just like an int x = 42 would be.
     struct Node *n2 = malloc(sizeof(struct Node)); 
}

所以，显然为了揭开 malloc() 的神秘面纱，需要了解不同类型的内存以及如何处理它。

到目前为止，我们看到了 "automatic" 又名 "stack memory"，我们看到了 "initvars" 内存。我们看到了 "heap" 内存。 malloc() 是用于在堆上分配内存的函数。

最后一点，还有其他类型的内存我这里就不提了。

Answer 3

请不要从 malloc() 转换 return 值。

malloc(sizeof(SomeStruct))

为一个结构分配足够的内存，然后您必须初始化结构中的每个字段。

calloc(1, sizeof(SomeStruct))

做同样的事情，但结构的每个字节都被初始化为 0。 malloc() 和 calloc() 对您的结构一无所知，它们只是分配您要求的内存量。它们 return 一个 void* 指针，因此它们可以用于任何数据类型，它们既不知道也不关心。

当你到达 free() 分配的内存时，同样适用 - free() 对你的结构一无所知，即使它是一个结构.在 free() 结构的内存之前 free() 该结构内的任何内存分配由您决定。它不释放结构。它释放结构所在的内存。

所以答案是肯定的，你确实需要遍历整个数据结构，否则任何嵌套的内存分配指针都会丢失，导致内存泄漏。

Answer 4

Does this create memory for the pointer to the list as well as the fields inside of it?

给定你的结构类型

typedef struct ListNode_st
{
    char * str;
    struct ListNode_st * next;
} List;

以下调用将为该结构的实例创建内存：

List *l = malloc( sizeof *l ); // note no cast, operand of sizeof

l 指向一个足够大的内存块，可以包含两个指针；但是，没有为 str 或 next 分配任何指向到的内容。您必须分别为字符串和下一个节点分配内存：

l->str = malloc( N * sizeof *l->str ); // allocate N characters

或

l->str = strdup( str );

请注意，在大多数链表实现中，创建新节点时不会为 next 分配内存；该字段旨在指向列表中另一个先前分配的节点。当你在当前节点后面插入一个节点时，你将设置它。

Alongside this, if I am trying to free this node AND the fields inside of it. Do I need to walk through all the fields (see code below). Does this just free the pointer (created from the line above) or does it free the pointer and and the fields.

在删除整个节点之前，您需要先释放所有分配的成员，例如

free( l->str );
free( l );

释放 l 不会释放 l->str 指向的内存。

使用链表的 malloc() 和 free 的正确方法

Correct way to use malloc() and free with linked lists

c

pointers

struct

linked-list

free