[数据结构与算法]第92篇 C++数据结构（二）链表

1.链表简介

链表是一种通过指针串联在一起的线性结构，每一个节点是又两部分组成，一个是数据域一个是指针域（单向链表：存放指向下一个节点的指针，双向链表：存放指向下一个节点的指针和上一个的指针），最后一个节点的指针域指向null（空指针的意思）。链接的入口点称为列表的头结点也就是head。

1.1.链表的分类

1、单链表（最普通的链表）
2、双向链表（有两个指针域）
3、循环链表（首尾相接）
4、静态链表（链表的数组表示法）

1.2.链表的优点：

1、插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可。
2、没有空间限制,存储元素无上限,只与内存空间大小有关。
3、动态分配内存空间，不用事先开辟内存。

1.3.链表的缺点：

1、查找速度比较慢，因为在查找时，只能顺序查找，需要遍历整个链表
2、内存空间消耗更大，因为需要额外的空间存储指针信息。
3、 对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC(自动垃圾回收器)

1.4.节点说明

头节点：不是必须存在（若存在则为链表的第一个节点）其主要作用是使所有链表（包括空表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行（还是挺有用的）。其数据域可以不储存任何数据，若储存则通常是链表的长度啥的。

首元节点：第一个数据域中储存有效数据的节点 若头节点不存在 则其为链表的第一个节点，是一定要存在的（除非是空表）

头指针：指向链表第一个节点的指针，通过其访问整个链表，在链表长度不为零的情况下，如果有头节点，头指针就是头节点，如果没有头节点，头指针就是首元节点，如果链表长度为零，即链表为空，则头指针为空。

1.5.链表的定义与使用

链表是通过一个个节点串起来的，因此使用节点时先定义节点，如定义一个存储整型数据的单向链表的节点如下：

struct Node {
	int value;//数据域
	Node* next;//指针域
};

如果只是简单的应用，那么可以用一个节点表示链表，即表头，那么可以定义如下：

Node* listHead = new Node;//有头节点

Node* listHead = nullptr;//无头节点

插入数据的方法有头插法和尾插法：

//新节点
Node* newNode = new Node;
newNode->value = 4;
newNode->next = nullptr;

//无头节点
//头插法
newNode->next = listHead;
listHead = newNode;
//尾插法
Node* tailNode = listHead;
while(tailNode->next) {
	tailNode = tailNode->next;
}
tailNode->next = newNode;

//有头节点
//头插法
newNode->next = listHead->next;
listHead->next = newNode;
//尾插法
Node* tailNode = listHead;
while(tailNode->next) {
	tailNode = tailNode->next;
}
tailNode->next = newNode;

如果要更方便的应用，那就可以定义一个链表：

struct List {
	Node* front;
	Node* tail;
};

这样头插和尾插都方便。
如果再要方便一点，就在节点内添加构造函数：

struct Node {
	int value;//数据域
	Node* next;//指针域

	Node(int val): value(val), next(nullptr){}
	Node(int val, Node* _next), value(val), next(_next){}
};

插入数据时：

//无头节点
//头插法
listHead = new Node(4, listHead);
//尾插法
Node* tailNode = listHead;
while(tailNode->next) {
	tailNode = tailNode->next;
}
tailNode->next = new Node(4);

//有头节点
//头插法
listHead->next = new Node(4, listHead->next);
//尾插法
Node* tailNode = listHead;
while(tailNode->next) {
	tailNode = tailNode->next;
}
tailNode->next = new Node(4);

遍历的时候，要借助辅助空间：

//无头
Node* currNode = listHead;
while(currNode) {
	std::cout << currNode->value << ", ";
	currNode = currNode->next;
}
std::cout << std::endl;

//有头
Node* currNode = listHead->next;
while(currNode) {
	std::cout << currNode->value << ", ";
	currNode = currNode->next;
}
std::cout << std::endl;

1.6.链表相关操作

插入、删除、查找、替换、反转、排序、截取、遍历、拼接等。
不使用标准模板库的链表容器，则需要我们自定义相关方法，在此封装一个数组类，封装了以上序列操作，技术不过关，如有错误，请以斧正。

链表插入数据的方法

1.头部插入
2.尾部插入
3.指定位置插入
4.指定区间插入：在区间内插入同一个数据或者一段数据

