C语言双向链表实现遇double free错误，求修复方案

我是C语言初学者，尝试实现包含pop、insert、remove等功能的双向链表，测试从链表两端弹出元素时出现错误：

"Approaching: Testing popping elements from the list, both ends Test Failed: free(): double free detected in tcache 2"

用valgrind检测到内存泄漏，但不清楚如何修复，以下是我的代码实现：

#ifndef MYDLL_H
#define MYDLL_H

#include <stdlib.h>


typedef struct node
{
    int data;
    struct node *next;
    struct node *previous;
} node_t;

typedef struct DLL
{
    int count;    
    node_t *head; 
    node_t *tail; 
} dll_t;

// Creates a DLL
dll_t *create_dll()
{
    dll_t* myDLL = (dll_t*)malloc(sizeof(dll_t));
    if (myDLL == NULL) {
        return NULL;
    }
    //initial pointer point to self
    // myDLL->next=myDLL->previous=myDLL;
    // return myDLL;

    // set fileds to default values
    myDLL->count = 0;
    myDLL->head = NULL; 
    myDLL->tail = NULL; 

    return myDLL;
}

// DLL Empty
// Check if the DLL is empty
// Returns -1 if the dll is NULL.
// Returns 1 if true (The DLL is completely empty)
// Returns 0 if false (the DLL has at least one element enqueued)
int dll_empty(dll_t *l)
{
    if (l == NULL) {
        return -1;
    }
    if (l->count == 0) {
        return 1;
    }
    return 0;
}

