如上图即为单链表的示意图。将结点按照一定的次序进行串联起来的，即为单链表。因为如果要访问链表中的任何一个结点的话，都需要从head处开始遍历，故称其为单链表。

单链表的每个结点存储地址并不连续（可能某两个之间是连续的，只不过几率很小），在访问的时候，只能从头指针开始沿着结点的link域进行。

使用带头结点的单链表有两个好处：

① 对带头结点的单链表，在表的任何结点之前插入节点或者删除表中的任何结点，所要做的都是修改前一结点的指针域。若单链表没有头结点，则首节点没有前驱结点，在其前插入及结点或者删除该及结点要做特殊情况处理。

② 对带头结点的单链表，表头指针是指向头及结点的非空指针，因此空链表与非空链表的处理是一样的。

其中每个节点的数据结构代码如下：

template<class T>
class LinkNode
{
public:
	T m_Data; // 数据域
	LinkNode<T>* pLink; // 指针域，指向下一个后继结点

	// 构造函数
	LinkNode(const T& data, LinkNode<T>* ptr = 0)
	{
		m_Data = data;
		pLink = ptr;
	}
};

m_Data 即是用来存储数据的成员变量。pLink 是用来指向当前节点的后继结点，如果没有则为null/0。

以下演示如何构建链表：

#include <iostream>
#include "Link.h"
using namespace std;

int main()
{
	
	LinkNode<int>* head = new LinkNode<int>(-1, 0); // 创建首个结点
	LinkNode<int>* current = head;
	const int length = 10;

	for (int i = 0; i < length; i++)
	{
		LinkNode<int>* point = new LinkNode<int>(i, current); // 创建新结点
		current->pLink = point;                               // 将当前结点的后继结点指针指向新结点
		current = current->pLink;
	}

    current = head;
	for (int i = 0; i < length; i++)
	{
		if (current != 0)
		{
			cout << current ->m_Data << " ";
			current = current ->pLink;
		}
	}
    
	system("pause");
}

实际开发过程中肯定不能像上述代码一样，构造链表需要做各种循环工作，应该封装起来，合理管理。

下面定义一个单链表的类。

#pragma once
#include "Link.h"

template<class T>
class LinkList
{
private :
	LinkNode<T> *pHead, *pTail;
	LinkNode<T> *pPre, *pCur;
	int position; // 当前元素在表中的位置序号

private :
	LinkNode<T>* GetPos(int pos); // 返回指定位置pos的指针

public:
	LinkList();
	~LinkList();
	int GetSize()const;
	bool IsEmpty()const;
	void Reset(int pos = 0);  // 初始化指针的位置
	void Next(); // 使用指针移动到一个结点
	bool EndOfList()const; // 指针是否到了链尾
	int CurrentPosition(void); // 返回当前指针的位置
	void InsertHead(const T& item); // 在表头插入结点
	void InsertTail(const T& item); // 在表尾插入结点
	void InsertAt(const T& item); // 在当前结点之前插入结点
	void InsertAfter(const T& item); // 在当前结点之后插入结点
	T DeleteCurrent(); // 删除当前结点
	T& Data(); // 返回对当前结点成员数据的引用
	const T& Data()const; // 返回对当前结点数据成员的常引用
	void Clear();  // 清空链表：释放所有结点的内存空间	
	bool InsertPos(const int pos, const T value); // 在指定位置pos插入结点
	bool DeletePos(const int pos); // 删除指定位置的结点
};

构造函数和析构函数：

template<class T>
LinkList<T>::LinkList()
{
	position = 0;
	pHead = nullptr;
	pTail = pHead;
	pPre = pHead;
	pCur = pHead;
}

template<class T>
LinkList<T>::~LinkList()
{
	LinkNode<T> *pLast, *pCurrent;
	pCurrent = pHead;

	while (pCurrent != nullptr)
	{
		pLast = pCurrent->pLink;
		delete pCurrent;
		pCurrent = pLast;
	}
}

返回指定位置 pos 的指针。

template<class T>
LinkNode<T>* LinkList<T>::GetPos(int pos)
{
	if (pos == -1 || pos == 0)
	{
		return pHead;
	}

	int count = 0; 
	LinkNode<T>* p = pHead;
	while (p != nullptr && count < pos)
	{
		p = p->pLink;
		count++;
	}
	return p;
}

如果要对当前的链表插入一个新的结点，需要怎么做呢？

1. 创建新的结点。

2. 将新建结点q的指针域link指向要插入链表中的后继结点的位置。

3. 将p结点的linkl指针域指向q。即可完成新增结点功能。

代码实现：

template<class T>
bool LinkList<T>::InsertPos(const int pos, const T value)
{
	if (pos < 0)
		return false;

	LinkNode<T> *p, *q;
	p = GetPos(pos - 1);

	// 首次插入，GetPos 返回空，则应插入成功
	if (p == pHead)
	{
		if (p == nullptr && pos == 0)
		{
			InsertHead(value);
			return true;
		}
	}

	// 如果pos前一个位置为null，则不允许插入
	if (p == nullptr)
	{
		return false;
	}

	q = new LinkNode<T>(value);
	q->pLink = p->pLink;
	p->pLink = q;
	if (p == pTail) //如果 p是表尾，则pTail 指向新结点 q;
	{
		pTail = q;
	}

	return true;
}

删除指定位置pos的结点。

将q结点的前驱结点p结点的link域指向q的后继结点，q的link域指向null，同时要清理delete q结点，否则，会引起内存泄漏。

实现代码：

template<class T>
bool LinkList<T>::DeletePos(const int pos)
{
	LinkNode<T> *p, *q;
	p = GetPos(pos - 1);  // 待删除结点的前驱结点

	// p结点不存在，则pos位置的结点不存在，删除失败
	if (p == nullptr)
	{
		return false;
	}
    
	// q 是待删除结点
	if (pos == 0)
	{
		q = pHead;
	}
	else
	{
		q = p->pLink; 
	}

	if (q != nullptr)
	{
		p->pLink = q->pLink;
	}
	else
	{
		return false;
	}

	// 首部和尾部指向同一个内存块，即链表中只有0个或者1个结点
	if (pHead == pTail)
	{
		pHead = pTail = nullptr;
	}
	else if (q == pTail) // 如果待删除结点q是链表尾部，删除后，前驱结点p变成尾部结点
	{
		pTail = p;
	}
	else if (q == pHead)// 如果待删除结点q是链表首部，删除后，q的后继结点变成首部结点
	{
		pHead = q->pLink;
	}

	if(q != nullptr)
		delete q;

	return true;
}