数据结构之双向循环链表-指针实现

发表于 | 分类于

基础知识

双向循环链表和单向链表一样是一种线性表数据结构，但和单向链表不同，双向循环链表需要增加两个指针域分别指向前驱节点和后继节点，同时首尾节点分别指向彼此。双向链表的实现和单向链表相比稍微有点复杂，但是双向循环链表具有前向和后向遍历能力并且可以从任意节点开始循环遍历所有的节点。双向循环链表的指针域增加也造成了更多的空间浪费，使空间利用率进一步降低。

双向循环链表数据结构的定义

使用单向链表的ADT，采用C++模板的方式编写双向循环链表的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <typename DataType>
class Node
{
public:
	Node(DataType inData):data(inData), prior(nullptr), next(nullptr) {}
public:
	DataType data;
	Node *prior; /*前驱*/
	Node *next; /*后继*/
};

template <typename DataType>
class List
{
public:
	List(): listSize(0), head(nullptr) {}
	~List(); //析构函数，负责回收内存
	void MakeEmpty(); //清空链表
	bool IsEmpty(); //判断链表是否为空
	bool IsLast(Node<DataType> * inPosition); //判断是否为最后一个元素
	Node<DataType> *FindElement(DataType value); //查找一个元素并返回地址
	Node<DataType> *FindNthElement(int n); //查找第n个元素，返回地址或者nullptr
	void DeleteElement(DataType inData); //删除一个节点
	void DeleteNthElement(int n); //删除第n个节点
	void InsertElement(DataType inData, int n); //插入一个节点
	int Length(); //返回链表长度
private:
	int listSize; //保存链表长度
	Node<DataType> *head; /*只需头节点即可*/
};

如上所示，在链表类中有两个数据成员，分别为listSize和head。listSize保存当前链表大小，对一些函数可快速判断输入是否合法；head保存链表头节点，如果链表为空则置为空指针。

下面依次实现各函数：

  • 清空链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename DataType>
void List<DataType>::MakeEmpty()
{
	if (listSize <= 0 || head == nullptr) {
		return;
	}
	/*使首尾断开连接，便于终止条件判断*/
	head->prior->next = nullptr;

	Node<DataType> * tmp = head;
	while (tmp != nullptr) {
		head = head->next;
		delete tmp;
		tmp = head;
	}
	listSize = 0; head = nullptr;
	return;
}
  • 判断列表是否为空
1
2
3
4
5
6
7
8
template <typename DataType>
bool List<DataType>::IsEmpty()
{
	if (listSize <= 0 || head == nullptr) {
		return true;
	}
	return false;
}
  • 判断是否为最后一个元素
1
2
3
4
5
template <typename DataType>
bool List<DataType>::IsLast(Node<DataType> * inPosition)
{
	return inPosition != nullptr && inPosition == head->prior;
}
  • 查找一个元素并返回地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename DataType>
Node<DataType> * List<DataType>::FindElement(DataType value)
{
	Node<DataType> *cycleIter = head;
	while (cycleIter != nullptr) {
		if (cycleIter->data == value) {
			return cycleIter;
		}
		cycleIter = cycleIter->next;
		if (cycleIter == head) {
			break; /*回到头节点了*/
		}
	}
	return nullptr;
}
  • 查找第n个元素，下标从1开始，返回地址或者nullptr
1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename DataType>
Node<DataType> * List<DataType>::FindNthElement(int n)
{
	if (n <= 0 || n > listSize) {
		/*超过大小直接返回nullptr防止回绕*/
		return nullptr;
	}
	Node<DataType> *cycleIter = head;
	while (--n > 0 && cycleIter != nullptr) {
		cycleIter = cycleIter->next;
	}
	return cycleIter;
}
  • 删除一个节点，如果不存在则不做任何事
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename DataType>
void List<DataType>::DeleteElement(DataType inData)
{
	Node<DataType> *cycleIter = head;
	while (cycleIter != nullptr) {
		if (cycleIter->data == inData) {
			/*注意处理只有一个节点和删除头节点的问题*/
			if (cycleIter == head) {
				head = head->next != head ? head->next : nullptr;
			}
			Node<DataType> * tmp = cycleIter;
			tmp->prior->next = tmp->next;
			tmp->next->prior = tmp->prior;
			delete tmp; --listSize;
			return;
		}
		cycleIter = cycleIter->next;
	}
	return;
}
  • 删除第n个节点，如果不存在则不做任何事
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename DataType>
void List<DataType>::DeleteNthElement(int n)
{
	if (n <= 0 || n > listSize) {
		return;
	}
	Node<DataType> *cycleIter = head;
	while (--n > 0 && cycleIter != nullptr) {
		cycleIter = cycleIter->next;
	}
	if (n <= 0) {
		Node<DataType> * tmp = cycleIter;
		tmp->prior->next = tmp->next;
		tmp->next->prior = tmp->prior;
		delete tmp; --listSize;
	}
	return;
}
  • 插入一个节点, n<0或者>链表长度代表直接插到末尾，其他代表插到第n个节点后

如果只有一个节点将该节点的首尾均指向自己。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template <typename DataType>
void List<DataType>::InsertElement(DataType inData, int n)
{
	Node<DataType> *insertElement = new Node<DataType>(inData);
	if (head == nullptr || listSize <= 0) {
		head = insertElement;
		head->next = head;
		head->prior = head; ++listSize;
	}
	else {
		if (n < 0 || n >= listSize) {
			head->prior->next = insertElement;
			insertElement->prior = head->prior;
			insertElement->next = head;
			head->prior = insertElement; ++listSize;
		}
		else {
			Node<DataType> *cycleIter = head;
			while (--n > 0 && cycleIter != nullptr) {
				cycleIter = cycleIter->next;
			}
			if (n <= 0) {
				insertElement->next = cycleIter->next;
				insertElement->prior = cycleIter;
				cycleIter->next->prior = insertElement;
				cycleIter->next = insertElement; ++listSize;
			}
		}
	}
	return;
}
  • 返回链表长度
1
2
3
4
5
template <typename DataType>
int List<DataType>::Length()
{
	return listSize;
}
  • 析构函数
1
2
3
4
5
template <typename DataType>
List<DataType>::~List()
{
	MakeEmpty();
}

代码测试

以下对上述代码进行简单的测试，测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;

int main()
{
        List<int> Test;
        Test.InsertElement(9, 1);
        Test.InsertElement(10, 3);

        cout << Test.IsEmpty() << endl;

        Test.InsertElement(12, 1);
        Test.InsertElement(14, 3);

        cout << Test.Length() << endl;

        Test.DeleteElement(10);
        Test.DeleteElement(9);
        Test.DeleteElement(14);
        Test.DeleteElement(12);

        cout << Test.IsEmpty() << endl;

        cout << Test.Length() << endl;

        Test.InsertElement(9, 1);
        Test.InsertElement(10, 3);
        Test.InsertElement(12, 1);
        Test.InsertElement(14, 3);
        Test.MakeEmpty();

        Test.InsertElement(9, 1);
        Test.InsertElement(10, 3);
        Test.InsertElement(12, 1);
        Test.InsertElement(14, 3);

        Node<int> * pTest = Test.FindElement(12);
        pTest = Test.FindElement(9);
	pTest = Test.FindElement(-1);

        pTest = Test.FindNthElement(4);
        pTest = Test.FindNthElement(-1);
        pTest = Test.FindNthElement(1);
        pTest = Test.FindNthElement(10);

        return 0;
}

参考文章

数据结构与算法分析