单链表的实现（c++）

什么是单链表

• 我们知道顺序表的最大的缺点是插入和删除操作可能移动大量的元素，会导致程序的执行效率很低。导致程序低效的原因就是顺序表的元素必须连续且不能有间隙，建立一个顺序表的时候需要在内存中很大一片连续空的空间进行创造。
• 线性表的链式存储不需要使用连续的内存空间，链式存储是是通过“链”也就是指针的指向来建立各个相邻元素的关系，使其保证元素之间像一条线一样按顺序排列。
  • 优点：我们在插入和删除元素的时候，就不需要进行大量的数据元素的迁移，只需改变修改元素的（结点）的指针的指向。
  • 缺点：结点结构比顺序表的结点结构要复杂一点。

---

单链表的数据成员

• 一个结点包含一个数据域和一个指针域（指针的内容是指向下一个结点的地址）

template <typename T>
	struct Node
	{
		T data;			//数据域
		Node<T>* next;	//指针域

	};

---

单链表的基本操作

• 单链表的类的定义和设计

  • 构造函数

  • 析构函数

  • 插入元素

    • 在第i个位置插入元素
    • 快速在尾部插入元素
    • 在已知结点之前插入元素

  • 删除第i个位置的元素

  • 获取元素

  • 按元素值查找第一次出现的位置

  • 展示链表所有元素

  • 获取链表的长度

  • 判断链表是否为空

  • 翻转链表

  • 查看尾指针

---

单链表的编程实现

单链表类的定义

(这个版本是包含了尾指针的)

// 定义单链表
	template<typename T>
	class Link_List
	{
	public:
		Link_List();  //构造函数
		~Link_List();	//析构函数
	
	public:
	//插入操作
		//按位置插入元素
		bool Link_List_Insert(int i, const T& e);		//在第i个位置插入元素
		//快速在尾部插入元素
		void Link_List_Insert_Back(const T& e);
		//在已知的结点之前插入元素
		bool Link_List_Prior_Insert_Node(const T& e, Node<T>*purr );	

	//删除
		bool Link_List_Delete(int i);
		
	//获取元素
		T Get_Link_List_Elem(int i);		//获取第i个元素的值
		Node<T>* Get_Link_List_point(int i);//获取第i个元素的指向

	//按照元素值查找链表中第一次出现的位置
		int Locate_Link_List_Elem(const T& e);

	// 输出链表所有的元素
		void Display_Link_List();

	//获取链表的长度
		int Link_List_length();

	//判断链表是否为空
		bool Link_List_Empty();

	// 翻转链表
		void Reverse_Link_List();

	// 查看尾指针
		void rear();


	// 数据成员
	private:
		Node<T>* m_head;	//单链表的头指针
		int m_length;		//单链表的实际长度
		 Node<T>* m_rear ;	//单链表的尾指针
	};

---

1)构造函数（初始化）

• 首先会开辟一个内存存储结点，并让头指针指向它
• 因为是第一个结点，又是链表，头结点的指针域暂时指向nullptr
• 记录链表长度（头结点不算入）
• 尾指针指向链表尾部，初始化指向头结点（尾指针永远指向尾部）
• 注意事项：链表只要进行结构的变化（比如说进行删除结点，插入结点）一定要及时更新链表的长度和尾指针的指向

// 构造函数定义
	template<typename T>
	Link_List<T>::Link_List()
	{
		m_head = new Node<T>;		//头指针初始化并指向开辟一个内存
		m_head->next = nullptr;		//头结点是链表的第0个结点，此时也是尾结点
		m_length = 0;				//头结点不算入实际长度
		m_rear = m_head;			//尾指针指向尾结点
	}

---

2)析构函数

• 对链表中每个结点都必须进行释放
• 释放的同时，表的长度更新为0

