C++实现双向链表_c++ getprev

C++ 实现双向链表

简介

功能：实现环形链表

工程环境：CMake

文件目录介绍：

• 结点类 Node 位于 LinkedList/Node.hpp
• 链表类 LinkedList 位于 LinkedList/LinkedList.hpp
• CMakeProject_2_List.cpp 用于测试

双向链表简介

该项目实现的双向链表示意图如下

每一个结点都由四个部分组成（这里只画出了三个），包括：数据、next 指针、prev 指针以及结点类型。

• next 指针用来指向下一个结点，prev 指针用来指向前一个结点；
• 结点类型包括：头部结点类型（HEAD）、尾部结点类型（TAIL）、普通结点类型（NORMAL），头部结点就是头部结点类型，尾部结点就是尾部结点类型，其他结点就是普通结点类型。这样做是为了方便区分头尾结点和其他结点（节点类型定义为枚举类）。

初始状态有一个头部结点和尾部结点，即 head 和 tail，这两个结点中没有数据，只有 prev 指针和 next 指针。头部结点和尾部结点虽然在链表中，但是不计入总长度（因为这不是使用者创建的，而是编码者创建的）。即初始状态时链表长度为 0，当且仅当使用者添加结点后，长度才会大于 0。

初始状态时 head->next 指向 tail，tail->prev 指向 head；head->prev 指向 tail，tail->next 指向 head。

对于链表的增删操作，具体如下：

添加结点时，分为尾部添加和头部添加两种，设新添加的结点为 newNode：

• 尾部添加：先获取最后一个结点 latestNode，将 newNode 的 prev 指向 latestNode，将 newNode 的 next 指向 tail；将 latestNode 的 next 指向 newNode，将 tail 的 prev 指向 newNode。
• 头部添加：先获取第一个结点 firstNode，将 newNode 的 next 指向 firstNode，将 newNode 的 prev 指向 head；将 firstNode 的 prev 指向 newNode，将 head 的 next 指向 newNode。
• 一定要注意设置指针指向的顺序，因为 latestNode 是通过 tail->prev 获取的，firstNode 是通过 head->next 获取的。如果在此之前就设置了“将 tail 的 prev 指向 newNode”或“将 head 的 next 指向 newNode”的话，我们获取到的就不是真正的 latestNode 和 firstNode 了。

删除结点时，先锁定要删除的结点，设为 node，然后将 node->prev 的 next 指向 node->next，将 node->next 的 prev 指向 node->prev，这样 node 就被剥离下来了，达到了删除的效果

对于链表的迭代，主要有 hasNext,hasPrev 和 next,prev 操作：

• hasNext 判断是否有下一个结点（首尾节点不算），只需要判断当前节点的下一个结点类型是否为 NORMAL
• hasPrev 判断是否有删一个结点（首尾节点不算），只需要判断当前节点的上一个结点类型是否为 NORMAL
• next 是当前指针指向下一个结点
• prev 是当前指针指向上一个结点

代码

设计时考虑到可扩展性，节点类和链表类都是模板类（因此后缀需要是 .hpp）

项目地址：数据结构 链表 gitee

节点类

#pragma once

#include <iostream>

using namespace std;

#define NULL 0


enum NodeType
{
	HEAD,
	TAIL,
	NORMAL
};

template<typename D>
class Node
{
public:
	Node(NodeType nodeType, D data) {
		setNodeType(nodeType);
		setData(data);
		prev = NULL;
		next = NULL;
	};
	Node(NodeType nodeType, D data, Node* prev, Node* next) {
		setNodeType(nodeType);
		setData(data);
		setPrev(prev);
		setNext(next);
	};
	~Node() {}

	D getData() { return data; }
	void setData(D data) { this->data = data; }
	Node* getPrev() { return prev; }
	void setPrev(Node* prev) { this->prev = prev; }
	Node* getNext() { return next; }
	void setNext(Node* next) { this->next = next; }
	NodeType getNodeType() { return nodeType; }
	void setNodeType(NodeType nodeType) { this->nodeType = nodeType; }

