链表是一种线性表，但是并不是顺序存储，而是每个节点里面存储着下一个节点的指针，把存储数据元素的数据串链起来。

单链表的基本实现：

typedef int DataType;
//定义单链表
typedef struct ListNode
{
	DataType _data;    //数据
	struct ListNode * _next;   //指向下一个节点的指针
}ListNode;

//初始化
void InitList(ListNode * &pHead)
{
	pHead = NULL;
}

//创建节点
ListNode * BuyNode(DataType x)
{
	ListNode * tmp = (ListNode *)malloc(sizeof(ListNode));
	assert(tmp);
	tmp->_data = x;
	tmp->_next = NULL;
	return tmp;
}

//尾插
void PushBack(ListNode * &pHead, DataType x)
{
	if (NULL == pHead)      //为空时，表示没有节点，创建新节点
	{
		pHead = BuyNode(x);
	}
	else
	{
		ListNode * tail = pHead;   
		while (tail->_next != NULL)
		{
			tail = tail->_next;     //令tail指向最后一个节点
		}
		tail->_next = BuyNode(x);
	}
}

//头插
void PushFront(ListNode * &pHead, DataType x)
{
	if (NULL == pHead)
	{
		pHead = BuyNode(x);
	}
	else
	{
		ListNode * tmp = BuyNode(x);
		tmp->_next = pHead;
		pHead = tmp;
	}
}

//尾删
void PopBack(ListNode * &pHead)    //1.为空  2.一个节点  3，多个节点
{
	if (NULL == pHead)
	{
		printf("List is empty!\n");
		return;
	}
	else if (NULL == pHead->_next)
	{
		free(pHead);
		pHead = NULL;
	}
	else
	{
		ListNode * prevtail = NULL, *tail = pHead;
		while (tail->_next != NULL)
		{
			prevtail = tail;         //令tail指向尾部，prevtail指向倒数第二个
			tail = tail->_next;
		}
		prevtail->_next = NULL;
		free(tail);
	}
}

//头删
void PopFront(ListNode * &pHead)
{
	if (NULL == pHead)    //为空
	{
		printf("List is empty!\n");
		return;
	}
	else      //不为空
	{
		ListNode* cur = pHead;
		pHead = pHead->_next;
		free(cur);
	}
}

//查找
ListNode * Find(ListNode * pHead, DataType x)
{
	ListNode * cur = pHead;
	while (cur)
	{
		if (cur->_data == x)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}

//插入
void Insert(ListNode * &pos, DataType x)    //在pos节点后插入
{
	assert(pos);
	ListNode * tmp = BuyNode(x);
	tmp->_next = pos->_next;
	pos->_next = tmp;
}

//删除某节点
void Erase(ListNode * &pHead, ListNode * pos)
{
	assert(pos);

	if (pos == pHead)    //当要删除的节点就是第一个时，直接删
	{
		pHead = pHead->_next;
		free(pos);
	}
	else
	{
		ListNode * cur = pHead;
		while (cur)
		{
			if (cur->_next == pos)
			{
				cur->_next = pos->_next;
				free(pos);
				break;
			}
			cur = cur->_next;
		}
	}
}

//删除数据为x的节点
void Remove(ListNode * &pHead, DataType x)
{
	if (NULL == pHead)
	{
		printf("List is empty!\n");
		return;
	}
	else
	{
		ListNode * ret = Find(pHead, x);    //用ret变量指向x所在节点
		if (ret)
		{
			Erase(pHead, ret);		//删除此节点
		}
	}
}

//释放
void DestroyList(ListNode* & pHead)
{
	ListNode* cur = pHead;
	while (cur)
	{
		ListNode* tmp = cur;
		cur = cur->_next;
		free(tmp);
	}
	pHead = NULL;
}

//打印输出
void PrintList(ListNode * pHead)
{
	ListNode * cur = pHead;
	while (cur != NULL)
	{
		printf("%d -> ", cur->_data);
		cur = cur->_next;
	}
	printf("NULL\n");
}