有头结点和没有头结点的单链表

在我们遇到的大多数题中，一般都是有头结点的单链表。这里我们可以把没有头结点的单链表看成我们的特殊情况，接下来，我们将从有头结点的单链表和没有头结点的单链表的定义，插入一个元素，删除一个元素等方面进行对比。

有头结点的单链表和没有头结点的单链表的定义：

typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

带头结点的单链表的按位插入

bool ListInsert(Linklist& l, int i, ElemType e)
{
	if (i < 1)
	{
		return false;
	}
	LNode* p;
	int j = 0;
	p = L;
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

不带头结点的单链表

bool ListInsert(LinkList& l, int i, ElemType e)
{
	if (i < 1)
		return false;
	if(i==1)
	{
		LNode* s=(LNode *)malloc(sizeof(LNode));
			s->data=e;
			s->next=L;
			L=s;
			return true;
	}
	LNode* p;
	int j = 1;
	p = L;
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

从有序插入我们都可以看出来，对于没有头结点的单链表来说，我们需要考虑当它处理的问题为第一个元素的时间，其他没有什么差别。