链表删除数据的方法

1.删除头部
2.删除尾部
3.删除指定位置
4.删除指定数据（只要等于就删除）
5.删除指定位置指定数据（如果这个位置的数据等于要删除的数据就删除）
6.删除指定区间（删除范围内所有数据）

链表查找数据的方法

1.顺序查找指定数据
2.指定位置查找指定数据
3.指定区间查找数据

链表替换数据的方法

1.替换指定位置数据
2.替换指定目标数据
3.替换指定区间数据

链表反转数据的方法

1.整体反转
2.指定区间反转

链表排序数据的方法

1.冒泡排序
2.选择排序

链表截取数据的方法

1.截取区间数据
2.截取指定位置往后数据

链表遍历数据的方法（用于封装之后的遍历）

迭代器遍历

链表拼接数据的方法（封装之后）

重载+拼接

2.Node节点

封装的是一个双向链表，再次定义一个双向链表的节点：

template <typename _dataType>
struct Node
{
	using _NodePtr = Node*;

	_dataType m_value;
	_NodePtr m_next;
	_NodePtr m_pre;

	Node() : m_value(_dataType()), m_next(nullptr), m_pre(nullptr) {}
	Node(_dataType value) : m_value(value), m_next(nullptr), m_pre(nullptr) {}
	Node(_dataType value, _NodePtr next) : m_value(value), m_next(next), m_pre(nullptr) {}
	Node(_dataType value, _NodePtr next, _NodePtr pre) : m_value(value), m_next(next), m_pre(pre) {}
};

3.List类

简单实现一些数据和操作的封装。

3.1.变量

3.2.方法

3.3.迭代器

简单的实现四个迭代器，没有很多方法。

3.3.1.变量

3.3.2.方法

4.测试

int listTest()在List.h声明，在List.cpp定义

4.1.测试代码

#include "List.h"

void list_constructorTest();//构造函数测试
void list_insertTest();//插入测试
void list_eraseTest();//删除测试
void list_selectTest();//查找测试
void list_replaceTest();//替换测试
void list_reverseTest();//反转测试
void list_sortTest();//排序测试
void list_subTest();//截取测试
void list_ergodicTest();//遍历测试
void list_connectTest();//连接测试
void list_iteratorTest();//迭代器测试

int listTest()
{
	list_constructorTest();//构造函数测试
	list_insertTest();//插入测试
	list_eraseTest();//删除测试
	list_selectTest();//查找测试
	list_replaceTest();//替换测试
	list_reverseTest();//反转测试
	list_sortTest();//排序测试
	list_subTest();//截取测试
	list_ergodicTest();//遍历测试
	list_connectTest();//连接测试
	list_iteratorTest();//迭代器测试

	return 0;
}

void list_constructorTest()//构造函数测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;

	std::cout << "\n传节点构造：" << std::endl;
	Node<int>* head = new Node<int>(2);
	List<int> list2(head);

	std::cout << "\n拷贝构造：" << std::endl;
	List<int> list3(list2);
}

void list_insertTest()//插入测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n头部插入：" << std::endl;
	list.push_front(9);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n尾部插入：" << std::endl;
	list.push_back(7);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n指定位置插入：" << std::endl;
	list.insert(3, 16);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n指定区间插入：" << std::endl;
	list.insert(4, 7, 16);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;
}

void list_eraseTest()//删除测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n头部删除：" << std::endl;
	list.pop_front();
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n尾部删除：" << std::endl;
	list.pop_back();
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n指定位置删除：" << std::endl;
	list.eraseIndex(3);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n指定位置指定数据删除：" << std::endl;
	list.eraseIndexValue(3, 8);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	list.eraseIndexValue(3, 6);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n指定数据删除：" << std::endl;
	std::cout << "\n在3---7插入19：" << std::endl;
	list.insert(3, 7, 19);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n指定数据删除：" << std::endl;
	list.eraseValue(19);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n指定区间删除：" << std::endl;
	list.eraseSection(3, 7);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;
}

