链表的介绍

引言

大家好，我是链表。我呢，是一种存储非连续性数据的物理数据结构，我的每一个数据都用一个个节点来存储，我的每一个节点都用一条条的“链”来链接，因此，就被后人称作链表了。

优缺点

其中，我增加数据和删除数据的时间复杂度最坏是O(n)，因为增加数据的话，就只要让我的最后一个节点接上存储新数据的节点就行了。而删除数据的话，就只要让我倒数第二个节点断开跟我最后一个节点的链接就行了。
虽然我非常擅长这些，但我也有一些坏的地方，如查询数据和修改数据，时间复杂度最好是O(n)，查询的话，就需要让我遍历每一个节点，然后分别对每一个节点判断，才行；而修改的话，其实就是跟我查询数据的操作差不多，也是要先让我遍历每一个节点，然后分别对每一个节点判断才行。

与链表相似的数据结构

而与我相似的数据结构呢，有双向链表，有循环链表，还有他们俩的结合体——双向循环链表，跟C++里的STL容器list差不多。其中，我们将要实现的是单向链表，也就是我，如果你不知道它们长什么样的话，就看下下面的图片吧。

注意事项

不要用节点对象的引用去定位节点，因为这会让我的节点莫名消失！在实际用C/C++实现非连续性存储数据的数据结构的时候至关重要！

单向链表的实现

基础实现

创建类

首先，要想实现我，就需要两个模板类，一个是节点类，一个是单向链表类。

template<class T>
class mylist {
private:class node {public:T t;node* next;node(const T t = NULL, node* nextTo = nullptr) {this->t = t;this->next = nextTo; }};
};

创建成员变量

然后，就要给这个单向链表类增加表示大小的成员变量ic和我的“头”——头结点head了。

template<class T>
class mylist {
private:class node {public:T t;node* next;node(const T t = NULL, node* nextTo = nullptr) {this->t = t;this->next = nextTo;}};int ic;node* head;
};

创建特殊方法

最后，在单向链表类里，我们需要做许多特殊的方法，分别是无参构造方法，数组构造方法，拷贝构造方法，重载赋值运算符和析构方法，其中，析构方法不用递归实现的话对我来说太复杂了，因此，就需要一个助于让我们析构的临时私有方法deletenode方法来销毁我。至此，这些特殊方法做完之后，我们就要准备要创建并实现我增加数据的方法了。

#pragma once
#include <iostream>
using namespace std;
template<class T>
class mylist {
private:class node {public:T t;node* next;node(const T t = NULL, node* nextTo = nullptr) {this->t = t;this->next = nextTo;}};unsigned int ic;node* head;void deletenode(node*& delnode) {if (nullptr != delnode->next) {deletenode(delnode->next);}delnode->next = nullptr;delete delnode;}T* arr;
public:mylist() {this->ic = 0;this->head = new node;}mylist(T* array, const unsigned int isize) {this->ic = isize;this->head = new node;node** addnode = &this->head;for (int i = 0; i < isize; i++) {(*addnode)->next = new node(array[i]);addnode = &(*addnode)->next;}}mylist(const mylist& list) {this->ic = list.ic;this->head = new node;*this = list;}mylist& operator=(const mylist& list) {node* searchnode = list.head;node** addnode = &this->head;while (nullptr != searchnode->next) {searchnode = searchnode->next;(*addnode)->next = new node(searchnode->t);addnode = &(*addnode)->next;}return *this;}~mylist() {deletenode(this->head);}
};

增加数据

增加数据的方法呢，有两个，一个是push_back方法，一个是insert方法。

push_back方法

其中，push_back方法用于在我的最后一个节点插入存放新数据的节点，因此，push_back方法的形参就是要插入的新数据。实现它时，首先要创建一个指向我的头结点的节点对象的指针tailnode，用于定位我的最后一个节点，然后，用一个while循环将这个节点对象指针移到在我的“链”上的下一个节点的地址上，以此类推，最终会使这个节点对象指针定位到我的最后一个节点的地址上，最后，在定位好后，new出来一个节点，这个新节点的值为push_back方法中传入的新数据形参，并让tailnode这个节点指针指向的节点的下一个节点为这个刚new出来的新节点，以此让这个新节点在我的“链”上。之后呢，我的大小自增1，并返回这个新数据，因为这个新数据是泛型的，所以返回的类型就为T。

T push_back(const T item) {node** addnode = &this->head;while (nullptr != (*addnode)->next) {addnode = &(*addnode)->next;}(*addnode)->next = new node(item);this->ic++;return item;
}

insert方法

