说明

链表太不好用了。明明链表只考选择题 D 老师非要我们做链表的编程题。

---

原文，有删改

在这之前，要引入几个概念：结构体、指针、申请新内存、释放内存。

链表的概念

这个都懂吧。就是一条链。如图：

可以发现，链表的每一个节点（还是结点？）都由至少两部分组成：

1. 储存值的容器
2. 指向下一个节点的指针
3. （可选）指向上一个节点的指针

因此想到结构体。下面是最初始、最简单的链表结构体：

struct node
{
	int val;
	node* next;
};

当然，这里的 node 、 val 和 next 都是结构体、变量名，你可以自由发挥。

好像没什么好讲的了。

链表的分类：

分类-单向/双向链表

单向、双向很好理解，就是每一个节点都加上指向前一个节点的指针。

分类-带/不带头节点链表

那这个呢？先上张大图：

这就体现出来了。假如你现在有一个带头节点的链表 list2 和一个不带头节点的链表 list1 （注意 list1 不带头节点， list2 带头节点）。那么如果你想要遍历 list1 ，你就要从 list1 这个节点（因为它是一个指针）开始遍历。如果你要遍历 list2 ，那你就要从 list2 这个节点的下一个节点开始遍历。视频说不带头节点的链表更方便，现在先不管。

分类-循环/不循环链表

这也比较好理解，只需要把链表的最后一个节点的 next 指向第一个节点就变成循环链表了。

动态链表

链表的定义

定义这个概念是很虚的。因为链表本质是一堆变量，只是根据指针连接而已。这就推出链表一个很重要的性质： 链表的内存不一定是连续的。

为了定义链表，有两种方法。

1. 定义空链表
2. 根据数组定义链表

定义空链表

这就需要使用到一个概念：申请新内存。这也是某一天在做五级（又是五级）客观题是问 D 老师的。哦，前面的话先放在一遍，看这里：

其实好像没啥。函数内部的变量都是储存在栈空间的，函数执行完就会被释放。所以要在函数里实现定义链表，就需要用到申请新内存—— new。在堆空间里申请一些空间来放链表。使用方法：

node* list = new node;

申请一个 node 结构体的空间。这就是空链表了。这又需要知道的一个概念：空——nullptr 。为了后面的遍历链表的停止（找到空就结束），需要把链表的最后一项设为空：

list -> next = nullptr;

还有就是指向一个结构体的指针需要用到 -> 。最后把这个定义的 list 返回，就得到了定义链表的函数：

// 创建空链表
node* create()
{
	node* list = new node;
	list -> next = nullptr;
	return list;
}

要注意的是：返回的 list 只是指向链表第一个节点的指针，而不是整个链表。

根据数组定义链表

这个……只需要召唤小拨鼠，帮你画图理解一下就很好理解了。（这里使用的都是带头指针的链表）

只需要按照思路来就好了。最后把 list 返回。代码：

// 根据数组创建链表
node* create2(int n, int a[])
{
	node* list = new node;
	
	node* p = list;
	for (int i = 1; i <= n; i++)
	{
		node* newNode = new node;
		newNode -> val = a[i];
		p -> next = newNode;
		p = p -> next;
	}
	p -> next = nullptr;
	
	return list;
}

注意最后要把 p 指向 nullptr ，方便后面的遍历。

链表的遍历

类似遍历 map（即迭代器） ，定义一个（不需要申请了） 指针 p ，如果 p 指向的内容不为空，就继续，执行完一次循环体， p 就改为它指向的那一个节点。代码：

// 打印链表
void visit(node* list)
{
	for (auto p = list -> next; p != nullptr; p = p -> next)
	{
		cout << p -> val << " ";
	}
}

链表的删除

这里要引出一个概念： 释放内存 。这也不难。格式是：

delete 地址;

先找到一块你要释放的空间，在前面加上 delete 就好了。因为链表的删除其实不是实际意义上的删除，而是把要删除的节点的上一个和下一个连接：

个人认为这释放空间并没有什么用。反正只有一个节点。

但是这又导致一个问题。要删除这个节点，就需要连接上一个和下一个节点。但是这是单向链表啊，我并不知道它的上一个节点。所以我要找的并不是这一个节点，而是它的上一个节点。

链表的删除有两种方法（或是办法、格式、思路？）：

1. 删除链表的第 n 个数；
2. 删除链表中第一个值为 data 的数。

删除-第 n 个数

因为要删除第 n 个数，就要先找到第 n-1 个数。这直接遍历就好了。

node* p = list;
for (int i = 1; i < n; i++)
{
	p = p -> next;
}

这样就能找到第 n-1 个节点。但是有几个要注意的地方：

1. 如果链表为空？
2. 如果链表没有 n 个数？

所以这要使用 bool 类型的函数，判断删除成功或失败。

bool del(node* list, int n)
{
	if (list == nullptr)return 0;
	node* p = list;
	for (int i = 1; i < n; i++)
	{
		if (p -> next == nullptr)return 0;
		p = p -> next;
	}
	if (p -> next == nullptr)return 0;

}

怎么删除呢？就是先找到要删除的节点（当前 p 的下一个节点），再连接连接上一个和下一个节点。最后把这个节点释放。

bool del(node* list, int n)
{
	if (list == nullptr)return 0;
	node* p = list;
	for (int i = 1; i < n; i++)
	{
		if (p -> next == nullptr)return 0;
		p = p -> next;
	}
	if (p -> next == nullptr)return 0;

	node* cut = p -> next;
	p -> next = cut -> next;
	delete cut;
}

