本文转自 https://blog.csdn.net/mbuger/article/details/52528242 ### 介绍 链表是一种物理储存单元上非连续、非顺序的储存结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 ### 和顺序表的区别 顺序表使用数组存储线形的元素,其特点是可以随机存取,但是,因为逻辑上相邻的元素物理上也相邻,所以插入删除需要移动元素。链表使用指针链表示线形表元素的逻辑关系,插入和删除只需修改指针,不能随机存取。 ![](https://box.kancloud.cn/c922da1997d6863bc47b235c46540417_760x268.png) ### 代码实现 typedef struct node{ int data; struct node *next; }node_t; typedef node_t *list; ### 链表操作 void InitList(list* head)//初始化 { assert(head); *head = NULL; } list ByeNode(int data)//申请一个结点 { list newNode = NULL; newNode = (list)malloc(sizeof(Node)); if (NULL == newNode) { printf("out of memory.\n"); exit(1); } else { newNode->data = data; newNode->next = NULL; } return newNode; } void PopBack(list* head)//尾删 { assert(head); if (NULL == *head) { return; } else if(NULL == (*head)->next) { list Temlist = *head; free(Temlist); Temlist = NULL; *head = NULL; } else { list PCur = *head; while (PCur->next->next) { PCur = PCur->next; } PCur->next = NULL; } } void PushBack(list* head, int data)//尾插 { assert(head); if (NULL == *head) { *head = ByeNode(data); } else { list PCur = NULL; PCur = *head; while (PCur->next) { PCur = PCur->next; } PCur->next = ByeNode(data); } } void PushFront(list *head, int data)//头插 { assert(head); list PreNode = NULL; list Node = ByeNode(data); PreNode = *head; Node->next = PreNode; *head = Node; } void PopFront(list *head)//头删 { assert(head); list PreNode = *head; if (NULL == *head) { return; } else if (NULL == (*head)->next) { *head = NULL; } else { *head = PreNode->next; free(PreNode); PreNode = NULL; } } list Find(list* head, int data)//查找 { assert(head); list PCur = *head; while (PCur) { if (data == PCur->data) break; PCur = PCur->next; } return PCur; } void Destroy(list* head)//销毁 { assert(head); list PCur = *head; while (PCur->next) { list Dnode = PCur; PCur = PCur->next; free(Dnode); Dnode = NULL; } } int Empty(list head)//判空 { if (NULL == head) return 0; else return 1; } int Size(list head)//求链表中结点的个数 { list Node = head; int num = 0; while (Node) { num++; Node = Node->next; } return num; } void PrintList(list* head)//打印单链表 { list PCur = *head; assert(head); while (PCur) { printf("%d->",PCur->data); PCur = PCur->next; } printf("NULL\n"); } void Insert(list pos, int data)//在data后插入结点 { list newNode = ByeNode(data); list PreNode = pos; newNode->next = PreNode->next; PreNode->next = newNode; }