C++链表类及链表常用功能实现_c++用类实现链表

使用C++编写链表类，实现以下功能：

• 建立链表
• 删除链表
• 插入元素（链表尾部或者指定位置）
• 删除元素（指定位置）
• 查找第K个元素
• 查找某个元素值是否存在
• 逆序链表

为了使链表可以用于不同数据类型，因此使用了模板类。

1，节点类

链表的每个节点都是一个独立的单元，每个单元由数据和指向下一节点的指针构成

//定义链表节点
template <class T>
class Node
{
public:
	T data;
	Node<T>* next;
};
1
2
3
4
5
6
7
8

2，链表类

链表本身可以定义为类，但是节点却不能简单直接地作为其成员变量，因为链表含有的节点数量是可以变化的，甚至可以为空。

而且链表具有的特点就是可以根据第一个节点（或者它的地址）推出其他所有的节点，因此可以把第一个节点作为成员变量，但是考虑到链表可能为空，所以给链表手动添加一个Header，也是Node类型，这样也可以方便初始化。这里使用了Node的指针。

template <class T>
class LinkedList
{
public:
	LinkedList();//建立链表
	~LinkedList();//删除链表
	int getLength();//返回长度
	void print();//打印
	Node<T>* findKthNode(int k);//查找第K个元素
	void insert(int data, int position);// 插入元素
	void pushBack(int data);//添加元素
	void remove(int position);//删除元素
	bool findNode(int data);//查找元素是否存在
	void reverse();//逆序
private:
	Node<T>* head;//指向链表第一个元素的指针
	int length;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3，建立链表和删除链表直接使用类的构造函数和析构函数实现

代码如下：

template <class T>
LinkedList<T>::LinkedList()
{
	head = new Node<T>;
	head->next = NULL;
	head->data = 0;
	length = 0;
}
//删除链表
template <class T>
LinkedList<T>::~LinkedList()
{
	if (length == 0)
	{
		delete head;
		head = NULL;
		return;
	}
	Node<T>* p = head->next;
	delete head;
	head = NULL;
	while (p != NULL)
	{
		Node<T>* temp = p->next;
		delete p;
		p = temp;
	}
	delete p;
	length = 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

4, 逆序功能实现
逆序功能可以从前到后循环实现，每次取三个节点，将第二个节点的指针指向第一个节点。开头和结尾则需要另外处理。流程如下图：
其它功能比较简单，不再赘述。

完整代码如下：

#include <iostream>
#include <iomanip>
using namespace std;

//定义链表节点
template <class T>
class Node
{
public:
	T data;
	Node<T>* next;
};

template <class T>
class LinkedList
{
public:
	LinkedList();//建立链表
	~LinkedList();//删除链表
	int getLength();//返回长度
	void print();//打印
	Node<T>* findKthNode(int k);//查找第K个元素
	void insert(int data, int position);// 插入元素
	void pushBack(int data);//添加元素
	void remove(int position);//删除元素
	bool findNode(int data);//查找元素是否存在
	void reverse();//逆序
private:
	Node<T>* head;
	int length;
};

template <class T>
LinkedList<T>::LinkedList()
{
	head = new Node<T>;
	head->next = NULL;
	head->data = 0;
	length = 0;
}
//返回长度
template <class T>
int LinkedList<T>::getLength()
{
	return length;
}
//删除链表
template <class T>
LinkedList<T>::~LinkedList()
{
	if (length == 0)
	{
		delete head;
		head = NULL;
		return;
	}
	Node<T>* p = head->next;
	delete head;
	head = NULL;
	while (p != NULL)
	{
		Node<T>* temp = p->next;
		delete p;
		p = temp;
	}
	delete p;
	length = 0;
}
//
template <class T>
void LinkedList<T>::print()
{
	if (length == 0) return;
	Node<T>* temp = head->next;
	//cout << temp->data << " " << temp->next;
	cout << "Current list is:";
	for (int i = 0; i < length; i++)
	{
		cout << setw(4) << temp->data;
		temp = temp->next;
	}
	cout << endl << endl;
	temp = NULL;
}

template <class T>
Node<T>* LinkedList<T>::findKthNode(int k)
{
	Node<T>* temp;
	if (k > length)
	{
		cout << "K is out of range! " << endl;
		temp = new Node<T>;
		temp->data = NULL;
		temp->next = NULL;
	}
	else
	{
		temp = head;
		while (k--)
			temp = temp->next;
	}
		return temp;

}

template <class T>
void LinkedList<T>::insert(int data, int position)
{
	if (position > length + 1 || position < 1)
	{
		cout << "Position " << position << " is out of range! " << endl;
		cout << endl;
	}
	else if (position == length + 1)
	{
		pushBack(data);
	}
	else
	{
		//找到插入的位置
		Node<T>* pre = findKthNode(position - 1);
		Node<T>* cur = new Node<T>;
		cur->data = data;
		cur->next = pre->next;
		pre->next = cur;
		pre = cur = NULL;
		length++;
		cout << "Successfully insert " << data << " to position " << position << " !" << endl;

	}
	return;
}

template <class T>
void LinkedList<T>::pushBack(int data)
{
	Node<T>* cur = new Node<T>;
	cur->data = data;
	cur->next = NULL;
	Node<T>* temp = findKthNode(length);
	temp->next = cur;
	temp = NULL;
	cur = NULL;
	cout << "Successfully push back " << data << " to linked list! " << endl;
	length++;
}

template <class T>
void LinkedList<T>::remove(int position)
{
	if (position > length || position < 1)
	{
		cout << "Position " << position<< " is out of range! " << endl;
		cout << endl;
		return;
	}
	Node<T>* pre = findKthNode(position - 1);
	Node<T>* cur = pre->next;
	pre->next = cur->next;
	delete cur;
	cur = pre = NULL;
	length--;
	cout << "Successfully remove the node on position " << position << " !" << endl;
}

template <class T>
bool LinkedList<T>::findNode(int data)
{
	Node<T>* temp = head;
	bool isExist = 0;
	for (int i = 0; i < length; i++)
	{
		temp = temp->next;
		if (temp->data == data)
		{
			isExist = 1;
			cout << "Find " << data << " in position " << i << "." << endl;
		}
	}
	if (!isExist)
		cout << "Can not find " << data << " in current list." << endl;
	cout << endl;
	return isExist;
}


template <class T>
void LinkedList<T>::reverse()
{
	Node<T>* pre = head;
	Node<T>* cur = pre->next;
	Node<T>* next = cur->next;
	cur->next = NULL;
	for (int i = 0; i < length - 2; i++)
	{
		pre = cur;
		cur = next;
		next = next->next;
		cur->next = pre;
	}
	next->next = cur;
	head->next = next;
	pre = cur = next = NULL;
	cout << "Successfully reverse current list! " << endl;
}
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