单向链表：
一、链式存储核心概念
1. 节点结构定义
// 数据元素类型（与顺序表相同）
typedef struct person {char name[32];char sex;int age;int score;
} DATATYPE;// 单向链表节点
typedef struct node {DATATYPE data;struct node *next; // 后继指针（单向链表只需此指针）
} LinkNode;// 链表管理结构
typedef struct list {LinkNode *head; // 头节点指针int clen; // 当前元素个数
} LinkList;
二、核心操作实现要点
1. 创建链表
LinkList *CreateLinkList() {LinkList *list = (LinkList*)malloc(sizeof(LinkList));list->head = NULL; // 空链表初始化list->clen = 0;return list;
}
2. 头部插入
int InsertHeadLinkList(LinkList *list, DATATYPE data) {LinkNode *newnode = (LinkNode*)malloc(sizeof(LinkNode));newnode->data = data;newnode->next = list->head;list->head = newnode;list->clen++;return 0;
}
3. 尾部插入
int InsertTailLinkList(LinkList *list, DATATYPE data) {LinkNode *newnode = (LinkNode*)malloc(sizeof(LinkNode));newnode->data = data;newnode->next = NULL;if(!list->head) {list->head = newnode;} else {LinkNode *cur = list->head;while(cur->next) cur = cur->next;cur->next = newnode;}list->clen++;return 0;
}
4. 节点查找
LinkNode *FindLinkList(LinkList *list, char *name) {LinkNode *cur = list->head;while(cur) {if(strcmp(cur->data.name, name) == 0)return cur;cur = cur->next;}return NULL;
}
三、存储结构对比分析
| 对比维度 | 顺序表 | 链表 |
|---|
| 存储方式 | 连续内存空间 | 离散内存节点 |
| 容量管理 | 固定大小，需预分配 | 动态增长，按需分配 |
| 随机访问 | O(1) | O(n) |
| 插入/删除 | O(n)（需移动元素） | O(1)（已知节点位置） |
| 内存利用率 | 可能存在空间浪费 | 无内存浪费（精确分配） |
| 缓存友好性 | 优秀（空间局部性） | 较差（节点离散存储） |
四、内存管理实践
1. 节点删除示例
int DelLinkList(LinkList *ll,char*name)
{if (NULL == ll || NULL == name){return 1;}LinkNode *tmp = ll->head;if(0 == strcmp(tmp->data.name,name))//head del{ll->head = ll->head->next;free(tmp);}else{while (strcmp(tmp->next->data.name,name)){tmp = tmp->next;if(NULL == tmp->next){return 1;}}LinkNode *free_node = tmp->next;tmp->next = tmp->next->next;}ll->clen--;return 0;
}
2. 链表销毁
int DestroyLinkList(LinkList *ll)
{LinkNode *tmp = ll->head;while(1){ll->head = ll->head->next;free(tmp);tmp = ll->head;if(NULL == tmp){break;}free(ll);return 0;}
}
五、应用场景指南
| 场景特征 | 推荐结构 | 原因 |
|---|
| 高频随机访问 | 顺序表 | 直接下标访问优势 |
| 频繁插入删除 | 链表 | 无需数据移动 |
| 内存资源紧张 | 链表 | 精确分配无浪费 |
| 数据规模固定 | 顺序表 | 缓存友好性优势 |
| 实现简单优先级队列 | 链表 | 方便动态调整元素位置 |
)