// push a new item to the front of the DLL ( before the first node in the list).
// Returns -1 if DLL is NULL.
// Returns 1 on success
// Returns 0 on failure 
int dll_push_front(dll_t *l, int item)
{
    if (l == NULL) {
        return -1;
    }

    node_t* newNode = (node_t*)malloc(sizeof(node_t)); 
    if (newNode == NULL) {
        return 0;
    }
    
    newNode->data = item; 
    newNode->previous = NULL; 
    if (l->head == NULL) {
        l->head = newNode;
        l->tail = newNode; 
        newNode->next = NULL;
    }
    else {
        newNode->next = l->head; 
        l->head = newNode; 
        l->head->previous = newNode;
    
    l->count++;
    return 1;
}

// push a new item to the end of the DLL (after the last node in the list).
// Returns -1 if DLL is NULL.
// Returns 1 on success
// Returns 0 on failure ( i.e. we couldn't allocate memory for the new node)
// (i.e. the memory allocation for a new node failed).
int dll_push_back(dll_t *l, int item)
{
    if (l == NULL) {
        return -1;
    }
    node_t* newNode = (node_t*)malloc(sizeof(node_t));
    if (newNode == NULL) {
        return 0;
    }

    newNode->data = item; 
    newNode->next = newNode->previous = NULL; 
    if (l->tail == NULL) {
        l->head = newNode;
        l->tail = newNode; 
        newNode->previous = NULL;
    }
    else {
        newNode->previous = l->tail; 
        l->tail->next = newNode; 
        l->tail = newNode; 
    }
    l->count++;
    return 1;
}

// Returns the first item in the DLL and also removes it from the list.
// Returns -1 if the DLL is NULL.
// Returns 0 on failure, i.e. there is noting to pop from the list.
// Assume no negative numbers in the list or the number zero.
int dll_pop_front(dll_t *t)
{
    if (t == NULL) {
        return -1;
    }
    else if (t->count == 0) {
        return 0;
    }
    else {
        node_t* temp = (node_t*)malloc(sizeof(node_t));
        temp = t->head; 
        int data = temp->data; 
        t->head = t->head->next;
        free(temp); 
        t->count--;

        if (t->count == 0) { 
            t->tail = NULL; 
        }

        return data;
    }

}

// Returns the last item in the DLL, and also removes it from the list.
// Returns a -1 if the DLL is NULL.
// Returns 0 on failure, i.e. there is noting to pop from the list.
// Assume no negative numbers in the list or the number zero.
int dll_pop_back(dll_t *t)
{
    if (t == NULL) {
        return -1;
    }
    else if (t->count == 0) {
        return 0;
    }
    else {
        node_t* temp = (node_t*)malloc(sizeof(node_t));
        temp = t->tail; 
        int data = temp->data;
        t->tail = t->tail->previous; 
        free(temp);
        t->count--;

        if (t->count == 0) { 
            t->head = NULL; 
        }

        return data;
    }

}

// Inserts a new node before the node at the specified position.
// Returns -1 if the list is NULL
// Returns 1 on success
// Retruns 0 on failure:
//  * we couldn't allocate memory for the new node
//  * we tried to insert at a negative location.
//  * we tried to insert past the size of the list
//   (inserting at the size should be equivalent as calling push_back).
int dll_insert(dll_t *l, int pos, int item)
{
    if (l == NULL) {
        return -1;
    }

    if (pos == l->count) {
        return dll_push_back(l, item);
    }

    if (pos == 0) {
        return dll_push_front(l, item);
    }

    if (pos < 0 || pos > l->count) {
        return 0;
    }

    node_t* temp = (node_t*)malloc(sizeof(node_t));
    if(temp == NULL) {
        return 0;
    }

    temp->data = item;
    node_t* curr = l->head;
    for (int i = 0; i < pos - 1; i++) {
        curr = curr->next;
    }
    
    temp->previous = curr;
    temp->next = curr->next;
    temp->next->previous = temp;
    curr->next = temp;
    l->count++;

    return 1;
}

// Returns the item at position pos starting at 0 ( 0 being the first item )
// Returns -1 if the list is NULL
//  (does not remove the item)
// Returns 0 on failure:
//  * we tried to get at a negative location.
//  * we tried to get past the size of the list
// Assume no negative numbers in the list or the number zero.
int dll_get(dll_t *l, int pos)
{
    if (l == NULL) {
        return -1;
    }
    if (pos < 0 || pos > l->count) {
        return 0;
    }

    node_t* curr = l->head;
    for (int i = 0; i < pos; i++) {
        curr = curr->next;
    }
    return curr->data;
}

// Removes the item at position pos starting at 0 ( 0 being the first item )
// Returns -1 if the list is NULL
// Returns 0 on failure:
//  * we tried to remove at a negative location.
//  * we tried to remove get past the size of the list
// Assume no negative numbers in the list or the number zero.
// Otherwise returns the value of the node removed.
int dll_remove(dll_t *l, int pos)
{
    if (l == NULL) {
        return -1;
    }

    if (pos == l->count) {
        return dll_pop_back(l);
    }

    if (pos == 0) {
        return dll_pop_front(l);
    }

    if (pos < 0 || pos >= l->count) {
        return 0;
    }

    node_t* curr = l->head;
    for (int i = 0; i < pos; i++) {
        curr = curr->next;
    }

    node_t* temp = curr->next;
    curr->next = curr->next->next;
    int data = temp->data;
    free(temp);
    l->count--;
    return data;
}

// DLL Size
// Returns -1 if the DLL is NULL.
// Queries the current size of a DLL
int dll_size(dll_t *t)
{
    if (t == NULL) {
        return -1;
    }
    return t->count;
}

// Free DLL
void free_dll(dll_t *t)
{
    if (t == NULL) {
        return;
    }
    node_t* curr = t->head;
    node_t* next;
   
    while (curr != NULL) {
        next = curr->next;
        free(curr);
        curr = next;

    }
    free(t);
}

#endif

问题分析与修复方案 #

1. dll_push_front 函数逻辑错误

• 问题点：else分支花括号不匹配，导致l->count++仅在链表非空时执行；同时错误地将新头节点的previous指向自身，未修改原头节点的previous指针。
• 修复后代码：

int dll_push_front(dll_t *l, int item)
{
    if (l == NULL) {
        return -1;
    }

    node_t* newNode = (node_t*)malloc(sizeof(node_t)); 
    if (newNode == NULL) {
        return 0;
    }
    
    newNode->data = item; 
    newNode->previous = NULL; 
    if (l->head == NULL) {
        l->head = newNode;
        l->tail = newNode; 
        newNode->next = NULL;
    }
    else {
        newNode->next = l->head; 
        l->head->previous = newNode;
        l->head = newNode; 
    }
    l->count++;
    return 1;
}

2. dll_pop_front 和 dll_pop_back 的内存泄漏与指针错误

• 问题点：不必要地malloc临时节点，造成内存泄漏；弹出节点后未处理剩余节点的指针，导致野指针，引发双重释放。
• 修复后代码：

int dll_pop_front(dll_t *t)
{
    if (t == NULL) {
        return -1;
    }
    else if (t->count == 0) {
        return 0;
    }
    else {
        node_t* temp = t->head; 
        int data = temp->data; 
        t->head = t->head->next;
        if (t->head != NULL) {
            t->head->previous = NULL;
        }
        free(temp); 
        t->count--;

        if (t->count == 0) { 
            t->tail = NULL; 
        }

        return data;
    }
}

int dll_pop_back(dll_t *t)
{
    if (t == NULL) {
        return -1;
    }
    else if (t->count == 0) {
        return 0;
    }
    else {
        node_t* temp = t->tail; 
        int data = temp->data;
        t->tail = t->tail->previous; 
        if (t->tail != NULL) {
            t->tail->next = NULL;
        }
        free(temp);
        t->count--;

        if (t->count == 0) { 
            t->head = NULL; 
        }

        return data;
    }
}

3. dll_remove 函数双向链接断裂问题

• 问题点：删除中间节点时，未更新被删除节点下一个节点的previous指针，导致链表双向链接断裂。
• 修复后代码：

int dll_remove(dll_t *l, int pos)
{
    if (l == NULL) {
        return -1;
    }

    if (pos == l->count - 1) {
        return dll_pop_back(l);
    }

    if (pos == 0) {
        return dll_pop_front(l);
    }

    if (pos < 0 || pos >= l->count) {
        return 0;
    }

    node_t* curr = l->head;
    for (int i = 0; i < pos; i++) {
        curr = curr->next;
    }

    node_t* temp = curr->next;
    curr->next = temp->next;
    if (temp->next != NULL) {
        temp->next->previous = curr;
    }
    int data = temp->data;
    free(temp);
    l->count--;
    return data;
}

4. dll_get 函数边界判断错误

• 问题点：有效索引范围是0到count-1，原判断pos > l->count会允许越界访问。
• 修复后代码：

int dll_get(dll_t *l, int pos)
{
    if (l == NULL) {
        return -1;
    }
    if (pos < 0 || pos >= l->count) {
        return 0;
    }

    node_t* curr = l->head;
    for (int i = 0; i < pos; i++) {
        curr = curr->next;
    }
    return curr->data;
}

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