数据结构---双向链表（内存泄露相关知识）

一、内存泄露

内存泄露（Memory Leak）是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等严重后果。内存泄漏是程序设计中常见的错误之一，其特点包括隐蔽性和积累性。

一、内存泄露的定义

       内存泄漏并非指内存在物理上的消失，而是指应用程序分配某段内存后，由于设计错误或疏忽，失去了对该段内存的控制，使得该内存无法被再次使用或回收，从而造成了内存的浪费。

二、内存泄露的原因

1. 资源未被正确释放：程序中动态分配的内存（如使用malloc、new等函数分配的内存）在不再使用时，必须显式地释放（如使用free、delete等函数）。如果忘记释放或者释放时机不当，就会导致内存泄漏。

2. 垃圾回收机制失效：在一些使用垃圾回收机制的语言中（如Java、Python等），如果垃圾回收器未能及时回收无用的内存对象，也可能导致内存泄漏。这通常是由于程序中存在对无用对象的引用，使得垃圾回收器无法识别并回收这些对象。

3. 循环引用：在对象间存在循环引用的情况下，即使这些对象已经不再被程序的其他部分使用，它们也可能因为相互引用而无法被垃圾回收器回收，从而导致内存泄漏。

4. 程序设计错误：如错误的算法设计、错误的内存分配策略等，都可能导致内存泄漏。

 三、内存泄露的影响

内存泄漏会导致系统可用内存逐渐减少，进而影响程序的运行速度和稳定性。在极端情况下，内存泄漏甚至可能导致系统崩溃或无法响应。此外，内存泄漏还可能引发安全问题，如敏感信息泄露等。

四、如何避免内存泄漏

为了避免内存泄漏，开发人员可以采取以下措施：

1. 合理设计程序：在程序设计阶段就考虑到内存管理的问题，采用合适的算法和数据结构来减少内存的使用和泄漏。

2. 及时释放内存：在程序中及时释放不再使用的内存资源，避免内存泄漏的发生。

3. 使用内存检测工具：利用专业的内存检测工具来检测和分析程序中的内存泄漏问题，及时修复潜在的内存泄漏点。如使用valgrind工具

4. 编写高质量的代码：通过代码审查、单元测试等方式来提高代码质量，减少因程序设计错误导致的内存泄漏问题。

二、双向链表

双向链表（Doubly Linked List）是一种数据结构，它与单向链表相似，但每个节点不仅包含指向下一个节点的指针，还包含指向上一个节点的指针。

双向链表的每个节点通常包含以下两个指针：

• prev：指向上一个节点
• next：指向下一个节点

通过这两个指针，可以在双向链表中沿着两个方向遍历。

相比于单向链表，双向链表能够更方便地进行插入和删除操作。因为每个节点包含指向前一个节点的指针，所以在删除或插入一个节点时，只需要修改该节点前后节点的指针即可。而在单向链表中，则需要在删除或插入节点时，找到该节点的前一个节点，以便进行指针修改，显得相对麻烦。

//头插
int push_doulink_head(DLink_t *pdoulink, DataType data)
{
    DLink_Node_t *pnode = malloc(sizeof(DLink_Node_t));
    if(NULL == pnode)
    {
        perror("fail malloc");
        return -1;
    }
    pnode->data = data;
    pnode->ppre = NULL;
    pnode->pnext = NULL;
    if(is_empty_doulink(pdoulink))
    {
        pdoulink->phead = pnode;
    }
    else
    {
        pnode->pnext = pdoulink->phead;
        pdoulink->phead->ppre = pnode;
        pdoulink->phead = pnode;
    }
    pdoulink->clen++;
    return 0;
}

//遍历
void push_printlist(DLink_t *pdoulink, int dir)
{
    if(is_empty_doulink(pdoulink))
    {
        return;
    }
    DLink_Node_t *p = pdoulink->phead;
    if(dir)
    {
        while(p != NULL)
        {
            printf("%d ", p->data.id);
            printf("%s ", p->data.name);
            printf("%d \n", p->data.score);
            p = p->pnext;
        }
    }
    else
    {
        while(p->pnext != NULL)
        {
            p = p->pnext;
        }
        while(p != NULL)
        {
            printf("%d ", p->data.id);
            printf("%s ", p->data.name);
            printf("%d \n", p->data.score);
            p = p->ppre;
        }
    }
}

//尾插
int push_doulink_end(DLink_t *pdoulink, DataType data)
{
    if(is_empty_doulink(pdoulink))
    {
        push_doulink_head(pdoulink, data);
    }
    else
    {
    DLink_Node_t *p = pdoulink->phead;
    DLink_Node_t *pnode = malloc(sizeof(DLink_Node_t));
    if(NULL == pnode)
    {
        perror("fail malloc");
        return -1;
    }
    pnode->data = data;
    pnode->ppre = NULL;
    pnode->pnext = NULL;

    while(p->pnext != NULL)
    {
        p = p->pnext;
    }
    p->pnext = pnode;
    pnode->pnext = NULL;
    pnode->ppre = p;
    pdoulink->clen++;
    }
}

 使用头删时，需要注意当只有一个节点的情况，对于双向链表而言，p->pnext为空，此时p->pnext->ppre不存在，无法置为空，会发生栈崩溃。

//头删
int push_doulink_headpop(DLink_t *pdoulink)
{
    if(is_empty_doulink(pdoulink))
    {
        return 0;
    }
    DLink_Node_t *p = pdoulink->phead;
    pdoulink->phead = p->pnext;
    if(p->pnext != NULL)
    {
        p->pnext->ppre = NULL;
    }
    free(p);
    pdoulink->clen--;
    return 1;
}

//尾删
int push_doulink_endpop(DLink_t *pdoulink)
{
    if(is_empty_doulink(pdoulink))
    {
        return 0;
    }
    DLink_Node_t *p = pdoulink->phead;
    if(p->pnext == NULL)
    {
        push_doulink_headpop(pdoulink);
    }
    else
    {
        while(p->pnext != NULL)
        {
            p =p->pnext;
        }
        p->ppre->pnext = NULL;
        free(p);
        pdoulink->clen--;
        return 1;
    }
}

 使用完要及时销毁，避免内存泄露，可使用valgrind ./a.out查看是否发生内存泄露。

//销毁
void destroy_pdoulink(DLink_t *pdoulink)
{
    while(!(is_empty_doulink(pdoulink)))
    {
        push_doulink_headpop(pdoulink);
    }
    free(pdoulink);

}