双链表的实现（c++）

什么是双链表

• 单链表的缺点
  • 如果要寻找单链表中某个已知结点的前趋结点会比较繁琐，必须去从链表头出发开始寻找，这样也就导致算法的平均情况时间复杂度O（n）。
• 在单链表的基础上，增加一个用于指向前趋节点的指针。也就是说双链表是由单链表衍生出来的链表结构。
• 双链表的结点中有两个指针prior和next，分别指向前驱结点和后继结点。

---

双链表的数据成员

• 一个结点包含一个数据域和两个指针域（前趋指针，后继指针）
• 前趋指针指向该节点的前一个结点
• 后继指针指向该结点的后一个结点（尾结点除外，尾结点的后继指针next为nullptr

//双链表中每个结点的定义
	template<typename T>
	struct Double_Node
	{
		T data;
		Double_Node<T>* prior;
		Double_Node<T>* next;

	};

双链表的基本操作

• 双链表的类的定义和成员函数方法的设计

  • 构造函数
  • 析构函数
  • 在第i个位置插入结点
  • 删除第i个位置的元素
  • 获取第i个位置的元素
  • 获取值为e的在链表中第一次出现的位置
  • 遍历输出所有元素
  • 获取双链表的长度
  • 判断链表是否为空

  ---

双链表的编程实现

双链表类的定义

• 和单链表类似

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

	public:
		bool Double_Link_List_insert(int i, const T& e);	//在第i个位置插入
		bool Double_Link_List_delete(int i);			//删除第i个位置

		bool Get_Elem(int i, T& e);						//获取第i个位置的元素
		int Locate_Elem(const T& e);					//获取值为e的第一个出现的位置

		void Display_Double_Link_List();				//遍历输出所有元素
		int Double_Link_List_length();					//获取双链表的长度
		bool Empty();									//判断链表是否为空

	private:
		Double_Node<T>* m_head;							//头结点
		int m_length;									//表长
	};

---

构造函数并且进行初始化

• 头结点的前趋指针永远为空

//构造函数进行初始化
	template<typename T>
	Double_Link_List<T>::Double_Link_List()
	{
		m_head = new Double_Node<T>;
		m_head->next = nullptr;
		m_head->prior = nullptr;		//头结点永远为空
		m_length = 0;

	}

---

在第i个位置插入结点

• 首先判断位置i是否合法
• 遍历结点找到插入位置i的前一个位置
• 进行插入结点顺序如图所示

• 表长更新

template<typename T>
	bool Double_Link_List<T>::Double_Link_List_insert(int i, const T& e)
	{
		//判断插入位置i是否合法，i的合法值应该是1到length+1之间
		if (i < 1 || i >(m_length + 1))
		{
			cout << "元素" << e << "插入的位置" << i << "不合法，合法的位置是1到" << m_length + 1 << "之间!" << endl;
			return false;
		}

		Double_Node<T>* p_curr = m_head;		//用于找到定位应插入的位置的前一个位置

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

		Double_Node<T>* node = new Double_Node<T>;
		node->data = e;
		node->next = p_curr->next;
		node->prior = p_curr;

		// 如果插入的位置是尾结点，就没有后续结点的前趋指针指向新结点，故跳过；
		if (p_curr->next != nullptr)
		{
			p_curr->next->prior = node;

		}
		p_curr->next = node;
		cout << "成功在位置为" << i << "处插入元素" << e << "!" << endl;
		m_length++;
		return true;

	}

---

删除第i个位置的元素

• 判断表长是否为空
• 判断位置i是否合法
• 找到删除结点的前一个结点
• 进行删除结点顺序如图所示

• 更新表长