//析构函数进行释放
	template<typename T>
	Link_List<T>::~Link_List()
	{
		//对链表中的每个结点都需要进行释放
		Node<T>* pnode = m_head->next;	//记录下一个结点的指向
		Node<T>* ptemp;					//记录释放的结点
		while (pnode != nullptr)
		{
			ptemp = pnode;
			pnode = pnode->next;	//更新结点
			delete ptemp;
		}
		delete m_head;
		m_head = nullptr;	//非必须，建议
		m_rear = nullptr;	//非必须，建议
		m_length = 0;
	}

---

3)插入元素

• 头部插入，尾部插入，中间元素插入均可适用 **在第i个位置插入元素 **这个版本
• 快速在尾部插入元素 与 在第i个位置插入元素的尾部插入是一样的，只是少了个形参
• 在已知的结点之前插入元素 设计这个目的是时间复杂度O（1），就不需要去遍历单链表的所有元素
• 上述的头部插入时间复杂度为O（1）；尾部插入是因为设计了一个尾指针永远指向尾部结点，则尾部插入也是O（1）；中间插入结点 需要去遍历链表找到该位置的前一个结点，则时间复杂度为O（n）

//插入操作
		//在第i个位置插入元素
		bool Link_List_Insert(int i, const T& e);		
		//快速在尾部插入元素
		void Link_List_Insert_Back(const T& e);
		//在已知的结点之前插入元素
		bool Link_List_Prior_Insert_Node(const T& e, Node<T>*purr );

---

4)在第i个位置插入元素

• 判断位置i是否合法
• 判断第i个位置是否为单链表尾部，是则调用 快速在尾部插入元素
• 如果i =1相当于头插法
• 更新表长；如果是尾部插入，在 快速在尾部插入元素 里面已经更新了尾指针的指向和单链表的表长；不是尾部插入只需要更新单链表长
• i= 1，时间复杂度为O（1）；尾部插入，时间复杂度为O（1）；其他位置插入的平均时间复杂度为O（n)

// 在第i个位置插入元素
	template<typename T>
	bool Link_List<T>::Link_List_Insert(int i ,const T& e)
	{

		if (i<1 || i>(m_length + 1))
		{
			cout << "插入位置" << i << "不合法，合法的位置是1到"
				<< m_length + 1 << "之间!" << endl;
			return false;
		}

		//如果是要插入尾指针之后
		//如果i= 表长+1 ：代表就插入在尾处，相当于单链表的尾插法
		if (i - 1 == m_length)
		{
			Link_List_Insert_Back( e);
			return true;
		}

		Node<T>* p_curr = m_head;		//新建一个指针的目的是为指向第（i-1)的结点

		//开始定位第i-1位置的结点
		//如果i=1，直接跳过for循环，在头结点下一个位置插入，相当于单链表的头插法
		for (int j = 0; j < (i - 1); j++)
		{
			p_curr = p_curr->next;
		}

		Node<T>* node = new Node<T>;	//开辟一个新的内存存储要插入的结点
		node->data = e;					//存储数据域
		node->next = p_curr->next;		//以下两步指针域指向赋值顺序不可颠倒
		p_curr->next = node;
		cout << "成功在位置为" << i << "处插入元素" << e << "!" << endl;
		m_length++;						//更新表长

5)快速在尾部插入元素

• 核心步骤都是一样的
• 时间复杂度为O（1）

template<typename T>
	void Link_List<T>::Link_List_Insert_Back(const T& e)
	{
		Node<T>* node = new Node<T>;		//存储新节点
		node->data = e;
		node->next = m_rear->next;
		m_rear->next = node;
		m_rear = node;						//更新尾指针
		if (m_rear->next == nullptr)
		{
			cout << "尾部插入元素成功，更新尾指针成功" << endl;
		}
		m_length++;
		
	}

---

6)在已知结点之前插入元素

• 先判断结点是否是尾结点
• 先将这个新结点插入到已知结点之后
• 然后将其已知结点和新结点的数据域进行交换
• 时间复杂度为O(1)