void list_selectTest()//查找测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n查找指定数据：" << std::endl;
	int res = list.selectIndex(9);
	if (res != -1) {
		std::cout << "在" << res << "处" << std::endl;
	}
	else {
		std::cout << "找不到！" << std::endl;
	}

	std::cout << "\n查找指定位置指定数据：" << std::endl;
	if (list.selectIndexValue(3, 9)) {
		std::cout << "在3处是9" << std::endl;
	}
	else {
		std::cout << "在3处不是9" << std::endl;
	}

	std::cout << "\n查找指定指定区间数据：" << std::endl;
	if (list.selectSection(3, 9, 5)) {
		std::cout << "5在3-------9之间" << std::endl;
	}
	else {
		std::cout << "5不在3-------9之间" << std::endl;
	}
}

void list_replaceTest()//替换测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n替换指定数据：" << std::endl;
	list.replaceIndex(1, 44);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n替换目标数据：" << std::endl;
	std::cout << "\n在1---5插入22：" << std::endl;
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n将22替换为44：" << std::endl;
	list.replaceValue(22, 44);
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n替换区间数据：" << std::endl;
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;
}

void list_reverseTest()//反转测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n整体反转：" << std::endl;
	List<int> list2 = list.reverse();
	for (int num : list2) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n区间反转：" << std::endl;
	List<int> list3 = list.reverse(4, 7);
	for (int num : list3) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;
}

void list_sortTest()//排序测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n冒泡排序：" << std::endl;
	List<int> list2 = list.bubbleSort();
	for (int num : list2) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n选择排序：" << std::endl;
	List<int> list3 = list.selectionSort();
	for (int num : list3) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;
}

void list_subTest()//截取测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n截取区间数据：" << std::endl;
	List<int> list2 = list.subList(3, 9);
	for (int num : list2) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n截取指定位置往后数据：" << std::endl;
	List<int> list3 = list.subList(3);
	for (int num : list3) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;
}

void list_ergodicTest()//遍历测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;
}

void list_connectTest()//连接测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	List<int> list2;
	for (int i = 1; i < 11; i++) {
		list.push_back(i);
	}
	for (int num : list2) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n连接：" << std::endl;
	List<int> list3 = list + list2;
	for (int num : list3) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;
}