//删除第i个位置的元素
	template<typename T>
	bool Double_Link_List<T>::Double_Link_List_delete(int i)
	{
		if (m_length < 1)
		{
			cout << "当前双链表为空，不能删除任何数据!" << endl;
			return false;
		}
		if (i < 1 || i > m_length)
		{
			cout << "删除的位置" << i << "不合法，合法的位置是1到" << m_length << "之间!" << endl;
			return false;
		}

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

		Double_Node<T>* will_delete = p_curr->next				//记录将要删除的结点
		Double_Node<T>* will_delete_Next = will_delete->next;	//记录删除结点的下一个位置
		p_curr->next = will_delete->next;
		if (will_delete_Next != nullptr)						//删除结点是尾结点故跳过
		{
			will_delete_Next->prior = p_curr;
		}

		cout << "成功删除位置为" << i << "的元素，该元素的值为" << will_delete->data << "!" << endl;
		m_length--;       //实际表长-1
		delete will_delete;
		return true;
	}

---

获得第i个位置的元素值

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

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

		Double_Node<T>* p_curr = m_head;
		for (int j = 0; j < i; ++j)
		{
			p_curr = p_curr->next;
		}
		e = p_curr->data;
		cout << "成功获取位置为" << i << "的元素，该元素的值为" << e << "!" << endl;
		return true;
	}

---

按元素值查找其在双链表中第一次出现的位置

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

---

获取双链表的长度

//获取双链表的长度，时间复杂度为O(1)
	template<class T>
	int  Double_Link_List<T>::Double_Link_List_length()
	{
		return m_length;
	}

---

判断双链表是否为空

//判断双链表是否为空，时间复杂度为O(1)
	template<class T>
	bool Double_Link_List<T>::Empty()
	{
		if (m_head->next == nullptr) //双链表为空（如果是不带头结点的双链表则用if(m_head == nullptr）来判断是否为空）
		{
			return true;
		}
		return false;
	}

---

遍历输出所有元素

template<typename T>
	void Double_Link_List<T>::Display_Double_Link_List()
	{
		Double_Node<T>* p = m_head->next;
		while (p != nullptr) //这里采用while循环或者for循环书写都可以
		{
			cout << p->data << " ";  //每个数据之间以空格分隔
			p = p->next;
		}
		cout << endl; //换行
	}

---

析构函数

//通过析构函数对双链表进行资源释放
	template <typename T>
	Double_Link_List<T>::~Double_Link_List()
	{
		Double_Node<T>* pnode = m_head->next;
		Double_Node<T>* ptmp;
		while (pnode != nullptr)	//该循环负责释放数据节点
		{
			ptmp = pnode;
			pnode = pnode->next;
			delete ptmp;
		}
		delete m_head;    //释放头结点
		m_head = nullptr; //非必须
		m_length = 0;     //非必须

	}

总结

• 在单链表中，如果已知结点的情况下，寻找后继结点的时间复杂度O(1)，如果想要找前趋结点就必须从链表头开始往后遍历，所以最坏情况时间复杂度O(n)；双链表具有前趋指针，找到已知结点的前面一个结点的时间复杂度为O（1），大大提高了寻找效率；
• 双链表的某结点p的前趋结点的后继指针以及后继结点的前趋指针代表的都是p结点本身
• 因双链表添加了前趋指针，要额外消耗存储空间。

全部代码

