---

前言

单链表的概念：

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：数据域(数据元素的映象) + 指针域(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

---

一、带头结点的单链表结构体设计

1. 带头结点的单链表

头节点没有单独设计其结构体，直接使用的是有效数据节点的结构体设计，是因为：

1. 因为其头结点里的数据成员只需要一个：指针域
2. 有效数据节点里面的数据成员不仅有数据域还有指针域，所以直接使用有效数据节点设计

下图展示了带头结点的单链表示意图：

2. 结构体声明

typedef int ELEM_TYPE; 
//有效数据节点结构体设计（头结点借用）
typedef struct Node
{
	ELEM_TYPE data;//数据域   （1.头结点：不保存任何数据    2.有效数据节点：保存有效值）   
	struct Node *next;//指针域  (1.头结点：保存第一个元素的地址    2.有效数据节点：保存下一个有效元素的地址)
}Node, PNode;

---

二、函数实现

1. 初始化

对于带头结点的单链表，由于其头节点只需要一个指针域，所以初始化只需要对头节点进行赋值，代码如下：

// 初始化函数(对于头结点进行赋初值)
void Init_list(struct Node *plist)
{
	assert(plist != NULL);
	if(NULL == plist)
	{
		return;
	}
	//plist->data;  头结点的数据域不需要赋值
	plist->next = NULL;  // 只需要将头节点的next域赋值为NULL
}

---

2. 申请新节点

从堆区申请一个节点大小的内存，并将申请好内存的地址返回。代码如下：

//购买一个新节点
struct Node *BuyNode(ELEM_TYPE val)
{
	struct Node*pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
	assert(pnewnode != NULL);  // 断言
	if(pnewnode == NULL)
	{
		return NULL;
	}
	// 将新购买的节点进行赋值
	pnewnode->data = val;
	pnewnode->next = NULL; 

	return pnewnode;
}

---

3. 头插

① 错误情况：首先断开了头节点的next域，导致有效数据元素全部找不到了

② 正确情况：

代码如下：

//头插
bool Insert_head(struct Node *plist, ELEM_TYPE val)
{
	//1.判断参数合法性
	assert(plist != NULL);
	if(NULL == plist)
	{
		return false;
	}

	//2.1申请新节点 （插入一个节点， malloc申请一个节点）
	struct Node*pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return false;
	}
	//2.2将val值赋值给新节点
	pnewnode->data = val;
	//pnewnode->next = NULL; //?

	//3.找到合适的插入位置  （因为是头插函数， 所以直接可以得到合适的插入位置）

	//4.插入
	pnewnode->next = plist->next;//因为plist的next域指向首元素地址
	plist->next = pnewnode;

	return true;
}

---

4. 尾插

尾插需要先将指针挪到最后一个节点处，挪动指针使用for循环：

for(struct Node* p = plist; p->next!=NULL; p= p->next);
// 让指针p先指向头节点，判断依据是下一个节点是否存在，如果存在的话，p向后走一步，最终指针p可指向尾节点

代码如下：

//尾插
bool Insert_tail(struct Node *plist, ELEM_TYPE val)
{
	assert(plist != NULL);
	//1.购买新节点
	struct Node * pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if(NULL == pnewnode)
	{
		return false;
	}

	//2.找到合适的插入位置
	struct Node *p = plist;//因为指针p在for循环外面，还要使用，所以定义在for外面
	for(p; p->next!=NULL; p=p->next);
	//此时p指向尾结点

	//3.插入
	pnewnode->next = p->next; //pnewnode->next = NULL;
	p->next = pnewnode;

	return true;
}

---

5. 按位置插入

【注】插入的时候，先将指针挪动到待插入位置的上一个节点，然后将待插入节点的next置为待插入位置的下一个元素的地址，这样可以保证断开指针p的next域其后面的有效数据元素仍然可以找到

1. 按位置插入，假设pos==2，则将p指针向后依次挪动2步即可
2. 当pos == 0时，相当于头插，pos ==length时，相当于尾插
   
   代码如下：

//按位置插入(pos=0 相当于头插  pos==length 相当于尾插)
bool Insert_pos(struct Node *plist, int pos, ELEM_TYPE val)
{
	assert(plist != NULL);
	assert(pos >=0 && pos<=Get_length(plist));

	//1.购买新节点
	struct Node * pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if(NULL == pnewnode)
	{
		return false;
	}

	//2.找到合适的插入位置   
	struct Node *p = plist; 
	for(int i=0; i<pos; i++)
	{
		p=p->next;
	}

	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;

	return true;
}

---

6. 头删

头删的时候，记得先申请一个临时指针p，让指针p指向待删除节点，然后跨越指向，就可以达到删除节点的目的

代码如下：

//头删
bool Del_head(struct Node *plist)
{
	assert(plist != NULL);
	if(IsEmpty(plist))//删除需要判空
		return false;
	struct Node *p = plist->next;
	plist->next = p->next;//plist->next = plist->next->next;

	free(p);
	return true;
}

---

7. 尾删

1. 申请一个临时指针p，需要将指针p指向尾节点
2. 让指针q指向尾节点的前一个节点（前一个节点会变成新的尾节点）
3. 尾节点的next为NULL
4. 删除完成需要释放指针p

代码如下：

//尾删
bool Del_tail(struct Node *plist)
{
	assert(plist != NULL);
	if(IsEmpty(plist))   //删除需要判空
		return false;

	struct Node *p = plist;
	for(p; p->next!=NULL; p=p->next); // 此时p指向尾结点

	struct Node *q = plist;
	for(q; q->next!=p; q=q->next); // 此时q停在尾结点的前面

	q->next = p->next;//q->next = NULL;
	free(p);
	return true;
}

---

8. 销毁

借助头节点，无限头删。

代码如下：

//销毁1（malloc申请来的空间 全部释放掉）
void Destroy(struct Node *plist)
{
	assert(plist != NULL);
	//一直循环判断（判断单链表里还有没有节点,如果有,则头删一次）
	/*while(!IsEmpty(plist))
	{
		Del_head(plist);
	}
	plist->next = NULL;*/

	while(plist->next != NULL)
	{
		struct Node *p = plist->next;
		plist->next = p->next;
		free(p);
	}
	plist->next = NULL;
}

---

总结

1. 需要前驱的操作函数：插入，删除等(让指针p指向头结点，判断依据是下一个节点存不存在，存在的话向后走一步)
   for(struct Node *p=plist; p->next!=NULL; p=p->next);//如果指针p循环外还使用，就提到for外面定义

2. 不需要前驱的操作函数：查找，获取有效值个数，打印等（让指针p指向第一个元素地址，判断依据是当前指向的节点存不存在，存在的话向后走一步）
   for(struct Node *p=plist->next; p!=NULL; p=p->next);

3. 插入的时候，pos == length是合法的；但是当删除的时候，pos ==length是非法的；

4. 删除节点的时候，需要对链表进行判空操作；

5. 链表不存在满这个概念，所以不需要判满操作；