而insert方法，则用于在我的其中一个节点之前插入存放新数据的节点，跟push_back方法的用途差不多，返回的类型都是泛型T，只不过插入的位置的形参变了。形参呢，除了要插入的新数据之外，还有索引index；位置呢，很随便，哪里都可以插。但需要注意的是，这个索引，它不能是负数，所以这个索引的形参的类型就只能是unsigned int了，之后，我们在实现这个方法前，先要对这个索引形参判断一下，如果这个索引大于等于我的大小，那么就不能插入，直接返回NULL就行，之后，我们定义指向头结点的节点指针addnode，并通过while循环来定位addnode插入的位置，这里的while循环以索引index的值来循环，每循环一次之后就使它自减1，直到它为0为止。定位好后，就new一个节点对象newnode，它的值为要插入的新数据，它的下一个节点则为addnode指向的节点的下一个节点，之后，就用这个addnode节点指针指向的节点来连接节点对象newnode，使其在我的同一条“链”上，就行了，然后，大小自增1，返回新数据的值，整个insert方法也就正式完成了。

T insert(const T item, unsigned int index) {if (index >= this->ic) {return NULL;}node** addnode = &this->head;while (index--) {addnode = &(*addnode)->next;}node* newnode = new node(item, (*addnode)->next);(*addnode)->next = newnode;this->ic++;
}

接着，我们就要实现删除数据的一些方法了。

删除数据

删除数据的方法呢，我要的有三个，第一是del_back方法，第二是del_index方法，第三是clear方法。

del_back方法

del_back方法呢，无参，返回泛型T，对应了我最后一个节点的数据，在实现这个方法之前，像insert方法那样，也需要先判断一下，不过跟insert方法不同的是，del_back方法则先检测我的大小是否为0，如果是，就返回NULL，因为我的大小为0，相当于我只有“头”可以删，我删了“头”等于我“英年早逝”，只有析构方法执行时，我老了，才能“逝”，所以直接返回NULL，不是就继续执行，然后定义一个指向我的头结点的节点指针nextIsTailNode，随即等它在通过while循环移到倒数第2个节点的时候，就让它定位好了，之后，用一个类型为泛型T的变量last存储nextIsTailNode指向的节点的下一个节点的值，并delete掉节点指针nextIsTailNode指向的节点的下一个节点——就是我的最后一个节点，让它指向的的下一个节点设为空指针，然后让我的大小自减1，最后一个节点也就彻底离开我了。

T del_back() {if (!this->ic) {return NULL;}node** nextIsTailNode = &this->head;while (nullptr != (*nextIsTailNode)->next->next) {nextIsTailNode = &(*nextIsTailNode)->next;}T last = (*nextIsTailNode)->next->t;delete (*nextIsTailNode)->next;(*nextIsTailNode)->next = nullptr;this->ic--;return last;
}

del_index方法

而del_index方法，肯定是要有一个代表索引的类型为unsigned int的形参index的，如果你用指向某个节点的指针来删的话，那么这个指针所删除的节点及它后面的节点也一并不见了，相当于我骨折了。因此，我建议你们根据索引来删数据的时候，用节点指针来查找，用节点对象来存储索引所对应的节点的下一个节点及它后面的节点。而且在这个方法实现之前，除了我的大小不能为0之外，如果索引是否大于等于我的大小，也直接返回NULL，不删，之后，根据刚才提到的建议，在后面定义一个指向头节点的节点指针searchnode用于查找，通过while循环执行index次循环，让searchnode通过一次次的转到它的下一个节点的地址来定位。之后定位好，就定义一个类型为泛型T的变量item来存储索引代表的节点的值，然后定义一个节点对象hasnode为searchnode指向的下一个节点的下一个节点及后面的所有节点，并delete掉searchnode节点指针指向的节点及后面的所有节点，然后让searchnode指向的节点跟hasnode节点对象连接一下，既能保证了数据的完整性，又使我只删除了一个节点，最后我的大小自减1，并返回变量item的值，这个del_index方法也实现完毕了。

T del_index(unsigned int index) {if (!this->ic || index >= this->ic) {return NULL;}node** searchnode = &this->head;while (index--) {searchnode = &(*searchnode)->next;}T item = (*searchnode)->next->t;node* hasnode = (*searchnode)->next->next;delete (*searchnode)->next;(*searchnode)->next = hasnode;this->ic--;return item;
}

clear方法

clear方法，就跟我的析构方法差不多，只是要删的对象有差别，析构方法是包括头节点，全都要删，而clear方法，除了头节点以外，全都要删，这就是区别。当然，如果要从头节点的下一个节点开始删的话，就要我的大小不为0才行，否则报错。之后删完全了，就给大小设为0就行了。