删除-第一个值为 data 的数

基本上都和前面相同。但是需要用指针遍历，而不是 int 了。

bool del2(node* list, int data)
{
	if (list == nullptr)return 0;
	node* p = list;
	for (; p -> next != nullptr; p = p -> next)
	{
		if (p -> next -> val == data)break;
	}
	if (p -> next == nullptr)return 0;

	node* cut = p -> next;
	p -> next = cut -> next;
	delete cut;
}

最后要加上 return 1; 表示删除成功。

链表的插入

这和删除差不多。这里的写法是在链表的第 n 项后插入 data 。

bool insert(node* list, int n, int data)
{
	if (list == nullptr)return 0;
	node* p = list;
	for (int i = 1; i <= n; i++)
	{
		if (p -> next == nullptr)return 0;
		p = p -> next;
	}
	if (p -> next == nullptr)return 0;
	
	node* newNode = new node;
	newNode -> val = data;
	newNode -> next = p -> next;
	p -> next = newNode;
	
	return 1;
}

---

不完全完整版

#include <iostream>
using namespace std;

struct node
{
	int val;
	node* next;
};

node* create()
{
	node* list = new node;
	list -> next = nullptr;
	return list;
}

node* create2(int n, int a[])
{
	node* list = new node;

	node* p = list;
	for (int i = 1; i <= n; i++)
	{
		node* newNode = new node;
		newNode -> val = a[i];
		p -> next = newNode;
		p = p -> next;
	}
	p -> next = nullptr;

	return list;
}

void visit(node* list)
{
	for (auto p = list -> next; p != nullptr; p = p -> next)
	{
		cout << p -> val << " ";
	}
	cout << "\n";
}

bool del(node* list, int n)
{
	if (list == nullptr)return 0;
	node* p = list;
	for (int i = 1; i < n; i++)
	{
		if (p -> next == nullptr)return 0;
		p = p -> next;
	}
	if (p -> next == nullptr)return 0;

	node* cut = p -> next;
	p -> next = cut -> next;
	delete cut;
	
	return 1;
}

bool del2(node* list, int data)
{
	if (list == nullptr)return 0;
	node* p = list;
	for (; p -> next != nullptr; p = p -> next)
	{
		if (p -> next -> val == data)break;
	}
	if (p -> next == nullptr)return 0;

	node* cut = p -> next;
	p -> next = cut -> next;
	delete cut;
	
	return 1;
}

bool insert(node* list, int n, int data)
{
	if (list == nullptr)return 0;
	node* p = list;
	for (int i = 1; i <= n; i++)
	{
		if (p -> next == nullptr)return 0;
		p = p -> next;
	}
	if (p -> next == nullptr)return 0;
	
	node* newNode = new node;
	newNode -> val = data;
	newNode -> next = p -> next;
	p -> next = newNode;
	
	return 1;
}

int main()
{
	int n = 5;
	int a[] = {0, 1, 2, 3, 4, 5};
	
	node* list = create2(n, a);// 根据数组a创建链表
	
	visit(list);// 打印
	
	del(list, 2);// 删除第2个节点
	visit(list);
	
	insert(list, 1, 2);// 恢复
	
	del2(list, 3);// 删除第一个值为3的节点
	visit(list);
	
	insert(list, 2, 25);// 在第2个节点后插入25
	visit(list);
	return 0;
}

静态链表

静态链表，就是用数组来模拟一段内存。用下标代替地址，用 int 代替 * 。以下是一些操作，解释参考上面的动态链表。

#include <iostream>
using namespace std;

int top = 0;

struct node
{
	int val, next;
}a[1000005];

void creat()
{
	int n, x;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		a[++top].val = x;
		a[top].next = -1;
		a[top - 1].next = i;
	}
}

void print()
{
	for (int p = a[0].next; p != -1; p = a[p].next)
	{
		cout << a[p].val << " ";
	}
	cout << "\n";
}

void insert(int n, int x)
{
	int p = a[0].next;
	for (int i = 1; i < n; i++)
	{
		p = a[p].next;
	}
	top++;
	a[top].val = x;
	a[top].next = a[p].next;
	a[p].next = top;
}

void del(int n)
{
	int p = a[0].next;
	for (int i = 1; i < n - 1; i++)
	{
		p = a[p].next;
	}
	a[p].next = a[a[p].next].next;
}

int main()
{
	a[0] = {0, -1};
	creat();
	print();
	insert(2, 4);
	print();
	del(3);
	print();
    return 0;
}

STL：list 库

C++ 的 STL 库中就有链表容器，和栈、队列一样。下面是一些操作。

初始化

就像栈和队列。

list <结构> 链表名;

插入

list 的插入有三种：

1. 链表前：链表.push_front(值);
2. 链表中（迭代器前）：链表.insert(迭代器,值);
3. 链表后：链表.push_back(值)

删除

也有三种：

1. 链表前：链表.pop_front()
2. 链表中：链表.erase(迭代器)
3. 链表后：链表.pop_back()

遍历

可以使用迭代器。迭代器的定义：

list <结构> :: iterator 迭代器名;

可以放到 for 循环里（例）：

for (list <int> :: iterator it = lst.begin(); it != lst.end(); it++)

如果不想定义这么长，可以使用 auto 。例如：

auto it = lst.begin();

注意： auto 定义的变量后一定要赋值。