//已知结点插入元素
template<typename T > 
bool Link_List<T>::Link_List_Prior_Insert_Node(const T& e, Node<T>* purr )
{
	//链表末尾插入（防止已知结点是尾结点）
	if (purr->next == nullptr)
	{
		Link_List_Insert_Back( e);
		
		return true;
	}
	//在purr结点之前插入新结点
	//先将新结点插入到已知结点之后
	Node<T>* node = new Node<T>;
	node->data = e;
	node->next = purr->next;
	purr->next = node;
	Display_Link_List();
	//交换数据域
	T temp = node->data;
	node->data = purr->data;
	purr->data = temp;
	m_length++;
	return true;

}

这个程序是便于获得某个元素的指向来作为上一个程序的形参来进行检验的

//获得第i个位置的元素,返回指针
	template<typename T>
	Node<T>* Link_List<T>:: Get_Link_List_point(int i)
	{
		

		Node<T>* p_curr = m_head;

		for (int j = 0; j < i; j++)
		{
			p_curr = p_curr->next;
		}

		return p_curr;
	}

---

7)删除第i个位置的元素

• 判断链表是否为空

• 判断位置i是否为链表的合法位置

• 遍历链表找第i-1个位置的元素

  • 如果 i =表长，则说明删除的结点是尾结点，则需要更新尾指针，和前一个结点的指针域赋值为nullptr

• 更新表长

• 释放要删除的结点

// 删除操作
template<typename T>
bool Link_List<T>::Link_List_Delete(int i)
{
	//判断链表是否为空
	if (m_length == 0)
	{
		cout << "链表为空不可删除元素" << endl;
		return false;
	}

	//判断删除是否合法位置
	if (i<1 || i>m_length)
	{
		cout << "删除的位置" << i << "不合法，合法的位置是1到" 
		<< m_length << "之间!" << endl;
	}
	
	Node<T>* p_curr = m_head;
	
	//找到第（i-1）位置结点的指向
	for (int j = 0; j < (i - 1); j++)
	{
		p_curr = p_curr->next;  //指向第i-1位置
	}

	//指针域指向操作
	Node<T>* will_delete = p_curr->next;  //will_delete指向第i个位置结点
	p_curr->next = will_delete->next;

	cout << "成功删除位置为" << i << "的元素，该元素的值为" 
	<< will_delete->data << "!" << endl;
	
	//更新尾指针
	if (i == m_length)
	{
		cout << "说明删除的是尾结点,需要更新尾指针" << endl;
		m_rear = p_curr;
		if (m_rear->next == nullptr)
		{
			cout << "更新尾结点成功" << endl;
		}
	}
	m_length--;		//表长-1
	//释放删除的结点
	delete will_delete;
	return true;
}

---

8)获取元素

• 判断链表是否为空
• 判断位置i是否为链表的合法位置
• 遍历寻找

//获得第i个位置的元素,返回值
	template<class T>
	T Link_List<T>::Get_Link_List_Elem(int i)
	{
		if (m_length < 1)
		{
			cout << "当前单链表为空，不能获取任何数据!" << endl;
			return false;
		}

		if (i < 1 || i > m_length)
		{
			cout << "获取元素的位置" << i << "不合法，合法的位置是1到"
			<< m_length << "之间!" << endl;
			return false;
		}

		Node<T>* p_curr = m_head;
		
		for (int j = 0; j < i; j++)	//这里是i不是i-1
		{
			p_curr = p_curr->next;
		}
		
		cout << "成功获取位置为" << i << "的元素，该元素的值为" 
		<< p_curr->data << "!" << endl;
		return p_curr->data;
		
	}

---

9)按元素值查找第一次出现的位置