void clear() {if (this->ic) {this->ic = 0;deletenode(this->head->next);this->head->next = nullptr;}
}

到后面，就要开始来查询一下数据了。

查询数据

查询数据的方法呢，普通的有at方法，与之同等的重载中括号运算符，你要是想遍历我整个“链”上的元素，也可以带上toArray方法，你要是想查询我所存的元素在哪个节点上，这个节点又在我的哪个位置上，indexOf方法就足够。

at方法与重载的中括号运算符

先略讲at方法，因为at方法的实现跟重载的中括号运算符的实现差不多，所以实现起来很简单，只需要返回重载的中括号运算符返回的值就好。现在主要就是实现重载的中括号运算符。

T& at(const unsigned int index) {return (*this)[index];
}

重载的中括号运算符，有代表索引的类型为unsigned int的形参index。执行这个方法时，第一步，检测一下索引是否正常，如果索引超过我的大小，就直接返回NULL，反之就继续执行；第二步，初始化节点对象searchnode为我头节点的下一个节点，通过index次循环来定位，具体定位的方法前面都讲过了；第三步，也是最后一步，节点对象searchnode定位好后，返回节点对象searchnode的值，就行了。

T& operator[](unsigned int index) {if (index >= this->ic) {static T nulldata = NULL;return nulldata;}node* searchnode = this->head->next;while (index--) {searchnode = searchnode->next;}return searchnode->t;
}

toArray方法

实现这个方法，得先往我这个类里面定义一个将要成为动态数组的指向泛型T类型的arr指针，因为这将要为整个toArray方法提供地基来“搭建”。
之后，就用一个searchnode节点对象在我的“链”上遍历一下我的节点，并把遍历的节点一一转化成数据并输出在动态数组arr里面，最后返回arr这个动态数组的引用，就又好了一次。

T*& toArray() {delete[] this->arr;this->arr = new T[this->ic];node* searchnode = this->head;int i = 0;while (nullptr != searchnode->next) {searchnode = searchnode->next;this->arr[i++] = searchnode->t;}return this->arr;
}

啥?你说我的这个arr动态数组还没有创建和析构的方式?没事，在我的所有构造方法中，可以为动态数组arr new一小块大小为0的内存；在析构方法中，可以delete[]掉这个动态数组arr，即使是大小为0的内存也原封不动地还给操作系统，就跟“借空气，还空气”差不多；在toArray方法中，也可以前面增加这两行代码，只要有了这些必备的代码，那你的构造方法，析构方法和toArray方法也就能放下心了，因为几乎没有任何的bug存在。在这之后，就可以去学最后一个特殊的方法——indexOf方法了。

delete[] this->arr;
this->arr = new T[this->ic];

indexOf方法

在indexOf方法中，只要一个形参——代表要找的数据的类型为泛型T的item。开始执行后，先初始化一个节点对象searchnode为我的头结点，也可以理解成节点对象searchnode对我1:1地进行克隆，用于遍历节点，找到数据，并初始化一个代表索引的无符号整型变量index为0，以此来辅助这个indexOf方法找数据，然后searchnode节点对象遍历我的所有节点：先转到下一个节点，如果searchnode的值为要找的数据，那么就返回这个数据所对应的节点索引——就是刚才创建过的无符号整型index，如果不是，那么索引index自增1，再接着遍历，直到searchnode节点对象找到数据或者遍历完我，如果遍历完我，最后就返回-1，说明这个要找的数据并不在我的某一个节点里面。那为什么这个indexOf方法的返回类型是long long呢，这是我因为怕在返回-1的时候被unsigned int转为正数，从而让用户被我误导，觉得要查找的数据在我的某一个节点上，并且unsigned int所能存储的最大值已经超过了int所能存储的最大值，如果以unsigned int的最大值来访问的话，可能就会因为int所能存储的最大值而被转换成负数。所以，就需要long long类型来返回这个index。好了，在indexOf方法做好之后，接下来就继续看吧。

long long indexOf(const T item) {node* searchnode = this->head;unsigned int index = 0;while (nullptr != searchnode->next) {searchnode = searchnode->next;if (item == searchnode->t) {return index;}index++;}return -1;
}

修改数据

修改数据的话，不需要什么方法，一般修改数据的办法就是借助我的查询方法来用赋值运算符来修改值，没有什么花招。如：

List[0] = 1;//这里的“List”是一个链表对象

获取链表大小