	void printString() {
		cout << "Node {" << endl;
		cout << "\tNodeType : " << reflectNodeType(nodeType) << endl;
		cout << "\tdata = " << data << endl;
		cout << "\tprev = " << prev->getData() << endl;
		cout << "\tnext = " << next->getData() << endl;
		cout << "}" << endl;
	}

	void printLine() {
		cout << "Node {";
		cout << " NodeType : " << reflectNodeType(nodeType);
		cout << " data = " << data;
		cout << " prev = " << prev->getData();
		cout << " next = " << next->getData();
		cout << " }" << endl;
	}

private:
	Node* prev;
	Node* next;
	D data;
	NodeType nodeType;

	string reflectNodeType(NodeType nodeType) {
		switch (nodeType)
		{
		case HEAD:
			return "HEAD";
			break;
		case TAIL:
			return "TAIL";
			break;
		case NORMAL:
			return "NORMAL";
			break;
		default:
			return "NULL";
			break;
		}
	}
};

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

链表类

#pragma once
#include "Node.hpp"

using namespace std;

/**
 * @brief 链表，双向环形，初始时有首尾定位结点（不纳入总结点计数），模型为：head-->结点-->tail-->head.
 */
template<typename T>
class LinkedList
{
public:
	LinkedList() {
		head = new Node<T>(HEAD, 0);
		tail = new Node<T>(TAIL, 0);
		head->setNext(tail);
		head->setPrev(tail);
		tail->setNext(head);
		tail->setPrev(head);
		size = 0;
		node = head;
	}
	~LinkedList() {};


	void addToTail(Node<T>* node);
	void addToTail(T data);
	void addToHead(Node<T>* node);
	void addToHead(T data);

	void remove(Node<T>* node);
	void remove(T data);

	Node<T>* selectFirstNode(T data);
	Node<T>* get(int index);

	Node<T>* getLastNode() { if (size > 0) return tail->getPrev(); else return head; }
	Node<T>* getFirstNode() { if (size > 0) return head->getNext(); else return head; }


	Node<T>* getHead() { return head; }
	Node<T>* getTail() { return tail; }
	int getSize() { return size; }


	void printString() {
		cout << "LinkedList (size = " << size << ") {" << endl;
		cout << "   head ";
		head->printLine();
		while (hasNext())
		{
			cout << "-> node ";
			next()->printLine();
		}
		cout << "-> tail ";
		tail->printLine();
		cout << "}" << endl;
	}
public:
	// 该部分迭代用

	bool hasNext() { return node->getNext()->getNodeType() == NORMAL; };
	bool hasPrev() { return node->getPrev()->getNodeType() == NORMAL; };
	Node<T>* next() {
		node = node->getNext();
		return node;
	}
	Node<T>* prev() {
		node = node->getPrev();
		return node;
	}
private:
	Node<T>* head;
	Node<T>* tail;
	int size;

	/* 当前节点指针 */
	Node<T>* node;
};


/**
 * @brief 尾部添加结点.
 * @param node 结点
 */
template <typename T>
void LinkedList<T>::addToTail(Node<T>* node)
{
	node->setNext(tail);
	node->setPrev(getLastNode());
	getLastNode()->setNext(node);
	tail->setPrev(node);
	//node->printLine();
	size++;
}

/**
 * @brief 尾部添加节点.
 * @param 结点对应的数据
 */
template <typename T>
void LinkedList<T>::addToTail(T data)
{
	Node<T>* node = new Node(NORMAL, data, getLastNode(), tail);
	getLastNode()->setNext(node);
	tail->setPrev(node);
	//node->printLine();
	size++;
}

/**
 * @brief 头部添加结点.
 * @param node 结点
 */
template<typename T>
void LinkedList<T>::addToHead(Node<T>* node)
{
	node->setPrev(tail);
	node->setnext(getFirstNode());
	getFirstNode()->setPrev(node);
	head->setNext(node);
	//node->printLine();
	size++;
}

