单向链表:
一、链式存储核心概念
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;}
}
五、应用场景指南
场景特征 | 推荐结构 | 原因 |
---|
高频随机访问 | 顺序表 | 直接下标访问优势 |
频繁插入删除 | 链表 | 无需数据移动 |
内存资源紧张 | 链表 | 精确分配无浪费 |
数据规模固定 | 顺序表 | 缓存友好性优势 |
实现简单优先级队列 | 链表 | 方便动态调整元素位置 |