在做好我的最后，获取链表的大小的方法也要有，如size方法和isEmpty方法，不然，用户怎么能查询到我的大小呢?第一是size方法，只需要返回我的大小就行；第二是isEmpty方法，只需要返回我的大小是否为0就行。

unsigned int size() const {return this->ic;
}
bool isEmpty() const {return 0 == this->ic;
}

测试方法是否正常

现在我的所有方法都走做好了，我们也要测试一下了。就一口气测试我的全部方法好了。

#include <iostream>
#include "mylist2.hpp"
using namespace std;int main() {mylist<int>m;//普通构造方法测试cout << "原始大小：" << m.size() << "    是否为空：" << (m.isEmpty() ? "true" : "false") << endl;//size方法与isEmpty方法测试1m.insert(1, 0);//insert方法测试1m.push_back(1);//push_back方法测试1m.push_back(2);//push_back方法测试2m.insert(3, 1);//insert方法测试2cout << "链表m增加数据后大小：" << m.size() << "    是否为空：" << (m.isEmpty() ? "true" : "false") << endl;//size方法与isEmpty方法测试2m.del_back();//del_back方法测试m.del_index(2);//del_index方法测试1m.del_index(1);//del_index方法测试2cout << "链表m删除数据后大小：" << m.size() << "    是否为空：" << (m.isEmpty() ? "true" : "false") << endl;//size方法与isEmpty方法测试3int arr[5] = { 1, 2, 3, 4, 5 };mylist<int>ma(arr, 5);//数组构造方法测试mylist<int>mb = ma;//拷贝构造方法测试const int* arra = ma.toArray();//toArray方法测试1const int* arrb = mb.toArray();//toArray方法测试2int i = 0;while (i < 5) {cout << "ma[" << i << "] == mb[" << i << "]：" << (arra[i] == arrb[i] ? "true" : "false") << endl;//toArray方法测试3i++;}cout << "ma[1] = " << ma[1] << "    ma[3] == ma.at(3)：" << (ma[3] == ma.at(3) ? "true" : "false") << endl;//重载中括号运算符测试1 at方法测试cout << "5 == ma[ma.indexOf(5)]：" << (5 == ma[ma.indexOf(5)] ? "true" : "false") << endl;//重载中括号运算符测试2 indexOf方法测试1cout << "ma.indexOf(7) = " << ma.indexOf(7) << "    NULL == ma[-1]：" << (NULL == ma[-1] ? "true" : "false") << endl;//重载中括号运算符测试3 indexOf方法测试2m.clear();//clear方法测试cout << "链表m清空数据后大小：" << m.size() << "    是否为空：" << (m.isEmpty() ? "true" : "false") << endl;//size方法与isEmpty方法测试4return 0;
}

如果这段测试代码执行之后是这样打印的：

原始大小：0 是否为空：true
链表m增加数据后大小：3 ​ ​ ​ 是否为空：false
链表m删除数据后大小：1 ​ ​ ​ 是否为空：false
ma[0] == mb[0]：true
ma[1] == mb[1]：true
ma[2] == mb[2]：true
ma[3] == mb[3]：true
ma[4] == mb[4]：true
ma[1] = 2 ​ ​ ​ ma[3] == ma.at(3)：true
5 == ma[ma.indexOf(5)]：true
ma.indexOf(7) = -1 ​ ​ ​ NULL == ma[-1]：true
链表m清空数据后大小：0 ​ ​ ​ 是否为空：true

那么，我也就完全实现好了。

总结

通过刚才实现我这个链表类的代码，我们可以知道，我增加数据的时间复杂度为O(n)，因为要通过某一个指向节点对象的指针来定位；删除数据的时间复杂度也为O(n)，或者以delnode方法为例时间复杂度也为O(1)，内存复杂度却为O(n)，因为在删除元素的时候，这两种方法都需要通过循环来定位节点，删除元素；查询数据的时间复杂度还为O(n)，因为都需要通过循环来定位；修改数据的时间复杂度也为O(n)，原因同查询数据的时间复杂度的原因，最后只有获取链表大小的时间复杂度为O(1)，因为这一些方法都通过我私有的成员变量来获取。
虽然来看，我不太行。但是能体现出我们链表优点的，最优是经过一些成长的双向循环链表，他能快速的往尾部插入数据，时间复杂度为O(1)，删除尾部元素，时间复杂度也为O(1)，是我们链表的骄傲！当我想到这个双向循环链表时，我不禁想到了以后的美好未来：在未来中，数据结构们的运行速度将会更快，内存开销将会更少，人类们的生活也将因为这些变得越来越便携，真是一个美好的未来啊！

下篇预告

粗心的连点器