/**
 * @brief 头部添加节点.
 * @param 结点对应的数据
 */
template<typename T>
void LinkedList<T>::addToHead(T data)
{
	Node<T>* node = new Node(NORMAL, data, head, getFirstNode());
	getFirstNode()->setPrev(node);
	head->setNext(node);
	//node->printLine();
	size++;
}

/**
 * @brief 移除 node 结点.
 * @param node 结点
 */
template<typename T>
void LinkedList<T>::remove(Node<T>* node) {
	remove(node->getData());
}

/**
 * @brief 移除数据为 data 结点.
 * @param data 节点数据
 */
template<typename T>
void LinkedList<T>::remove(T data) {
	node = head;
	if (size > 0)
	{
		while (hasNext())
		{
			if (next()->getData() == data)
			{
				node->getPrev()->setNext(node->getNext());
				node->getNext()->setPrev(node->getPrev());
				node = head;
				size--;
				return;
			}
			else continue;
		}
		return;
	}
	else return;
}

/**
  * @brief 找到第一个值为 data 的结点，要求 data 的类必须可以被比较，如果是自定义类，建议重载 == 运算符. 如果链表没有结点，则只返回头部结点；如果找不到，就返回尾部结点
  * @return Node<T>*
  */
template<typename T>
Node<T>* LinkedList<T>::selectFirstNode(T data)
{
	node = head;
	if (size > 0)
	{
		while (hasNext())
		{
			if (next()->getData() == data) return node;
			else continue;
		}
		return tail;
	}
	else return head;
}

/**
 * @brief 根据索引所在位置找到对应的结点，0 代表 head，size + 1 代表 tail，其余的代表中间结点. 如果链表没有结点，则只返回头部节点
 * @return Node<T>*
 */
template<typename T>
Node<T>* LinkedList<T>::get(int index)
{
	node = head;
	if (size > 0 || index <= 0)
	{
		if (index > size) return tail;
		else
		{
			int count = 0;
			while (count < index)
			{
				next();
				count++;
			}
			return node;
		}

	}
	else return head;
}

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220

测试

#include "CMakeProject_2_List.h"

using namespace std;

void testNode();
void testLinkedList();

int main()
{
	/* Node test */
	/* head->node->tail->head */

	testLinkedList();
	//cout << "Hello CMake." << endl;
	return 0;
}

void testNode() {
	/* Node test */
	/* head->node->tail->head */

	Node<int>* head = new Node(HEAD, 0);
	Node<int>* tail = new Node(TAIL, 0);
	Node<int>* node = new Node(NORMAL, 1, head, tail);
	head->setNext(node);
	head->setPrev(tail);
	tail->setNext(head);
	tail->setPrev(node);

	/* test success ! */

	node->printString();

	node->~Node();
}

void testLinkedList() {
	LinkedList<int>* linkedList1 = new LinkedList<int>();
	LinkedList<int>* linkedList2 = new LinkedList<int>();
	for (int i = 0; i < 10; i++)
	{
		linkedList1->addToTail(i + 1);
		linkedList2->addToHead(i + 1);
	}
	cout << "linkedlist1" << endl;
	linkedList1->printString();
	linkedList1->getHead()->printString();
	linkedList1->getTail()->printString();

	cout << endl << endl;
	cout << "linkedlist2" << endl;
	linkedList2->printString();
	linkedList2->getHead()->printString();
	linkedList2->getTail()->printString();

	cout << endl << endl;
	cout << "node1" << endl;
	Node<int>* node1 = linkedList1->get(4);
	node1->printString();

	cout << endl << endl;
	cout << "node2" << endl;
	Node<int>* node2 = linkedList1->selectFirstNode(5);
	node2->printString();

	cout << endl << endl;
	cout << "remove node 1" << endl;
	linkedList1->remove(node1);
	linkedList1->printString();
}

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

测试结果

