面试题：C语言链表内存管理与性能优化

可能出现的内存问题

内存泄漏：在单链表频繁的插入和删除操作中，如果在删除节点时没有正确释放其占用的内存，就会导致内存泄漏。例如，没有调用 free 函数释放已删除节点的内存空间。
内存碎片化：随着频繁的插入和删除操作，内存会被分割成许多小块，导致内存碎片化。当需要分配较大内存块时，可能由于碎片过多而无法满足分配需求，尽管总的可用内存足够。

优化策略

正确释放内存：在删除节点时，确保调用 free 函数释放节点占用的内存，避免内存泄漏。
内存池机制：为了减少内存碎片化和提高内存分配效率，可以使用内存池机制。内存池预先分配一块较大的内存空间，然后在需要时从这个内存池中分配小块内存给链表节点使用，释放节点时将内存返回内存池而不是归还给系统。

内存池设计思路

初始化：在程序开始时，分配一块较大的内存作为内存池。
分配内存：当需要为链表节点分配内存时，从内存池中取出一块未使用的内存块。
释放内存：当链表节点被删除时，将其占用的内存块返回内存池，标记为可用。
管理结构：使用一个数据结构（如链表）来管理内存池中的可用内存块，记录哪些内存块已被使用，哪些可用。

代码实现原理

定义内存池结构体：包含内存池的起始地址、内存池大小、可用内存块链表头指针等信息。
初始化内存池：分配一块大内存，并将其分割成多个小内存块，初始化可用内存块链表。
从内存池分配内存：从可用内存块链表中取出一个节点，返回其地址。
释放内存到内存池：将释放的内存块重新插入可用内存块链表。

C语言代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义内存块结构体
typedef struct MemoryBlock {
    struct MemoryBlock *next;
} MemoryBlock;

// 定义内存池结构体
typedef struct MemoryPool {
    MemoryBlock *freeList;  // 可用内存块链表头指针
    char *poolStart;        // 内存池起始地址
    size_t poolSize;        // 内存池大小
} MemoryPool;

// 初始化内存池
MemoryPool* createMemoryPool(size_t numBlocks, size_t blockSize) {
    MemoryPool *pool = (MemoryPool*)malloc(sizeof(MemoryPool));
    if (pool == NULL) {
        return NULL;
    }
    pool->poolSize = numBlocks * blockSize;
    pool->poolStart = (char*)malloc(pool->poolSize);
    if (pool->poolStart == NULL) {
        free(pool);
        return NULL;
    }
    pool->freeList = (MemoryBlock*)pool->poolStart;
    MemoryBlock *current = pool->freeList;
    for (size_t i = 1; i < numBlocks; ++i) {
        current->next = (MemoryBlock*)(pool->poolStart + i * blockSize);
        current = current->next;
    }
    current->next = NULL;
    return pool;
}

// 从内存池分配内存
void* allocateFromPool(MemoryPool *pool) {
    if (pool->freeList == NULL) {
        return NULL;
    }
    MemoryBlock *block = pool->freeList;
    pool->freeList = block->next;
    return block;
}

// 释放内存到内存池
void freeToPool(MemoryPool *pool, void *block) {
    ((MemoryBlock*)block)->next = pool->freeList;
    pool->freeList = (MemoryBlock*)block;
}

// 释放内存池
void destroyMemoryPool(MemoryPool *pool) {
    free(pool->poolStart);
    free(pool);
}

// 单链表节点结构体
typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

// 创建链表节点，从内存池分配内存
ListNode* createListNode(MemoryPool *pool, int data) {
    ListNode *node = (ListNode*)allocateFromPool(pool);
    if (node == NULL) {
        return NULL;
    }
    node->data = data;
    node->next = NULL;
    return node;
}

// 插入节点到链表头部
void insertNode(ListNode **head, MemoryPool *pool, int data) {
    ListNode *newNode = createListNode(pool, data);
    if (newNode != NULL) {
        newNode->next = *head;
        *head = newNode;
    }
}

// 删除链表头部节点
void deleteNode(ListNode **head, MemoryPool *pool) {
    if (*head == NULL) {
        return;
    }
    ListNode *temp = *head;
    *head = (*head)->next;
    freeToPool(pool, temp);
}

// 打印链表
void printList(ListNode *head) {
    ListNode *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    MemoryPool *pool = createMemoryPool(10, sizeof(ListNode));
    if (pool == NULL) {
        return 1;
    }
    ListNode *head = NULL;
    insertNode(&head, pool, 1);
    insertNode(&head, pool, 2);
    insertNode(&head, pool, 3);
    printList(head);
    deleteNode(&head, pool);
    printList(head);
    destroyMemoryPool(pool);
    return 0;
}

以上代码首先定义了内存池相关的结构体和函数，包括内存池的创建、内存分配、内存释放以及销毁。然后实现了一个简单的单链表，使用内存池来为链表节点分配和释放内存，从而提高内存使用效率和性能。

星途面试题库

面试题：C语言链表内存管理与性能优化

知识考点

面试题答案

可能出现的内存问题

优化策略

内存池设计思路

代码实现原理

C语言代码实现