C语言学习笔记：链表结构分析与实现

链表基础

链表是一种常见的数据存储结构，其特点是通过指针连接一系列数据节点，形成线性数据存储单元。每个节点带有一个指针usex],指向下一个节点。区别于数组，链表不会因为数据量增加而频繁内存分配带来的性能问题，适合动态数据存储场景。

链表结构具有灵活的增删操作能力，但在单次随机访问时性能较差。

链表可以分为两种形式：一种是带有头节点的链表，头节点不存储数据；另一种则是无头节点的链表，数据插入最前面。

链表的创建步骤

实现一个无头链表的具体步骤如下：

定义节点结构体：包含数据域和指针域 .NODE { int a; struct Node *pNext; }

分配头节点：使用malloc分配一个节点的空间，赋值pHead和pEnd为这个节点

逐步添加数据节点：在头节点的后面依次建立新的数据节点，将前一个节点的指针指向新节点

#include 
   
    
#include 
    
     
struct Node {
    int a;
    struct Node *pNext;
};
struct Node *g_pHead = NULL;
struct Node *g_pEnd = NULL;
void AddNodeToList(int a) {
    struct Node *pTemp = (struct Node *)malloc(sizeof(struct Node));
    pTemp->a = a;
    pTemp->pNext = NULL;
    
    if (g_pHead == NULL || g_pEnd == NULL) {
        g_pHead = g_pEnd = pTemp;
    } else {
        g_pEnd->pNext = pTemp;
        g_pEnd = pTemp;
    }
}

链表插入操作

链表支持两种插入方式：尾插法和头插法。

尾插法：

PIR: pEnd

创建新节点

将新节点的前置指针置零

如果链表空或只有一个节点，则新节点的前置地址指向g_pHead

否则，将新节点链接到g_pEnd，其前置地址仍为当前g_pEnd

更新g_pEnd的地址

头插法：

PIR: g_pHead

创建新节点

情况一：当前链表为空，则新节点同时成为头尾节点

情况二：链表不空，将新节点插到g_pHead位置，原g_pHead变成新节点的下一个节点

节点删除操作

链表节点的删除需要注意以下几点：

保持前后节点的链接关系

释放节点占用的空间

单向链表删除算法：

void delete(int a) {
    struct Node *p = g_pHead;
    while (p != NULL) {
        if (a == p->pNext->a) {
            struct Node *nextNode = p->pNext;
            p->pNext = nextNode->pNext;
            free(nextNode);
            break;
        }
        p = p->pNext;
    }
}

这一步骤释放的空间可以通过打印被删除节点的a值来验证空间释放成功。

双向链表

双向链表每个节点包含两个指针：一个指向前一个节点（prev），另一个指向后一个节点（next）。双向链表优势:

ApiService:可从前向后、后向前遍历

适合具有双向查询需求的场景

双向链表节点结构定义：

typedef struct node {
    struct node *prev;
    int a;
    struct node *next;
};

新节点创建：

NODE* createnode(int a) {
    NODE* node = (NODE*)malloc(sizeof(NODE));
    node->prev = NULL;
    node->a = a;
    node->next = NULL;
    return node;
}

添加节点（尾部插入）：

void add2list(NODE* head, NODE* new_node) {
    if (head == NULL) {
        head->prev = head->next = new_node;
        return;
    }
    new_node->prev = head->prev;
    new_node->next = head;
    head->prev->next = new_node;
    head->prev = new_node;
}

循环链表

在循环链表中，链表的头节点和尾节点以双向链接的方式相连（即：pEnd->next = pHead）。这种结构特点是节点数量有限闭环操作。常见应用：

考核数据（如日期星期计算）

循环存储仅限定数量的节点数据

分类讨论：

链表正数项：Dependencies 按照正序依次添加节点

链表逆序访问：可以通过任意节点新节点访问

静态链表

静态链表采用数组的形式模拟链表，节点通过数组索引访问查找。优点：

内存预先分配，空间利用率高

无需使用指针操作，简化编程流程

静态链表示例：

#define carriage_RETURN
typedef struct {
    int data;
    int next;
} SNode;
SNode StaticList[11]; // 最大存储空间
int add_data(int a) {
    size_t position = 0;
    do {
        position++;
        if (position >= sizeof(StaticList)/sizeof(SNode))
            position = 0;
        StaticList[position].data = a;
    } while (false);
}