---

一、带头结点单链表

Single linked list with leading nodes

关于不带头结点的单链表：不带头结点的单链表

二、结点与接口定义

结点定义：

typedef int SLLWDataType;
typedef struct SLLWNode
{
	SLLWDataType data;
	struct SLLWNode* next;
}SLLWNode;

接口定义：

void SLLWInit(SLLWNode** phead);

void SLLWPrint(SLLWNode* phead);

void SLLWPushFront(SLLWNode* phead, SLLWDataType x);
void SLLWPushBack(SLLWNode* phead, SLLWDataType x);

void SLLWPopFront(SLLWNode* phead);
void SLLWPopBack(SLLWNode* phead);

SLLWNode* SLLWFind(SLLWNode* phead, SLLWDataType x);

// 在pos之前插入
void SLLWInsert(SLLWNode* phead, SLLWNode* pos, SLLWDataType x);
// 在pos之后插入
void SLLWInsertAfter(SLLWNode* pos, SLLWDataType x);

// 删除pos位置的值
void SLLWErase(SLLWNode* phead, SLLWNode* pos);
// 删除pos位置后面的值
void SLLWEraseAfter(SLLWNode* pos);

// 销毁
void SLLWDestroy(SLLWNode* phead);

三、接口实现

3.1 Init初始化与申请节点

初始化需要申请头结点，让头指针指向空的头结点。

void SLLWInit(SLLWNode** phead)
{
	assert(phead);
	*phead = SLLWMalloc((SLLWDataType)230504);
}

将申请结点的代码进行封装：