linkedlist1
LinkedList (size = 10) {
   head Node { NodeType : HEAD data = 0 prev = 0 next = 1 }
-> node Node { NodeType : NORMAL data = 1 prev = 0 next = 2 }
-> node Node { NodeType : NORMAL data = 2 prev = 1 next = 3 }
-> node Node { NodeType : NORMAL data = 3 prev = 2 next = 4 }
-> node Node { NodeType : NORMAL data = 4 prev = 3 next = 5 }
-> node Node { NodeType : NORMAL data = 5 prev = 4 next = 6 }
-> node Node { NodeType : NORMAL data = 6 prev = 5 next = 7 }
-> node Node { NodeType : NORMAL data = 7 prev = 6 next = 8 }
-> node Node { NodeType : NORMAL data = 8 prev = 7 next = 9 }
-> node Node { NodeType : NORMAL data = 9 prev = 8 next = 10 }
-> node Node { NodeType : NORMAL data = 10 prev = 9 next = 0 }
-> tail Node { NodeType : TAIL data = 0 prev = 10 next = 0 }
}
Node {
        NodeType : HEAD
        data = 0
        prev = 0
        next = 1
}
Node {
        NodeType : TAIL
        data = 0
        prev = 10
        next = 0
}


linkedlist2
LinkedList (size = 10) {
   head Node { NodeType : HEAD data = 0 prev = 1 next = 10 }
-> node Node { NodeType : NORMAL data = 10 prev = 0 next = 9 }
-> node Node { NodeType : NORMAL data = 9 prev = 10 next = 8 }
-> node Node { NodeType : NORMAL data = 8 prev = 9 next = 7 }
-> node Node { NodeType : NORMAL data = 7 prev = 8 next = 6 }
-> node Node { NodeType : NORMAL data = 6 prev = 7 next = 5 }
-> node Node { NodeType : NORMAL data = 5 prev = 6 next = 4 }
-> node Node { NodeType : NORMAL data = 4 prev = 5 next = 3 }
-> node Node { NodeType : NORMAL data = 3 prev = 4 next = 2 }
-> node Node { NodeType : NORMAL data = 2 prev = 3 next = 1 }
-> node Node { NodeType : NORMAL data = 1 prev = 2 next = 0 }
-> tail Node { NodeType : TAIL data = 0 prev = 0 next = 0 }
}
Node {
        NodeType : HEAD
        data = 0
        prev = 1
        next = 10
}
Node {
        NodeType : TAIL
        data = 0
        prev = 0
        next = 0
}


node1
Node {
        NodeType : NORMAL
        data = 4
        prev = 3
        next = 5
}


node2
Node {
        NodeType : NORMAL
        data = 5
        prev = 4
        next = 6
}


remove node 1
LinkedList (size = 9) {
   head Node { NodeType : HEAD data = 0 prev = 0 next = 1 }
-> node Node { NodeType : NORMAL data = 1 prev = 0 next = 2 }
-> node Node { NodeType : NORMAL data = 2 prev = 1 next = 3 }
-> node Node { NodeType : NORMAL data = 3 prev = 2 next = 5 }
-> node Node { NodeType : NORMAL data = 5 prev = 3 next = 6 }
-> node Node { NodeType : NORMAL data = 6 prev = 5 next = 7 }
-> node Node { NodeType : NORMAL data = 7 prev = 6 next = 8 }
-> node Node { NodeType : NORMAL data = 8 prev = 7 next = 9 }
-> node Node { NodeType : NORMAL data = 9 prev = 8 next = 10 }
-> node Node { NodeType : NORMAL data = 10 prev = 9 next = 0 }
-> tail Node { NodeType : TAIL data = 0 prev = 10 next = 0 }
}

N:\ANotes\计算机\数据结构\Code\CMakeProject_2_List\out\build\x64-debug\CMakeProject_2_List\CMakeProject_2_List.exe (进程 10392)已退出，代码为 0。
按任意键关闭此窗口. . .
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93