数据结构之单向链表-指针实现

发表于 | 分类于

基础知识

链表是一种线性表数据结构，其和顺序表的最大区别是链表在内存中无需连续存储，因此链表节点需要增加指针域（对于无指针的编程语言可能需要通过游标实现）用来指向下一个元素的内存地址。单向链表是链表的一种，其特点是链表的链接方向是单向的，访问单向链表的全部元素必须从头部开始依次访问。在单向链表的实现中，为了便于对表头元素进行插入、删除等操作，一般定义一个表头(header)或者称为哑节点(dummy node)，且默认表头在位置0处。在单向链表ADT中，一般至少需要需要实现以下操作：

  • 清空整个链表：MakeEmpty
  • 查找某个元素：FindElement
  • 删除一个元素：DeleteElement
  • 插入一个元素：InsertElement

在C++标准模板库(STL)中，list实现了一种双向链表。

单向链表数据结构的定义

仿照《数据结构与算法分析-C语言描述》一书中定义的格式，不过采用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),next(nullptr) {}
public:
	DataType data;
	Node *next;
};

template <typename DataType>
class List
{
public:
	List(DataType inDummy):dummyNode(inDummy), listSize(0), lastNode(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:
	Node<DataType> dummyNode; //哑节点
	int listSize; //保存链表长度
	Node<DataType> *lastNode; //保存最后一个节点地址
};

如上所示，在链表类中有三个数据成员，分别为dummyNode、listSize和lastNode。dummyNode是哑节点，不动态创建；listSize保存当前链表大小，对一些函数可快速判断输入是否合法；lastNode保存最后一个节点的地址。

下面依次实现各函数：

  • 清空链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename DataType>
void List<DataType>::MakeEmpty()
{
	if (listSize <= 0 || dummyNode.next == nullptr) {
		return;
	}
	Node<DataType> * tmp = nullptr;
	while (dummyNode.next != nullptr) {
		tmp = dummyNode.next;
		dummyNode.next = dummyNode.next->next;
		delete tmp;
	}
	listSize = 0; lastNode = nullptr;
	return;
}
  • 判断列表是否为空
1
2
3
4
5
6
7
8
template <typename DataType>
bool List<DataType>::IsEmpty()
{
	if (listSize <= 0 || dummyNode.next == nullptr) {
		return true;
	}
	return false;
}
  • 判断是否为最后一个元素
1
2
3
4
5
template <typename DataType>
bool List<DataType>::IsLast(Node<DataType> * inPosition)
{
	return inPosition != nullptr && inPosition == lastNode;
}
  • 查找一个元素并返回地址
1
2
3
4
5
6
7
8
9
10
11
12
template <typename DataType>
Node<DataType> * List<DataType>::FindElement(DataType value)
{
	Node<DataType> *cycleIter = dummyNode.next;
	while (cycleIter != nullptr) {
		if (cycleIter->data == value) {
			return cycleIter;
		}
		cycleIter = cycleIter->next;
	}
	return nullptr;
}
  • 查找第n个元素，dummy为第0个元素，返回地址或者nullptr
1
2
3
4
5
6
7
8
9
10
11
12
template <typename DataType>
Node<DataType> * List<DataType>::FindNthElement(int n)
{
	if (n <= 0) {
		return nullptr;
	}
	Node<DataType> *cycleIter = dummyNode.next;
	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
21
template <typename DataType>
void List<DataType>::DeleteElement(DataType inData)
{
	Node<DataType> *frontIter = &dummyNode;
	Node<DataType> *cycleIter = frontIter->next;
	while (cycleIter != nullptr) {
		if (cycleIter->data == inData) {
			Node<DataType> * tmp = cycleIter;
			frontIter->next = cycleIter->next;
			lastNode = lastNode == tmp ? frontIter : lastNode;
			delete tmp; --listSize;
			return;
		}
		frontIter = frontIter->next;
		cycleIter = cycleIter->next;
	}
	if (dummyNode.next == nullptr) {
		lastNode = nullptr;
	}
	return;
}
  • 删除第n个节点，如果不存在则不做任何事
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename DataType>
void List<DataType>::DeleteNthElement(int n)
{
	if (n <= 0 || n > listSize) {
		return;
	}
	Node<DataType> *frontIter = &dummyNode;
	Node<DataType> *cycleIter = frontIter->next;
	while (--n > 0 && cycleIter != nullptr) {
		frontIter = frontIter->next;
		cycleIter = cycleIter->next;
	}
	if (n <= 0) {
		Node<DataType> * tmp = cycleIter;
		frontIter->next = cycleIter->next;
		lastNode = lastNode == tmp ? frontIter : lastNode;
		delete tmp; --listSize;
	}
	if (dummyNode.next == nullptr) {
		lastNode = nullptr;
	}
	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
template <typename DataType>
void List<DataType>::InsertElement(DataType inData, int n)
{
	Node<DataType> *insertElement = new Node<DataType>(inData);
	if (n < 0 || n >= listSize) {
		if (lastNode == nullptr) {
			lastNode = &dummyNode;
		}
		lastNode->next = insertElement;
		lastNode = insertElement; ++listSize;
		return;
	}
	Node<DataType> *cycleIter = &dummyNode;
	while (n-- > 0 && cycleIter != nullptr) {
		cycleIter = cycleIter->next;
	}
	if (n <= 0) {
		insertElement->next = cycleIter->next;
		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(-1);
        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;
}

参考文章

数据结构与算法分析