#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 Double_Node
	{
		T data;
		Double_Node<T>* prior;
		Double_Node<T>* next;

	};

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

	public:
		bool Double_Link_List_insert(int i, const T& e);	//在第i个位置插入
		bool Double_Link_List_delete(int i);			//删除第i个位置

		bool Get_Elem(int i, T& e);						//获取第i个位置的元素
		int Locate_Elem(const T& e);					//获取值为e的第一个出现的位置

		void Display_Double_Link_List();				//遍历输出所有元素
		int Double_Link_List_length();					//获取双链表的长度
		bool Empty();									//判断链表是否为空

	private:
		Double_Node<T>* m_head;
		int m_length;
	};

	//构造函数进行初始化
	template<typename T>
	Double_Link_List<T>::Double_Link_List()
	{
		m_head = new Double_Node<T>;
		m_head->next = nullptr;
		m_head->prior = nullptr;
		m_length = 0;

	}

	template<typename T>
	bool Double_Link_List<T>::Double_Link_List_insert(int i, const T& e)
	{
		//判断插入位置i是否合法，i的合法值应该是1到length+1之间
		if (i < 1 || i >(m_length + 1))
		{
			cout << "元素" << e << "插入的位置" << i << "不合法，合法的位置是1到" << m_length + 1 << "之间!" << endl;
			return false;
		}

		Double_Node<T>* p_curr = m_head;		//用于找到定位应插入的位置的前一个位置

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

		Double_Node<T>* node = new Double_Node<T>;
		node->data = e;
		node->next = p_curr->next;
		node->prior = p_curr;

		// 如果插入的位置是尾结点，就没有后续结点的前趋指针指向新结点，故跳过；
		if (p_curr->next != nullptr)
		{
			p_curr->next->prior = node;

		}
		p_curr->next = node;
		cout << "成功在位置为" << i << "处插入元素" << e << "!" << endl;
		m_length++;
		return true;

	}



	//删除第i个位置的元素
	template<typename T>
	bool Double_Link_List<T>::Double_Link_List_delete(int i)
	{
		if (m_length < 1)
		{
			cout << "当前双链表为空，不能删除任何数据!" << endl;
			return false;
		}
		if (i < 1 || i > m_length)
		{
			cout << "删除的位置" << i << "不合法，合法的位置是1到" << m_length << "之间!" << endl;
			return false;
		}

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

		Double_Node<T>* will_delete = p_curr->next				//记录将要删除的结点
		Double_Node<T>* will_delete_Next = will_delete->next;	//记录删除结点的下一个位置
		p_curr->next = will_delete->next;
		if (will_delete_Next != nullptr)						//删除结点是尾结点故跳过
		{
			will_delete_Next->prior = p_curr;
		}

		cout << "成功删除位置为" << i << "的元素，该元素的值为" << will_delete->data << "!" << endl;
		m_length--;       //实际表长-1
		delete will_delete;
		return true;
	}

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

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

		Double_Node<T>* p_curr = m_head;
		for (int j = 0; j < i; ++j)
		{
			p_curr = p_curr->next;
		}
		e = p_curr->data;
		cout << "成功获取位置为" << i << "的元素，该元素的值为" << e << "!" << endl;
		return true;
	}

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


	//获取双链表的长度，时间复杂度为O(1)
	template<class T>
	int  Double_Link_List<T>::Double_Link_List_length()
	{
		return m_length;
	}

	//判断双链表是否为空，时间复杂度为O(1)
	template<class T>
	bool Double_Link_List<T>::Empty()
	{
		if (m_head->next == nullptr) //双链表为空（如果是不带头结点的双链表则用if(m_head == nullptr）来判断是否为空）
		{
			return true;
		}
		return false;
	}


	//通过析构函数对双链表进行资源释放
	template <typename T>
	Double_Link_List<T>::~Double_Link_List()
	{
		Double_Node<T>* pnode = m_head->next;
		Double_Node<T>* ptmp;
		while (pnode != nullptr)	//该循环负责释放数据节点
		{
			ptmp = pnode;
			pnode = pnode->next;
			delete ptmp;
		}
		delete m_head;    //释放头结点
		m_head = nullptr; //非必须
		m_length = 0;     //非必须

	}

	template<typename T>
	void Double_Link_List<T>::Display_Double_Link_List()
	{
		Double_Node<T>* p = m_head->next;
		while (p != nullptr) //这里采用while循环或者for循环书写都可以
		{
			cout << p->data << " ";  //每个数据之间以空格分隔
			p = p->next;
		}
		cout << endl; //换行
	}
}

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
	_nmsp::Double_Link_List<int> Creat_D_L_List;
	Creat_D_L_List.Double_Link_List_insert(1, 1);
	Creat_D_L_List.Double_Link_List_insert(2, 2);
	Creat_D_L_List.Double_Link_List_insert(3, 3);
	Creat_D_L_List.Display_Double_Link_List();
	Creat_D_L_List.Double_Link_List_length();

	Creat_D_L_List.Double_Link_List_delete(1);
	Creat_D_L_List.Display_Double_Link_List();
	return 0;
}