链表Push函数实现问题：malloc高效使用与硬故障排查

问题描述 #

我正在实现一个链表，试图高效使用malloc。已定义Node节点结构（包含data和next指针）与lllifo_s容器结构（存储length、capacity、head和tail指针）。lllifo_create函数会创建预分配capacity个节点的空链表，push函数需要先填充已有节点，当length等于capacity时再新增节点扩容。但调用push入队数据时出现硬故障，调试发现数据未更新，还观察到中断产生。

代码片段 #

struct Node
{
    uint8_t data;
    struct Node *next;
};

//LinkedList Container Structure
struct lllifo_s
{
    int length;
    int capacity;
    struct Node *head;
    struct Node *tail;
};

typedef struct lllifo_s lllifo_t;

lllifo_t *lllifo_create(int size)
{
    struct lllifo_s *list = (struct lllifo_s*)malloc(sizeof(struct lllifo_s));

        if (list == NULL) {
                // Handle allocation failure
                return NULL;
            }

            struct Node* first = NULL;

            //initialization
            list->length = 0;
            list->capacity = size;
            list->head = NULL;
            list->tail = NULL;

            for (int i = 0; i < size; i++)
            {
                struct Node *newnode = (struct Node*)malloc(sizeof(struct Node));

                newnode->data = 1;
                newnode->next = NULL;

                if (i == 0)
                {
                    list->head = newnode;
                    list->tail = newnode;
                    first = newnode;
                }
                else
                {
                    first->next = newnode;
                    first = newnode;
                }
            }
            first->next = NULL;
        return list;
}

int lllifo_push(struct lllifo_s *lifo, uint8_t element) {
    if (lifo->length < lifo->capacity) {

         if (lifo->length == 0)
         {
              lifo->head->data = element; // 缺少分号，语法错误
         }

        else
         {
        lifo->tail->data = (uint8_t)element; // 触发硬故障的位置
        lifo->tail = lifo->tail->next;
          }
        
        lifo->length++;
    } else {
        lifo->tail->data = element;
        lifo->tail->next = (struct Node*)malloc(sizeof(struct Node));
        lifo->tail = lifo->tail->next;
        lifo->tail->data = 0;
        lifo->tail->next = NULL;
        lifo->capacity++;
        lifo->length++;
    }
    return lifo->length;
}

问题根源分析 #

1. tail指针初始化错误 #

在lllifo_create函数中，仅在创建第一个节点时设置了list->tail = newnode，后续循环创建其他节点时，tail指针未更新，始终指向第一个节点，而非预分配链表的最后一个节点。这直接导致push时的节点填充逻辑完全偏离预期。

2. push函数填充逻辑错误 #

• 当length=0时，赋值head->data后未移动任何指针，导致后续push操作重复覆盖第一个节点的data，数据无法正确更新。
• 当length>0时，使用tail指针移动来填充节点，但初始tail指向第一个节点，填充几次后tail会指向链表末尾的NULL，此时再访问lifo->tail->data就会触发空指针访问，引发硬故障。

3. 扩容分支逻辑错误 #

当length == capacity时，此时tail已经指向NULL（因为之前的错误移动），访问lifo->tail->data会直接触发空指针异常，导致硬故障。此外，扩容时的逻辑错误：应该将新元素存入新创建的节点，而非覆盖最后一个预分配节点的data。

4. 缺少必要的错误检查 #

• lllifo_create中未检查newnode的malloc结果，若中间节点分配失败会导致内存泄漏。
• lllifo_push中未检查lifo是否为NULL，存在空指针访问风险。
• length=0分支的代码缺少分号，属于语法错误，可能导致未定义行为。

修复方案 #

1. 修正容器结构（新增current指针跟踪待填充节点） #

为了高效填充预分配节点，在容器结构中新增current指针，指向当前待填充的节点：

struct lllifo_s
{
    int length;
    int capacity;
    struct Node *head;
    struct Node *tail;
    struct Node *current; // 指向当前待填充的预分配节点
};

2. 修正lllifo_create函数 #

lllifo_t *lllifo_create(int size)
{
    struct lllifo_s *list = (struct lllifo_s*)malloc(sizeof(struct lllifo_s));
    if (list == NULL) {
        return NULL;
    }

    list->length = 0;
    list->capacity = size;
    list->head = NULL;
    list->tail = NULL;
    list->current = NULL;

    if (size <= 0) {
        return list;
    }

    struct Node* prev = NULL;
    for (int i = 0; i < size; i++)
    {
        struct Node *newnode = (struct Node*)malloc(sizeof(struct Node));
        if (newnode == NULL) {
            // 内存分配失败，释放已分配的节点和容器
            struct Node* temp = list->head;
            while (temp != NULL) {
                struct Node* next = temp->next;
                free(temp);
                temp = next;
            }
            free(list);
            return NULL;
        }

        newnode->data = 0;
        newnode->next = NULL;

        if (i == 0) {
            list->head = newnode;
            list->current = newnode;
            prev = newnode;
        } else {
            prev->next = newnode;
            prev = newnode;
        }
    }
    list->tail = prev; // tail指向预分配链表的最后一个节点
    return list;
}

3. 修正lllifo_push函数 #

int lllifo_push(struct lllifo_s *lifo, uint8_t element) {
    if (lifo == NULL) {
        return -1;
    }

    if (lifo->length < lifo->capacity) {
        // 填充预分配节点
        lifo->current->data = element;
        // 未到最后一个预分配节点时，current移动到下一个
        if (lifo->length != lifo->capacity - 1) {
            lifo->current = lifo->current->next;
        }
        lifo->length++;
    } else {
        // 扩容：新增节点并添加到链表末尾
        struct Node *newnode = (struct Node*)malloc(sizeof(struct Node));
        if (newnode == NULL) {
            return lifo->length;
        }
        newnode->data = element;
        newnode->next = NULL;
        lifo->tail->next = newnode;
        lifo->tail = newnode;
        lifo->capacity++;
        lifo->length++;
    }
    return lifo->length;
}

修复说明 #

• 新增current指针专门跟踪待填充的预分配节点，避免干扰tail指针（tail始终指向链表最后一个节点，方便扩容）。
• 修正lllifo_create中tail的初始化，确保其指向预分配链表的最后一个节点。
• 扩容时直接将新元素存入新创建的节点，逻辑更合理。
• 添加了内存分配失败的处理和空指针检查，避免内存泄漏和未定义行为。

内容的提问来源于stack exchange，提问作者madhvi burange