//按照元素值查找链表中第一次出现的位置
	template<class T>
	int Link_List<T>::Locate_Link_List_Elem(const T& e)
	{
		Node<T>* p_curr = m_head;
		for (int i = 1; i <= m_length; i++)
		{
			p_curr = p_curr->next;
			if (p_curr->data == e)
			{
				cout << "值为" << e << "的元素在单链表中第一次出现的位置为" 
				<< i << "!" << endl;
				return i;
			}
			
		}
		cout << "值为" << e << "的元素在单链表中没有找到!" << endl;
		return -1;		//查找失败
	}

---

10)展示链表所有元素

// 输出链表所有的元素
	template<typename T>
	void Link_List<T>::Display_Link_List() 
	{
		Node<T>* p = m_head;
		cout << "单链表所有元素展示：" << endl;
		for (int i = 1; i <= m_length; i++)
		{
			p = p->next;
			cout << p->data << " ";
		}
		cout << endl;
	}

---

11)获取链表的长度

//获取链表的长度
	template<typename T>
	int Link_List<T>::Link_List_length()
	{
		return m_length;
	}

12)判断链表是否为空

//判断链表是否为空
	template<typename T>
	bool Link_List<T>:: Link_List_Empty()
	{
		if (m_head->next == nullptr) //单链表为空（如果是不带头结点的单
									//链表则用if(m_head == nullptr）来判断是否为空）
		{
			
			return true;
		}
		cout << "单链表不为空" << endl;
		return false;
	}

---

13)翻转链表

以a0 a1 a2 a3 a4为例，其中a0为头结点

• 判断单链表是否为空或者只有一个元素

• 将头结点和第二个结点作为一个整体（a0和a1），翻转过后a1作为最后一个元素，则a1的指针域为nullptr，尾指针也要更新为a1

• 后续只要改变的a2元素的指针域的指向（和头插法的步骤一致），同时也要更新要处理的结点也就是a3

  

// 翻转链表
	template<typename T>
	void Link_List<T>::Reverse_Link_List()
	{
		if (m_length <= 1)
		{
			//如果没有顺序表中没有元素或者只有一个元素，那么就不用做任何操作
			return;
		}

		
		Node<T>* p2 = m_head->next->next;	// 获取指向第二个结点的指针域
		m_head->next->next = nullptr;	//将第一个结点的指针域赋值为空（作为最后一个结点）
		m_rear = m_head->next;			//更新尾指针

		Node<T>* p_curr;
		//只要改变第二个结点的指针域指向，便可改变顺序
		//具体步骤和头插法一致
		while (p2 != nullptr)
		{
			p_curr = p2;		//当前（假设a2)赋给p_curr指针进行插入操作
			p2 = p2 -> next;		//更新结点
			 
			p_curr->next = m_head->next;
			m_head->next = p_curr;
		}
	}

14)查看尾指针

• 主要用于查看是否正确

template <typename T>
	void Link_List<T>::rear()
	{
		cout << " 链表最后一个元素为"<<m_rear->data << endl;
	}

---

主函数

int main()
{

	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
	_nmsp::Link_List<int> Creat_link;
	Creat_link.Link_List_Insert(1, 1);
	Creat_link.Link_List_Insert(2, 2);
	Creat_link.Link_List_Insert(3, 3);
	Creat_link.Link_List_Insert(4, 4);
	Creat_link.Link_List_Insert(5, 5);
	Creat_link.Display_Link_List();

	Creat_link.Link_List_Insert(3, 10);

	int length = Creat_link.Link_List_length();
	cout << "单链表长度为" << length << endl;

	Creat_link.Display_Link_List();
	Creat_link.rear();

	Creat_link.Reverse_Link_List();
	Creat_link.Display_Link_List();
	Creat_link.rear();
	

	
	Creat_link.Get_Link_List_Elem(3);
	Creat_link.Link_List_Empty();
	Creat_link.Locate_Link_List_Elem(1);

	Creat_link.Link_List_Delete(6);
	Creat_link.Display_Link_List();
	Creat_link.rear();
	
	_nmsp::Node<int> * node = Creat_link.Get_Link_List_point(4);
	Creat_link.Link_List_Prior_Insert_Node(1000, node);
	Creat_link.Display_Link_List();
	Creat_link.rear();
	cout << "hello world";
	return 0;
	

}

