本文轉自 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;
}
