数据结构------线性表（链表）

单向链表：

一、链式存储核心概念

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;}
}

---

五、应用场景指南

场景特征	推荐结构	原因
高频随机访问	顺序表	直接下标访问优势
频繁插入删除	链表	无需数据移动
内存资源紧张	链表	精确分配无浪费
数据规模固定	顺序表	缓存友好性优势
实现简单优先级队列	链表	方便动态调整元素位置

六、应用补充

1、链表的逆序

int ReversLinkList (LinkList *ll)
{if(NULL ==ll ){return 1;}int len = GetSizeLinkList(ll);if(len<2){return 1;}LinkNode*prev = NULL;LinkNode*tmp = ll->head;LinkNode*next = tmp->next;while (1){tmp->next = prev;  //逆序prev = tmp;tmp = next;if (NULL == tmp) { break; }next = next->next;}ll->head = prev;return 0;
}

1.1链表逆序（方法二）

int ReverseLinkList(LinkList *ll)
{LinkNode *pre = ll->head;LinkNode *cur = ll->head->next;while (cur){pre->next = cur->next;cur->next = ll->head;ll->head = cur;cur = pre->next;}return 0;
}

2.查找链表的中间节点

LinkNode *MiddleLinkList(LinkList *ll)
{if (NULL == ll){fprintf(stderr, "MiddleLinkList parmter error\n");return 1;}LinkNode *slow = ll->head;LinkNode *fast = ll->head;while (1){fast = fast->next;if (NULL == fast){return slow;break;}slow = slow->next;fast = fast->next;if (NULL == fast){return slow;break;}}return NULL;
}

3.查找链表倒数第k个节点

LinkNode *backwardsLinkList(LinkList *ll, int cnt)
{if (NULL == ll || cnt > ll->clen || cnt < 1){fprintf(stderr, "backwardsLinkList parmter error\n");return NULL;}LinkNode *slow = ll->head;LinkNode *fast = ll->head;for (int i = 0; i < cnt; i++){fast = fast->next;}while (fast){slow = slow->next;fast = fast->next;if (NULL == fast){break;}}return slow;
}

4.链表的插入排序

int InsertLinkList(LinkList *ll)
{LinkNode *phead = ll->head;LinkNode *pinsert = phead->next;LinkNode *pnext = pinsert->next;phead->next = NULL;while (1){phead = ll->head;while (phead->next != NULL && pinsert->data.score > phead->data.score && pinsert->data.score > phead->next->data.score){phead = phead->next;}if (pinsert->data.score < phead->data.score){pinsert->next = phead;ll->head = pinsert;}else{pinsert->next = phead->next;phead->next = pinsert;}pinsert = pnext;if (NULL == pinsert){break;}pnext = pnext->next;}
}