---

总结

• 并不需要大片的连续存储空间来存放数据元素，扩容很方便

• 插入和删除结点相对于顺序表来说很方便，平均时间复杂度为O（n），如果是头部插入和尾部插入和在已知结点插入，那么时间复杂度就为O（1），这也就说明链表更适合插入，删除的频繁操作

• 存放后后继指针要额外的消耗存储空间，体现了利用空间来换时间来提高算法效率的编程思想

• 单链表也有一个很大的弊端，它的内存空间不连续，无法实现随机访问单链表中的元素，如果要访问某个结点只能从链表中第一个结点开始往下进行遍历，单链表的主要时间都花在了遍历元素的方面，平均时间复杂度为O（n).

---

全部代码

# include<iostream>

#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif

using namespace std;
namespace _nmsp
{
	template <typename T>
	struct Node
	{
		T data;
		Node<T>* next;

	};


	// 定义单链表
	template<typename T>
	class Link_List
	{
	public:
		Link_List();  //构造函数
		~Link_List();	//析构函数

	public:
		//插入操作
			//按位置插入元素
		bool Link_List_Insert(int i, const T& e);		//在第i个位置插入元素
		//快速在尾部插入元素
		void Link_List_Insert_Back(const T& e);
		//在已知的结点之前插入元素
		bool Link_List_Prior_Insert_Node(const T& e, Node<T>* purr);

		//删除
		bool Link_List_Delete(int i);

		//获取元素
		T Get_Link_List_Elem(int i);		//获取第i个元素的值
		Node<T>* Get_Link_List_point(int i);//获取第i个元素的指向

		//按照元素值查找链表中第一次出现的位置
		int Locate_Link_List_Elem(const T& e);

		// 输出链表所有的元素
		void Display_Link_List();

		//获取链表的长度
		int Link_List_length();

		//判断链表是否为空
		bool Link_List_Empty();

		// 翻转链表
		void Reverse_Link_List();

		// 查看尾指针
		void rear();


		// 数据成员
	private:
		Node<T>* m_head;	//单链表的头指针
		int m_length;		//单链表的实际长度
		Node<T>* m_rear;	//单链表的尾指针
	};


	// 构造函数定义
	template<typename T>
	Link_List<T>::Link_List()
	{
		m_head = new Node<T>;		//头指针初始化并指向开辟一个内存
		m_head->next = nullptr;		//头结点是链表的第0个结点，此时也是尾结点
		m_length = 0;				//头结点不算入实际长度
		m_rear = m_head;			//尾指针指向尾结点
	}

	// 在第i个位置插入元素
	template<typename T>
	bool Link_List<T>::Link_List_Insert(int i, const T& e)
	{

		if (i<1 || i>(m_length + 1))
		{
			cout << "插入位置" << i << "不合法，合法的位置是1到"
				<< m_length + 1 << "之间!" << endl;
			return false;
		}

		// 如果是要插入尾指针之后
		// 如果i= 表长+1 ：代表就插入在尾处，相当于单链表的尾插法
		if (i - 1 == m_length)
		{
			Link_List_Insert_Back(e);
			return true;
		}

		Node<T>* p_curr = m_head;		//新建一个指针的目的是为指向第（i-1)的结点

		//开始定位第i-1位置的结点
		//如果i=1，直接跳过for循环，在头结点下一个位置插入，相当于单链表的头插法

		for (int j = 0; j < (i - 1); j++)
		{
			p_curr = p_curr->next;
		}

		Node<T>* node = new Node<T>;	//开辟一个新的内存存储要插入的结点
		node->data = e;					//存储数据域
		node->next = p_curr->next;		//以下两步指针域指向赋值顺序不可颠倒
		p_curr->next = node;
		cout << "成功在位置为" << i << "处插入元素" << e << "!" << endl;
		m_length++;						//更新表长


		return true;

	}

