概览

链表是一种有优秀动态性的数据结构，它通过指针来连接每一个节点(node)形成一个整体。链表可以很方便的插入删减，但是因为其不在一段连续的内存空间，它的遍历效率较低下而且因为每个节点多存储了指向下一个节点的指针所以占用空间比数组大。
这篇 blog 就作为自己的单向链表学习笔记，讲述链表的结构、初始化、删除节点等操作。

创建链表

要实现链表，可以用结构体来实现:

1
2
3
4
5
6

struct LinkNode
{
	int var;
	LinkNode *next;
	LinkNode(int x) : var(x), next(nullptr) {}
};

这里首先定义了一个 LinkNode 的结构体，每一个这样的一个结构体都是链表的一个节点，这是每一个节点的一个数据类型。其中var是这个节点的数据，LinkNode 类型的 *next 指针指向下一个节点。而下面是这个结构体的构造函数:
构造函数首先声明了需要一个 int 类型的参数，这样就可以非常简单的赋予参数，冒号后面是一个前导，它将 x 赋值到 var，并将指针默认为 nullptr，这里的nullptr是 C++ 的一个关键字即空指针。
上面构造了链表节点的图纸，而接下来就是要根据图纸创建链表了!
下面代码，创建了 4 个节点的链表：

1
2
3
4
5
6
7
8

LinkNode *n0 = new LinkNode(5);
LinkNode *n1 = new LinkNode(2);
LinkNode *n2 = new LinkNode(4);
LinkNode *n3 = new LinkNode(8);

n0->next = n1;
n1->next = n2;
n2->next = n3;

可以看到 n0 ~ n3 是每个节点的名称，而每个节点名其实就是指向这个节点地址的指针，是等价关系的，等号右边是在堆当中用 C++ 的new函数创建一个空间存储LinkNode类型的数据，这里的数据有 var和*next。而且还需要将每一个节点链接，就是将每个节点的 *next 赋值为下一个节点的地址。

结构体指针要使用指针内的元素用 ->运算符。

到这一步，有四个节点的链表就创建完成，接下来编写函数来操作这个链表。

操作链表

1.打印链表

要打印内容首先需要 iostream 内的 cout 函数，而后因为要打印内容需要遍历整个链表则需要循环，循环的终止条件可以是指针从头遍历到尾直至到 nullptr 为止，此时跳出循环，而如果要知道循环次数就需要知道链表长度，很显然还需要传入一个参数。综合以上考虑，用 while 循环是最好的选择。

1
2
3
4
5
6
7
8
9

void printLN (LinkNode* ptr)
{
	using namespace std;
	while(ptr != nullptr)
	{
		cout << ptr->var << endl;
		ptr = ptr->next;
	}
}

只需要传入链表第一个节点指针就可以操作整个链表。用 while 循环当 ptr 不指向空时循环运行，此时要注意需要让 ptr 不断指向下一个节点否则会陷入死循环。
余下用 cout 函数打印节点 var 变量内容就可以打印整个链表内容了。

2.查找节点

实现查找节点除了第一个节点外还需要查找目标参数，这个参数同样是 int 类型。查找到相同元素后需要返回索引，则这是一个 int 类型的函数。
和打印一样，用 while 遍历整个链表比较方便，但此时需要知道节点索引，这里就还需要先在函数生存域内声明一个 index 变量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int find(LinkNode *ptr, int target)
{
	int index = 0;
	while (ptr != nullptr)
	{
		if (ptr->var == target)
			return index;
		index++;
		ptr = ptr->next;
			
	}
	return -1;
}

核心就是 if判断，若符合相同则返回索引，若是 false 则索引 + 1，指向下一个节点，如果遍历完整个链表都没找到就返回 -1。

3.添加节点

添加节点即在链表内插入一个新的节点，首先肯定是要初始化这个节点，既创建一个内存空间来存放节点。而函数的核心在于指针指向的改变。
首先需要插入点前一个节点的内容，这个节点有下一个节点的地址，我们需要将这个地址复制给新节点的 *next变量，然后将这个地址变成新节点的地址。代码逻辑如下。

1
2
3
4
5

void insert (LinkNode *n0, LinkNode *P)
{
	P->next = n0->next;
	n0->next = P;
}

4.删除节点

要删除节点首先想到的参数自然是要删除的节点，但是当传入要删除节点的时候是无法操作前面一个节点，很显然还需要传入前一个节点，这样太麻烦了……
由此出发，我们可以发现，节点可以通过指针来移动到往后所有的节点，因为我们有 *next这个变量！由这个思路可以知道只需要要删除的节点前一个节点这一个节点就可以完成所需操作，这样方便调用函数。
代码整体很简单先将要删除节点地址赋值到*P变量同时也是指向要删除节点的地址，这样就可以操作要删除的节点。之后将前一个节点的 *next 赋值为 *P的*next变量(其实也就是 p->next)。最后在内存空间中释放删除节点。
但是，假如我们传入参数就是最后一个节点了，那下一个节点是不存在的，那样有什么意义呢？这样会引发编译器报错，所以在最前面需要先判断参数是否为末节点。

1
2
3
4
5
6
7
8
9

void Del(LinkNode *n0)
{
	if (n0->next == nullptr)
		return;

	LinkNode *P = n0->next;
	n0->next = P->next;
	delete P;
}

到这里，基本的链表操作就完成了。