SLLWNode* SLLWMalloc(SLLWDataType x)
{
	SLLWNode* newnode = (SLLWNode*)malloc(sizeof(SLLWNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

3.2 打印

需要越过头结点

void SLLWPrint(SLLWNode* phead)
{
	assert(phead);
	SLLWNode* cur = phead->next;
	while (cur)
	{
		print("[%d]->", cur->data);
		cur = cur->next;
	}
	print("NULL\n");
}

3.3 尾插PushBack

找到尾结点，然后插入到尾结点的后面。

void SLLWPushBack(SLLWNode* phead, SLLWDataType x)
{
	assert(phead);

	// Find the tail node 
	SLLWNode* tail = phead;
	while (tail->next)
	{
		tail = tail->next;
	}

	// insert it after the tail node
	SLLWNode* newnode = SLLWMalloc(x);
	tail->next = newnode;
}

对比不带头结点的单链表的尾插：

void SLLPushBack(SLLNode** pphead, SLLDataType x)
{
	assert(pphead); // 链表为空，pphead也不为空

	SLLNode* newnode = CreateSLLNode(x);
	
	if (*pphead == NULL)
	{
		// 1、空链表
		*pphead = newnode;
	}
	else
	{
		// 2、非空链表
		SLLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

我们发现相比于不带头结点的单链表尾插，带头结点的尾插的代码要更简洁，不用判断是否是空链表对插入第一个元素的单独处理。

此外，在函数的接口定义时，不带头结点的单链表还要传入二级指针，让函数外的头指针指向第一个节点，这也同样是对插入第一个元素的单独处理，而带头结点的单链表不用这样做，因为带头结点的链表在初始化时就有头结点，函数外的头指针始终指向头结点。

3.4 头插PushFront

void SLLWPushFront(SLLWNode* phead, SLLWDataType x)
{
	assert(phead);
	SLLWNode* newnode = SLLWMalloc(x);
	newnode->next = phead->next;
	phead->next = newnode;
}

3.5 头删PopFront

无论是头删还是尾删，链表中至少有一个数据元素才能进行删除：

void SLLWPopFront(SLLWNode* phead)
{
	assert(phead);
	assert(phead->next); // At least one element in the linked list can be deleted
	
	SLLWNode* del = phead->next;
	phead->next = del->next;
	free(del);
}

3.6 尾删PopBack

同头删一样，链表中要求至少有一个数据元素。

找到尾结点的前一个节点，然后将尾结点删除，其前一个节点的next域置空。

void SLLWPopBack(SLLWNode* phead)
{
	assert(phead);
	assert(phead->next);

	// Find the node before the tail node
	SLLWNode* pretail = phead;
	while (pretail->next->next)
	{
		pretail = pretail->next;
	}

    // Delete the tail node
	free(pretail->next);
	pretail->next = NULL;
}

对比不带头结点的单链表，还要对链表中只有一个元素时的PopBack进行单独处理，因为对头的处理。

3.7 查找Find

遍历链表，找到返回该节点，找不到返回空。

SLLWNode* SLLWFind(SLLWNode* phead, SLLWDataType x)
{
	assert(phead);

	SLLWNode* cur = phead->next;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

3.8 插入insert-在指定结点前插入

找到该结点前一个结点，插入到其后面。

如果pos节点没找到，在下面while循环遍历过程中，会产生空指针异常，直接报错。

void SLLWInsert(SLLWNode* phead, SLLWNode* pos, SLLWDataType x)
{
	assert(phead);
	assert(pos);

	// Find the node before the pos node
	SLLWNode* prev = phead;
	// The pos node is not found, a null pointer exception is raised
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	// The pos node is found
	SLLWNode* newnode = SLLWMalloc(x);
	prev->next = newnode;
	newnode->next = pos;
}

对比不带头结点的单链表的在pos之前进行插入，还要单独判断pos是否是第一个元素节点。而带头结点的单链表在实现时，不需要判断。

另一种偷梁换柱方法：

void SLLWInsert1(SLLWNode* phead, SLLWNode* pos, SLLWDataType x)
{
	assert(phead);
	assert(pos);

	// The consumer calls find first, then insert, 
	// so pos must be in the linked list

	SLLWNode* newnode = SLLWMalloc(pos->data);
	newnode->next = pos->next;
	pos->data = x;
	pos->next = newnode;
}

这里不需要判断pos是否在链表中，因为从使用者的角度来看，一般是先Find找到x所在的pos，然后Insert插入到找到的pos的位置之前。所以pos必在链表中。

3.9 指定pos后插

void SLLWInsertAfter(SLLWNode* pos, SLLWDataType x)
{
	assert(pos);

	SLLWNode* newnode = SLLWMalloc(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

3.10 删除Erase-在指定pos处插入

删除时，链表中至少有一个元素结点。

找到pos的前一个节点，然后将pos删除即可。

void SLLWErase(SLLWNode* phead, SLLWNode* pos)
{
	assert(phead);
	assert(phead->next);
	assert(pos);

	// Find the node before the pos node
	SLLWNode* prev = phead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	// The pos node is not found, a null pointer exception is raised
	
	// The pos node is found, delete it
	prev->next = pos->next;
	free(pos);
}

对比不带头结点的单链表，删除时还需要对只有一个元素时的链表进行单独处理。

3.11 指定pos后删

void SLLWEraseAfter(SLLWNode* pos)
{
	assert(pos);

	SLLWNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

3.12 销毁Destroy

头结点也要进行销毁。

void SLLWDestroy(SLLWNode* phead)
{
	assert(phead);

	SLLWNode* cur = phead;
	while (cur)
	{
		SLLWNode* del = cur;
		cur = cur->next;
		free(del);
	}
}

源码

gitee-SingleLinkedListWithLeadingNode

---

总结

带头结点的单链表，只要跳过头结点就变成了不带头结点的单链表，链表永远有一个头结点，所以代码写起来更简洁，特别是尾插PushBack、尾删PopBack、插入insert、删除Erase的代码。

事实上也确实如此，在实际的链表OJ题中，题目的要求是不带头结点的单链表，我们人为加上头结点，然后将逻辑代码写完后，再将添加的头结点删除，这样代码的逻辑会变得更简单。如 链表分割 、合并两个有序链表