	// 快速在尾部插入元素
	template<typename T>
	void Link_List<T>::Link_List_Insert_Back(const T& e)
	{
		Node<T>* node = new Node<T>;
		node->data = e;
		node->next = m_rear->next;
		m_rear->next = node;
		m_rear = node;
		if (m_rear->next == nullptr)
		{
			cout << "尾部插入元素成功，更新尾指针成功" << endl;
		}
		m_length++;

	}

	// 已知结点插入元素
	template<typename T >
	bool Link_List<T>::Link_List_Prior_Insert_Node(const T& e, Node<T>* purr)
	{
		// 链表末尾插入（防止已知结点是尾结点）
		if (purr->next == nullptr)
		{
			Link_List_Insert_Back(e);

			return true;
		}
		// 在purr结点之前插入新结点
		Node<T>* node = new Node<T>;
		node->data = e;
		node->next = purr->next;
		purr->next = node;
		Display_Link_List();
		// 交换数据域
		T temp = node->data;
		node->data = purr->data;
		purr->data = temp;
		m_length++;
		return true;

	}


	// 删除操作
	template<typename T>
	bool Link_List<T>::Link_List_Delete(int i)
	{
		// 判断链表是否为空
		if (m_length == 0)
		{
			cout << "链表为空不可删除元素" << endl;
			return false;
		}

		// 判断删除是否合法位置
		if (i<1 || i>m_length)
		{
			cout << "删除的位置" << i << "不合法，合法的位置是1到"
				<< m_length << "之间!" << endl;
		}

		Node<T>* p_curr = m_head;

		// 找到第（i-1）位置结点的指向
		for (int j = 0; j < (i - 1); j++)
		{
			p_curr = p_curr->next;  //指向第i-1位置
		}

		// 指针域指向操作
		Node<T>* will_delete = p_curr->next;  //will_delete指向第i个位置结点
		p_curr->next = will_delete->next;

		cout << "成功删除位置为" << i << "的元素，该元素的值为"
			<< will_delete->data << "!" << endl;

		// 更新尾指针
		if (i == m_length)
		{
			cout << "说明删除的是尾结点,需要更新尾指针" << endl;
			m_rear = p_curr;
			if (m_rear->next == nullptr)
			{
				cout << "更新尾结点成功" << endl;
			}
		}
		m_length--;		//表长-1
		// 释放删除的结点
		delete will_delete;
		return true;
	}


	// 获得第i个位置的元素,返回值
	template<class T>
	T Link_List<T>::Get_Link_List_Elem(int i)
	{
		if (m_length < 1)
		{
			cout << "当前单链表为空，不能获取任何数据!" << endl;
			return false;
		}

		if (i < 1 || i > m_length)
		{
			cout << "获取元素的位置" << i << "不合法，合法的位置是1到"
				<< m_length << "之间!" << endl;
			return false;
		}

		Node<T>* p_curr = m_head;

		for (int j = 0; j < i; j++)
		{
			p_curr = p_curr->next;
		}

		cout << "成功获取位置为" << i << "的元素，该元素的值为"
			<< p_curr->data << "!" << endl;
		return p_curr->data;

	}

	// 获得第i个位置的元素,返回指针
	template<typename T>
	Node<T>* Link_List<T>::Get_Link_List_point(int i)
	{


		Node<T>* p_curr = m_head;

		for (int j = 0; j < i; j++)
		{
			p_curr = p_curr->next;
		}

		return p_curr;
	}