void list_iteratorTest()//迭代器测试
{
	std::cout << "\n缺省构造：" << std::endl;
	List<int> list;
	for (int i = 1; i < 13; i++) {
		list.push_back(i);
	}
	for (int num : list) {
		std::cout << num << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n正向迭代器遍历：" << std::endl;
	for (List<int>::iterator it = list.begin(); it != list.end(); it++) {
		std::cout << *it << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n正向常量迭代器遍历：" << std::endl;
	for (List<int>::const_iterator it = list.cbegin(); it != list.cend(); it++) {
		std::cout << *it << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n反向迭代器遍历：" << std::endl;
	for (List<int>::reverse_iterator it = list.rbegin(); it != list.rend(); it++) {
		std::cout << *it << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n反向常量迭代器遍历：" << std::endl;
	for (List<int>::const_reverse_iterator it = list.crbegin(); it != list.crend(); it++) {
		std::cout << *it << ", ";
	}
	std::cout << std::endl;

	std::cout << "\n正向迭代器修改值：" << std::endl;
	for (List<int>::iterator it = list.begin(); it != list.end(); it++) {
		*it = 7;
	}
	for (List<int>::iterator it = list.begin(); it != list.end(); it++) {
		std::cout << *it << ", ";
	}
	std::cout << std::endl;

	int num = 10;
	std::cout << "\n反向迭代器修改值：" << std::endl;
	for (List<int>::reverse_iterator it = list.rbegin(); it != list.rend(); it++) {
		*it = num++;
	}
	for (List<int>::reverse_iterator it = list.rbegin(); it != list.rend(); it++) {
		std::cout << *it << ", ";
	}
	std::cout << std::endl;

	for (List<int>::iterator it = list.begin(); it != list.end(); it++) {
		std::cout << *it << ", ";
	}
	std::cout << std::endl;
}

4.2.输出结果

缺省构造：

传节点构造：

拷贝构造：

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

头部插入：
9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

尾部插入：
9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 7,

指定位置插入：
9, 1, 2, 16, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 7,

指定区间插入：
9, 1, 2, 16, 16, 16, 16, 16, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 7,

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

头部删除：
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

尾部删除：
2, 3, 4, 5, 6, 7, 8, 9, 10, 11,

指定位置删除：
2, 3, 4, 6, 7, 8, 9, 10, 11,

指定位置指定数据删除：
2, 3, 4, 6, 7, 8, 9, 10, 11,
2, 3, 4, 6, 7, 8, 9, 10, 11,

指定数据删除：

在3---7插入19：
2, 3, 4, 19, 19, 19, 19, 19, 6, 7, 8, 9, 10, 11,

指定数据删除：
2, 3, 4, 6, 7, 8, 9, 10, 11,

指定区间删除：
2, 3, 4, 11,

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

查找指定数据：
在8处

查找指定位置指定数据：
在3处不是9

查找指定指定区间数据：
5在3-------9之间

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

替换指定数据：
1, 44, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

替换目标数据：

在1---5插入22：
1, 44, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

将22替换为44：
1, 44, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

替换区间数据：
1, 44, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

整体反转：
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,

区间反转：
1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12,

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

冒泡排序：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

选择排序：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

截取区间数据：
4, 5, 6, 7, 8, 9, 10,

截取指定位置往后数据：
4, 5, 6, 7, 8, 9, 10, 11, 12,

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,


连接：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

缺省构造：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

正向迭代器遍历：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

正向常量迭代器遍历：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

反向迭代器遍历：
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,

反向常量迭代器遍历：
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,

正向迭代器修改值：
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

反向迭代器修改值：
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,

5.List实现代码

#pragma once
#ifndef _LIST_H_
#define _LIST_H_

#include <iostream>
#include <cassert>

template <typename _dataType>
struct Node
{
	using _NodePtr = Node*;

	_dataType m_value;
	_NodePtr m_next;
	_NodePtr m_pre;

	Node() : m_value(_dataType()), m_next(nullptr), m_pre(nullptr) {}
	Node(_dataType value) : m_value(value), m_next(nullptr), m_pre(nullptr) {}
	Node(_dataType value, _NodePtr next) : m_value(value), m_next(next), m_pre(nullptr) {}
	Node(_dataType value, _NodePtr next, _NodePtr pre) : m_value(value), m_next(next), m_pre(pre) {}
};

using _sizeType = size_t;

template <typename _dataType>
class List
{
	using _NodePtr = Node<_dataType>*;
public:
	List() : m_front(nullptr), m_tail(nullptr), m_len(0) {}
	List(_NodePtr node) : m_front(node), m_tail(node), m_len(1) {}
	List(const List& list)
	{
		if (list.m_front) {
			m_front = new Node<_dataType>(list.m_front->m_value);
			m_tail = m_front;
			m_len = 1;
			_NodePtr listfront = list.m_front->m_next;
			while (listfront) {
				m_tail->m_next = new Node<_dataType>(listfront->m_value, nullptr, m_tail);
				m_tail = m_tail->m_next;
				listfront = listfront->m_next;
				m_len++;
			}
		}
		else {
			m_front = nullptr;
			m_tail = nullptr;
			m_len = 0;
		}
	}
	~List()
	{
		_NodePtr front = m_front;
		while (front) {
			_NodePtr node = front;
			front = front->m_next;

			delete node;
			node = nullptr;
		}
	}

	_sizeType size() const
	{
		return m_len;
	}

	_sizeType length() const
	{
		return m_len;
	}

	bool empty()
	{
		return m_front == nullptr;
	}

	bool setData(int index, _dataType value)
	{
		if (index < 0 || index >= m_len) {
			return false;
		}
		
		_NodePtr front = m_front;
		while (index-- > 0) {
			front = front->m_next;
		}
		front->m_value = value;

		return true;
	}

	bool empty() const
	{
		return m_front == nullptr;
	}

	bool push_front(_dataType value)
	{
		m_front = new Node<_dataType>(value, m_front);

		if (m_len == 0) {
			m_tail = m_front;
		}
		m_len++;

		return true;
	}

	bool push_back(_dataType value)
	{
		if (m_tail == nullptr) {
			return push_front(value);
		}

		m_tail->m_next = new Node<_dataType>(value, nullptr, m_tail);
		m_tail = m_tail->m_next;

		m_len++;

		return true;
	}

	bool insert(_dataType value)
	{
		return push_back(value);
	}

	bool insert(int index, _dataType value)
	{
		if (index < 0 || index > m_len) {
			return false;
		}
		else if (index == 0) {
			return push_front(value);
		}
		else if (index == m_len) {
			return push_back(value);
		}

		_NodePtr front = m_front;
		while (index-- > 1) {
			front = front->m_next;
		}

		front->m_next = new Node<_dataType>(value, front->m_next, front);
		m_len++;

		return true;
	}

	bool insert(int begin, int end, _dataType value)
	{
		if (begin < 0 || begin > end || end > m_len) {
			return false;
		}

		int index = begin;
		while (begin <= end) {
			insert(index, value);
			begin++;
		}

		return true;
	}

	bool pop_front()
	{
		if (m_front == nullptr) {
			return false;
		}
		else if (m_front->m_next == nullptr) {
			delete m_front;
			delete m_tail;
			m_front = nullptr;
			m_tail = nullptr;
			m_len = 0;

			return true;
		}

		_NodePtr front = m_front;
		m_front = m_front->m_next;
		m_front->m_pre = nullptr;
		delete front;
		front = nullptr;

		m_len--;

		return true;
	}

	bool pop_back()
	{
		if (m_front == nullptr) {
			return false;
		}
		else if (m_front->m_next == nullptr) {
			delete m_front;
			delete m_tail;
			m_front = nullptr;
			m_tail = nullptr;
			m_len = 0;

			return true;
		}

		_NodePtr front = m_front;
		while (front->m_next->m_next) {
			front = front->m_next;
		}

		_NodePtr tail = m_tail;
		m_tail = front;
		m_tail->m_next = nullptr;
		delete tail;
		tail = nullptr;

		m_len--;

		return true;
	}

	bool eraseIndex(int index)
	{
		if (index < 0 || index >= m_len) {
			return true;
		}
		else if (index == 0) {
			return pop_front();
		}
		else if (index == m_len - 1) {
			return pop_back();
		}

		_NodePtr front = m_front;
		while (index-- > 1) {
			front = front->m_next;
		}

		_NodePtr node = front->m_next;
		front->m_next = node->m_next;
		node->m_next->m_pre = front;
		
		delete node;
		node = nullptr;

		m_len--;

		return true;
	}

	bool eraseValue(_dataType value)
	{
		_NodePtr front = m_front;
		int index = 0;
		while (front) {
			if (front->m_value == value) {
				front = front->m_next;
				eraseIndex(index);
			}
			else {
				front = front->m_next;
				index++;
			}
		}

		return true;
	}

	bool eraseIndexValue(int index, _dataType value)
	{
		_NodePtr front = m_front;
		int in = 0;
		while (front) {
			if (in == index && front->m_value == value) {
				front = front->m_next;
				return eraseIndex(index);
			}
			else {
				front = front->m_next;
				index++;
			}
		}

		return false;
	}

	bool eraseSection(int begin, int end)
	{
		if (begin < 0 || begin > end || end >= m_len) {
			return false;
		}

		int index = begin;
		while (begin <= end) {
			eraseIndex(index);
			begin++;
		}

		return true;
	}

	int selectIndex(_dataType value)
	{
		_NodePtr front = m_front;
		int index = 0;
		while (front) {
			if (front->m_value == value) {
				return index;
			}

			front = front->m_next;
			index++;
		}

		return -1;
	}

	bool selectIndexValue(int index, _dataType value)
	{
		if (index < 0 || index >= m_len) {
			return false;
		}

		_NodePtr front = m_front;
		int in = 0;
		while (front) {
			if (in == index && front->m_value == value) {
				return true;
			}

			front = front->m_next;
			in++;
		}

		return false;
	}

	bool selectSection(int begin, int end, _dataType value)
	{
		if (begin < 0 || begin > end || end >= m_len) {
			return false;
		}

		_NodePtr front = m_front;
		int in = 0;
		while (front) {
			if (in >= begin && in <= end && front->m_value == value) {
				return true;
			}

			front = front->m_next;
			in++;
		}

		return false;
	}

	bool replaceIndex(int index, _dataType value)
	{
		if (index < 0 || index >= m_len) {
			return false;
		}

		_NodePtr front = m_front;
		while (index-- > 0) {
			front = front->m_next;
		}
		front->m_value = value;

		return true;
	}

	bool replaceValue(_dataType target, _dataType value)
	{
		_NodePtr front = m_front;
		while (front) {
			if (front->m_value == target) {
				front->m_value = value;
			}
			front = front->m_next;
		}

		return true;
	}

	bool replaceSection(int begin, int end, _dataType value)
	{
		if (begin < 0 || begin > end || end >= m_len) {
			return false;
		}

		while(begin <= end) {
			replaceIndex(begin, value);
			begin++;
		}

		return true;
	}

	List<_dataType> reverse()
	{
		List<_dataType> list(*this);
		
		_NodePtr front = list.m_front;
		list.m_front = list.m_tail;
		list.m_tail = front;

		_NodePtr pre = nullptr;
		while (front) {
			_NodePtr next = front->m_next;

			front->m_next = pre;
			front->m_pre = next;
			pre = front;

			front = next;
		}

		return list;
	}

	List<_dataType> reverse(int begin, int end)
	{
		if (begin < 0 || begin > end || end >= m_len || begin == end) {
			return List<_dataType>();
		}

		int beginIndex = begin;

		List<_dataType> list(*this);

		int in = begin;
		_NodePtr firstNode = list.m_front;
		while (in-- > 1) {
			firstNode = firstNode->m_next;
		}

		_NodePtr beginNode = list.m_front;
		while (begin-- > 0) {
			beginNode = beginNode->m_next;
		}

		_NodePtr endNode = list.m_front;
		while (end-- > 0) {
			endNode = endNode->m_next;
		}

		_NodePtr secondNode = endNode->m_next;
		endNode->m_next = nullptr;

		_NodePtr bNode = beginNode;
		_NodePtr preNode = nullptr;
		while (bNode) {
			_NodePtr nextNode = bNode->m_next;
			bNode->m_next = preNode;
			bNode->m_pre = nextNode;
			preNode = bNode;

			bNode = nextNode;
		}

		if (beginNode) {
			beginNode->m_next = secondNode;
		}

		if (beginIndex == 0) {
			list.m_front = endNode;
		}
		else if(firstNode) {
			firstNode->m_next = endNode;
		}

		return list;
	}

	List<_dataType> bubbleSort()
	{
		List<_dataType> list(*this);

		_NodePtr front = list.m_front;
		while(front && front->m_next) {
			_NodePtr firstNode = list.m_front;
			_NodePtr secondeNode = firstNode->m_next;

			while (secondeNode) {
				if (firstNode->m_value > secondeNode->m_value) {
					std::swap(firstNode->m_value, secondeNode->m_value);
				}

				firstNode = secondeNode;
				secondeNode = firstNode->m_next;
			}

			front = front->m_next;
		}

		return list;
	}

	List<_dataType> selectionSort()
	{
		List<_dataType> list(*this);

		_NodePtr front = list.m_front;
		while (front && front->m_next) {
			_NodePtr minNode = front;

			_NodePtr secondeNode = front->m_next;
			while (secondeNode) {
				if (secondeNode->m_value < minNode->m_value) {
					minNode = secondeNode;
				}

				secondeNode = secondeNode->m_next;
			}

			if (minNode != front) {
				std::swap(minNode->m_value, front->m_value);
			}

			front = front->m_next;
		}

		return list;
	}

	List<_dataType> subList(int begin, int end)
	{
		if (begin < 0 || begin > end || end >= m_len) {
			return List<_dataType>();
		}

		List<_dataType> list;

		_NodePtr beginNode = m_front;
		while (begin-- > 0) {
			beginNode = beginNode->m_next;
		}

		_NodePtr endNode = m_front;
		while (end-- > 0) {
			endNode = endNode->m_next;
		}

		do {
			list.push_back(beginNode->m_value);
			beginNode = beginNode->m_next;
		} while (beginNode != endNode);
		list.push_back(endNode->m_value);

		return list;
	}

	List<_dataType> subList(int begin)
	{
		if (begin < 0 || begin >= m_len) {
			return List<_dataType>();
		}

		List<_dataType> list;

		_NodePtr beginNode = m_front;
		while (begin-- > 0) {
			beginNode = beginNode->m_next;
		}

		while (beginNode) {
			list.push_back(beginNode->m_value);
			beginNode = beginNode->m_next;
		}

		return list;
	}

	void print() const {
		_NodePtr front = m_front;
		while (front) {
			std::cout << front->m_value << ", ";
			front = front->m_next;
		}
		std::cout << std::endl;
	}

	List<_dataType> splice(const List<_dataType>& right)
	{
		List<_dataType> list(*this);

		_NodePtr beginNode = right.m_front;
		while (beginNode) {
			list.push_back(beginNode->m_value);
			beginNode = beginNode->m_next;
		}

		return list;
	}

	List<_dataType> operator + (const List<_dataType>& right)
	{
		List<_dataType> list(*this);

		_NodePtr beginNode = right.m_front;
		while (beginNode) {
			list.push_back(beginNode->m_value);
			beginNode = beginNode->m_next;
		}

		return list;
	}

private:
	_NodePtr m_front;
	_NodePtr m_tail;
	_sizeType m_len;

private:

	using _ListPtr = List<_dataType>*;
	class ListIteratorBase
	{
	public:
		ListIteratorBase() : m_list(nullptr), m_currNode(nullptr) {}
		ListIteratorBase(_ListPtr list, _NodePtr currNode)
			: m_list(list), m_currNode(currNode) {}

		_dataType operator * ()
		{
			assert(m_currNode);
			return m_currNode->m_value;
		}
	protected:
		_ListPtr m_list;
		_NodePtr m_currNode;
	};

	class ListIterator : public ListIteratorBase
	{
		using _MyBase = ListIteratorBase;
	public:
		ListIterator() : ListIteratorBase() {}
		ListIterator(_ListPtr list, _NodePtr currNode) : ListIteratorBase(list, currNode) {}

		bool operator == (const ListIterator& it)
		{
			return _MyBase::m_currNode == it._MyBase::m_currNode;
		}

		bool operator != (const ListIterator& it)
		{
			return _MyBase::m_currNode != it._MyBase::m_currNode;
		}

		ListIterator operator ++ ()
		{
			assert(_MyBase::m_currNode);
			_MyBase::m_currNode = _MyBase::m_currNode->m_next;
			return *this;
		}

		ListIterator operator ++ (int)
		{
			assert(_MyBase::m_currNode);
			ListIterator& it = *this;
			_MyBase::m_currNode = _MyBase::m_currNode->m_next;
			return it;
		}

		ListIterator operator -- ()
		{
			assert(_MyBase::m_currNode);
			_MyBase::m_currNode = _MyBase::m_currNode->m_pre;
			return *this;
		}

		ListIterator operator -- (int)
		{
			assert(_MyBase::m_currNode);
			ListIterator& it = *this;
			_MyBase::m_currNode = _MyBase::m_currNode->m_pre;
			return it;
		}

		_dataType& operator * ()
		{
			assert(_MyBase::m_currNode);
			return _MyBase::m_currNode->m_value;
		}
	};

	class ListConstIterator : public ListIteratorBase
	{
		using _MyBase = ListIteratorBase;
	public:
		ListConstIterator() : ListIteratorBase() {}
		ListConstIterator(_ListPtr list, _NodePtr currNode) : ListIteratorBase(list, currNode) {}

		bool operator == (const ListConstIterator& it)
		{
			return _MyBase::m_currNode == it._MyBase::m_currNode;
		}

		bool operator != (const ListConstIterator& it)
		{
			return _MyBase::m_currNode != it._MyBase::m_currNode;
		}

		ListConstIterator operator ++ ()
		{
			assert(_MyBase::m_currNode);
			_MyBase::m_currNode = _MyBase::m_currNode->m_next;
			return *this;
		}

		ListConstIterator operator ++ (int)
		{
			assert(_MyBase::m_currNode);
			ListConstIterator& it = *this;
			_MyBase::m_currNode = _MyBase::m_currNode->m_next;
			return it;
		}

		ListConstIterator operator -- ()
		{
			assert(_MyBase::m_currNode);
			_MyBase::m_currNode = _MyBase::m_currNode->m_pre;
			return *this;
		}

		ListConstIterator operator -- (int)
		{
			assert(_MyBase::m_currNode);
			ListConstIterator& it = *this;
			_MyBase::m_currNode = _MyBase::m_currNode->m_pre;
			return it;
		}
	};

	class ListReverseIterator : public ListIteratorBase
	{
		using _MyBase = ListIteratorBase;
	public:
		ListReverseIterator() : ListIteratorBase() {}
		ListReverseIterator(_ListPtr list, _NodePtr currNode) : ListIteratorBase(list, currNode) {}

		bool operator == (const ListReverseIterator& it)
		{
			return _MyBase::m_currNode == it._MyBase::m_currNode;
		}

		bool operator != (const ListReverseIterator& it)
		{
			return _MyBase::m_currNode != it._MyBase::m_currNode;
		}

		ListReverseIterator operator ++ ()
		{
			assert(_MyBase::m_currNode);
			_MyBase::m_currNode = _MyBase::m_currNode->m_pre;
			return *this;
		}

		ListReverseIterator operator ++ (int)
		{
			assert(_MyBase::m_currNode);
			ListReverseIterator& it = *this;
			_MyBase::m_currNode = _MyBase::m_currNode->m_pre;
			return it;
		}

		ListReverseIterator operator -- ()
		{
			assert(_MyBase::m_currNode);
			_MyBase::m_currNode = _MyBase::m_currNode->m_next;
			return *this;
		}

		ListReverseIterator operator -- (int)
		{
			assert(_MyBase::m_currNode);
			ListReverseIterator& it = *this;
			_MyBase::m_currNode = _MyBase::m_currNode->m_next;
			return it;
		}

		_dataType& operator * ()
		{
			assert(_MyBase::m_currNode);
			return _MyBase::m_currNode->m_value;
		}
	};


	class ListConstReverseIterator : public ListIteratorBase
	{
		using _MyBase = ListIteratorBase;
	public:
		ListConstReverseIterator() : ListIteratorBase() {}
		ListConstReverseIterator(_ListPtr list, _NodePtr currNode) : ListIteratorBase(list, currNode) {}

		bool operator == (const ListConstReverseIterator& it)
		{
			return _MyBase::m_currNode == it._MyBase::m_currNode;
		}

		bool operator != (const ListConstReverseIterator& it)
		{
			return _MyBase::m_currNode != it._MyBase::m_currNode;
		}

		ListConstReverseIterator operator ++ ()
		{
			assert(_MyBase::m_currNode);
			_MyBase::m_currNode = _MyBase::m_currNode->m_pre;
			return *this;
		}

		ListConstReverseIterator operator ++ (int)
		{
			assert(_MyBase::m_currNode);
			ListConstReverseIterator& it = *this;
			_MyBase::m_currNode = _MyBase::m_currNode->m_pre;
			return it;
		}

		ListConstReverseIterator operator -- ()
		{
			assert(_MyBase::m_currNode);
			_MyBase::m_currNode = _MyBase::m_currNode->m_next;
			return *this;
		}

		ListConstReverseIterator operator -- (int)
		{
			assert(_MyBase::m_currNode);
			ListConstReverseIterator& it = *this;
			_MyBase::m_currNode = _MyBase::m_currNode->m_next;
			return it;
		}
	};

public:
	using iterator = ListIterator;
	using const_iterator = ListConstIterator;
	using reverse_iterator = ListReverseIterator;
	using const_reverse_iterator = ListConstReverseIterator;

	iterator begin()
	{
		return ListIterator(this, m_front);
	}

	iterator end()
	{
		return ListIterator(this, nullptr);
	}

	const_iterator cbegin()
	{
		return ListConstIterator(this, m_front);
	}

	const_iterator cend()
	{
		return ListConstIterator(this, nullptr);
	}

	reverse_iterator rbegin()
	{
		return ListReverseIterator(this, m_tail);
	}

	reverse_iterator rend()
	{
		return ListReverseIterator(this, nullptr);
	}

	const_reverse_iterator crbegin()
	{
		return ListConstReverseIterator(this, m_tail);
	}

	const_reverse_iterator crend()
	{
		return ListConstReverseIterator(this, nullptr);
	}
};

#endif //_LIST_H_

6.总结

只实现了些许方法，看STL里面似乎有挺多的，以后在慢慢研究了。

阅读世界，共赴山海

423全民读书节，邀你共读