本文转自 https://blog.csdn.net/mbuger/article/details/52528242
### 介绍
链表是一种物理储存单元上非连续、非顺序的储存结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
### 和顺序表的区别
顺序表使用数组存储线形的元素,其特点是可以随机存取,但是,因为逻辑上相邻的元素物理上也相邻,所以插入删除需要移动元素。链表使用指针链表示线形表元素的逻辑关系,插入和删除只需修改指针,不能随机存取。
### 代码实现
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;
}