	// 按照元素值查找链表中第一次出现的位置
	template<class T>
	int Link_List<T>::Locate_Link_List_Elem(const T& e)
	{
		Node<T>* p_curr = m_head;
		for (int i = 1; i <= m_length; i++)
		{
			p_curr = p_curr->next;
			if (p_curr->data == e)
			{
				cout << "值为" << e << "的元素在单链表中第一次出现的位置为"
					<< i << "!" << endl;
				return i;
			}

		}
		cout << "值为" << e << "的元素在单链表中没有找到!" << endl;
		return -1;		//查找失败
	}


	// 输出链表所有的元素
	template<typename T>
	void Link_List<T>::Display_Link_List()
	{
		Node<T>* p = m_head;
		cout << "单链表所有元素展示：" << endl;
		for (int i = 1; i <= m_length; i++)
		{
			p = p->next;
			cout << p->data << " ";
		}
		cout << endl;
	}


	// 获取链表的长度
	template<typename T>
	int Link_List<T>::Link_List_length()
	{
		return m_length;
	}


	// 判断链表是否为空
	template<typename T>
	bool Link_List<T>::Link_List_Empty()
	{
		if (m_head->next == nullptr) //单链表为空（如果是不带头结点的单
			//链表则用if(m_head == nullptr）来判断是否为空）
		{

			return true;
		}
		cout << "单链表不为空" << endl;
		return false;
	}

	// 翻转链表
	template<typename T>
	void Link_List<T>::Reverse_Link_List()
	{
		if (m_length <= 1)
		{
			//如果没有顺序表中没有元素或者只有一个元素，那么就不用做任何操作
			return;
		}


		Node<T>* p2 = m_head->next->next;	// 获取指向第二个结点的指针域
		m_head->next->next = nullptr;	//将第一个结点的指针域赋值为空（作为最后一个结点）
		m_rear = m_head->next;			//更新尾指针

		Node<T>* p_curr;
		// 只要改变第二个结点的指针域指向，便可改变顺序
		// 具体步骤和头插法一致
		while (p2 != nullptr)
		{
			p_curr = p2;		//当前（假设a2)赋给p_curr指针进行插入操作
			p2 = p2->next;		//更新结点

			p_curr->next = m_head->next;
			m_head->next = p_curr;
		}
	}


	// 析构函数进行释放
	template<typename T>
	Link_List<T>::~Link_List()
	{
		// 对链表中的每个结点都需要进行释放
		Node<T>* pnode = m_head->next;
		Node<T>* ptemp;
		while (pnode != nullptr)
		{
			ptemp = pnode;
			pnode = pnode->next;	//更新结点
			delete ptemp;
		}
		delete m_head;
		m_head = nullptr;
		m_rear = nullptr;
		m_length = 0;
	}

	template <typename T>
	void Link_List<T>::rear()
	{
		cout << " 链表最后一个元素为" << m_rear->data << endl;
	}

}


int main()
{

	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
	_nmsp::Link_List<int> Creat_link;
	Creat_link.Link_List_Insert(1, 1);
	Creat_link.Link_List_Insert(2, 2);
	Creat_link.Link_List_Insert(3, 3);
	Creat_link.Link_List_Insert(4, 4);
	Creat_link.Link_List_Insert(5, 5);
	Creat_link.Display_Link_List();

	Creat_link.Link_List_Insert(3, 10);

	int length = Creat_link.Link_List_length();
	cout << "单链表长度为" << length << endl;

	Creat_link.Display_Link_List();
	Creat_link.rear();

	Creat_link.Reverse_Link_List();
	Creat_link.Display_Link_List();
	Creat_link.rear();



	Creat_link.Get_Link_List_Elem(3);
	Creat_link.Link_List_Empty();
	Creat_link.Locate_Link_List_Elem(1);

	Creat_link.Link_List_Delete(6);
	Creat_link.Display_Link_List();
	Creat_link.rear();

	_nmsp::Node<int>* node = Creat_link.Get_Link_List_point(4);
	Creat_link.Link_List_Prior_Insert_Node(1000, node);
	Creat_link.Display_Link_List();
	Creat_link.rear();
	cout << "hello world";
	return 0;


}