单链表的概念：
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：数据域(数据元素的映象) + 指针域(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
头节点没有单独设计其结构体，直接使用的是有效数据节点的结构体设计，是因为：
指针域
下图展示了带头结点的单链表示意图：
typedef int ELEM_TYPE;
//有效数据节点结构体设计（头结点借用）
typedef struct Node
{
ELEM_TYPE data;//数据域 （1.头结点：不保存任何数据 2.有效数据节点：保存有效值）
struct Node *next;//指针域 (1.头结点：保存第一个元素的地址 2.有效数据节点：保存下一个有效元素的地址)
}Node, PNode;
对于带头结点的单链表，由于其头节点只需要一个指针域，所以初始化只需要对头节点进行赋值，代码如下：
// 初始化函数(对于头结点进行赋初值)
void Init_list(struct Node *plist)
{
assert(plist != NULL);
if(NULL == plist)
{
return;
}
//plist->data; 头结点的数据域不需要赋值
plist->next = NULL; // 只需要将头节点的next域赋值为NULL
}
从堆区申请一个节点大小的内存，并将申请好内存的地址返回。代码如下：
//购买一个新节点
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;
}
① 错误情况：首先断开了头节点的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;
}
尾插需要先将指针挪到最后一个节点处，挪动指针使用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;
}
【注】插入的时候，先将指针挪动到待插入位置的上一个节点，然后将待插入节点的next置为待插入位置的下一个元素的地址，这样可以保证断开指针p的next域其后面的有效数据元素仍然可以找到
//按位置插入(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;
}
头删的时候，记得先申请一个临时指针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;
}
代码如下：
//尾删
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;
}
借助头节点，无限头删。
代码如下：
//销毁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;
}
需要前驱的操作函数：插入，删除等(让指针p指向头结点，判断依据是下一个节点存不存在，存在的话向后走一步)
for(struct Node *p=plist; p->next!=NULL; p=p->next);//如果指针p循环外还使用，就提到for外面定义
不需要前驱的操作函数：查找，获取有效值个数，打印等（让指针p指向第一个元素地址，判断依据是当前指向的节点存不存在，存在的话向后走一步）
for(struct Node *p=plist->next; p!=NULL; p=p->next);
插入的时候，pos == length是合法的；但是当删除的时候，pos ==length是非法的；
删除节点的时候，需要对链表进行判空操作；
链表不存在满这个概念，所以不需要判满操作；