我们都知道不管是单链表、双向链表还是循环链表，都带有头结点，这个头结点相当于一个起始的位置。我们在设计带头结点的单链表的时候，我们会在主函数中设计一个头结点，并把它的指针域置为空，这样我们就可以进行增删查改这些操作了。那我们今天这篇博客就来说一下不带头结点的单链表。
一、不带头结点的单链表的定义
我们先来回忆一下带头结点的单链表是什么样子。如下图所示：红色的区域就是头结点，它有一个头指针指向它。

这样的话我们在设计单链表的时候总要浪费一个空间来设计头结点。那我们有什么方式来让整个链表之存放数据元素不存放头结点呢？这就是所谓的不带头结点的单链表，整个链表的结构如下图所示：

链表都有唯一的起始和唯一的结尾。那么不带头结点的单链表就以头指针为唯一的起始，最后一个结点的指针域为唯一的结尾。满足线性关系。
三、相关实现
1、整体结构的定义

typedef struct Node
{ElemType data;struct Node* next;
}Node,*plist;

2、不带头结点的单链表的基本实现
不带头结点的单链表操作中，除了初始化、删除和插入操作与带头结点的单链表有差别外，其它的操作基本上一样。除了插入，删除，清空操作需要传递头指针的地址外，其他基本上一样。

void init(Node** phead)//初始化
{*phead = NULL;
}
Node* buyNode(ElemType val)//购买新的结点
{Node* pnewnode = (Node*)malloc(sizeof(Node));pnewnode->data = val;pnewnode->next = NULL;return pnewnode;
}
int insertHead(plist* phead,ElemType val)//头插
{Node* pnewnode = buyNode(val);pnewnode->next = (*phead);(*phead) = pnewnode;return 1;
}
int insertTail(plist* ptwohead,ElemType val)//尾插
{ Node* pnewnode = buyNode(val);Node* ptail = *ptwohead;if(*ptwohead == NULL){(*ptwohead ) = pnewnode;}while(ptail->next != NULL){ptail = ptail->next;}ptail->next = pnewnode;return 1;
}
int empty(Node* phead)//判空
{return phead == NULL?1:0;
}
int deleteHead(Node* phead)//头删
{if(empty(*ptwohead)){return 0;}Node* pcur = *ptwohead;*ptwohead = pcur->next;free(pcur);return 1;
}
int deletetail(Node* ptwohead)//尾删
{if(empty(*ptwohead)){return 0;}Node* pfront = *ptwohead;Node* pcur = pfront->next;if(pcur==NULL){*ptwohead = NULL;free(pfront);return 1;}while(pfront->next! =NULL){pcur = pfront->next;if(pcur->next == NULL){break;}pfront = pfront->next;pfront->next = NULL;free(pcur);return 1;}
}
void show(Node* phead)
{Node* pcur = head;while(pcur != NULL){printf("%d",pcur->data);pcur = pcur->next;}printf("\n");
}
void destroy(plist* ptwohead)//销毁
{Node * pcur = *ptwohead;Node* pnext = NULL;while(pcur!=NULL){pnext = pcur->next;free(pcur);pcur = pnext;}*ptwohead = NULL;
}