• $Update$ 2024.5.14：完成单链表 + $List$
• $Update$ 2024.5.18：完成$Forward\_list$

链表：

链表，是一种线性数据结构。它的优势我们可以通过与数组的对比来看一下。

---

• 数组，优势在于可以随机访问，调用非常方便。但是劣势也非常明显：①删除和插入的操作中会涉及到大量数据的移动。②定义的空间必须是连续的，这就导致当需要一个较大空间的数组时，系统将面临无法分配处如此之大的连续空间的问题。
• 链表，是一种物理上分散，但逻辑上连续的数据结构。它可以将各个数据存入到内存中任意的空余空 间，哪怕这些空间是分散的。但在空间与空间之间建立一条隧道，即通过指针将空间串联起来，使得我 们可以有序访问。在逻辑上，它便是连续的。当我们需要插入和修改时，只需更改其指针的值即可。

---

一、单链表

🚀️准备操作：

1.定义：

struct node{
	int data;//存储数据 
	node *next;//存下一个数据点的地址 
};

2.申请空间：

p = new node;

3.释放空间：

delete p;

4.节点赋值：

p -> data = x;

🚀️基本操作：

子操作一：构建单链表

inline void create_list()//构建单链表 
{
	int n, x;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> x;
		p = new node;//申请新的空间
		p -> data = x;//将 x 封装成 node 节点
		//反向插入写法，从头部插入
		p -> next = head;//next 指向此时 head 所指向的地址
		head = p;//将 head 指向自己
	}
}

子操作二：输出单链表

inline void print_list()
{
	p = head;
	while(p != NULL){
		cout << p -> data << " ";
		p = p -> next;//让 p 跳到下一个节点 
	}
	cout << "\n";
}

子操作三：插入

inline void insert_list(int k, int x)//在第 k 个节点插入 x
{
	p = new node;
	p -> data = x;
	if(k == 1){//头部插入
		p -> next = head;//next 指向此时 head 指向的节点，即目前第一个节点
		head = p;//head 指向自己，称谓新的首节点
	}
	else{//非头部插入
		int i = 1;
		node *q = head;
		while(i < k - 1){//找到第 k-1 个节点
			q = q -> next;
			i++;
		}
		p -> next = q -> next;
		//q 为第 k-1 个节点，它的 next 指向此时第 k 个节点，将此值赋予 p 的 next 后，p 将成为新的第 k 个节点 
		q -> next = p;//第 k-1 个节点的 next 指向 p，即指向了新的第 k 个节点
	}
}

子操作四：删除

inline void delete_list(int k)
{
	if(k == 1){//头部删除 
		p = head;
		head = p -> next;
		delete p;
	}
	else{
		int i = 1; 
		p = head;
		while(i < k - 1){//p 为第 k - 1 个节点 
			p = p -> next;
			i++;
		}
		node *q = p -> next;//q 为待删除的第 k 个节点 
		p -> next = q -> next;//p 指向第 k + 1 节点 
		delete q;
	}	
}

$In$ $a$ $word$

#include <bits/stdc++.h>
using namespace std;
struct node{
	int data;//存储数据 
	node *next;//存下一个数据点的地址 
};
node *p, *head = NULL;
inline void create_list()//构建单链表 
{
	int n, x;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> x;
		p = new node;//申请新的空间
		p -> data = x;//将 x 封装成 node 节点
		//反向插入写法，从头部插入
		p -> next = head;//next 指向此时 head 所指向的地址
		head = p;//将 head 指向自己
	}
}
inline void print_list()
{
	p = head;
	while(p != NULL){
		cout << p -> data << " ";
		p = p -> next;//让 p 跳到下一个节点 
	}
	cout << "\n";
} 
inline void insert_list(int k, int x)//在第 k 个节点插入 x
{
	p = new node;
	p -> data = x;
	if(k == 1){//头部插入
		p -> next = head;//next 指向此时 head 指向的节点，即目前第一个节点
		head = p;//head 指向自己，称谓新的首节点
	}
	else{//非头部插入
		int i = 1;
		node *q = head;
		while(i < k - 1){//找到第 k-1 个节点
			q = q -> next;
			i++;
		}
		p -> next = q -> next;
		//q 为第 k-1 个节点，它的 next 指向此时第 k 个节点，将此值赋予 p 的 next 后，p 将成为新的第 k 个节点 
		q -> next = p;;//第 k-1 个节点的 next 指向 p，即指向了新的第 k 个节点
	}
} 
inline void delete_list(int k)
{
	if(k == 1){//头部删除 
		p = head;
		head = p -> next;
		delete p;
	}
	else{
		int i = 1; 
		p = head;
		while(i < k - 1){//p 为第 k - 1 个节点 
			p = p -> next;
			i++;
		}
		node *q = p -> next;//q 为待删除的第 k 个节点 
		p -> next = q -> next;//p 指向第 k + 1 节点 
		delete q;
	}	
}
int main()
{

	return 0;
}

二、forward_list标准库

STL中的List是一种单向链表，可高效进行插入和删除。 使用前必须调用forward_list头文件

准备操作：

• 头文件：

#include <forward_list>

• 定义：

forward_list<数据类型> lst;

• 函数：

函数名	功能	时间复杂度
size()	返回表的元素数	$O(1)$
begin()	返回指向表开头的迭代器
end()	返回指向表末尾的迭代器
push_front(x)	在表的开头添加元素x
pop_front()	删除表头元素
insert_after(p, x)	在位置p插入元素x
erase_after(p)	删除位置p的元素
clear()	删除表中所有元素

具体操作与 $list$ 一样，不多赘述，重点看 $list$

三、List标准库

STL中的List是一种双向链表，可高效进行插入和删除。 使用前必须调用list头文件

准备操作：

• 头文件：

#include <list>

• 定义：

list<数据类型> lst;

• 函数：

函数名	功能	时间复杂度
size()	返回表的元素数	$O(1)$
begin()	返回指向表开头的迭代器
end()	返回指向表末尾的迭代器
push_front(x)	在表的开头添加元素x
push_back(x)	在表的末尾添加元素x
pop_front()	删除表头元素
pop_back()	删除表尾元素
insert(p, x)	在位置p插入元素x
erase(p)	删除位置p的元素
clear()	删除表中所有元素

• 重点：

其中需要注意的是，虽然这部分函数的时间复杂度为 $O(1)$，但是插入和删除函数使用前需要先查找到待处理的位置 $p$，这个准备工作所需时间接近 $O(n)$。

$list$ 的运用中要注意输出的操作，需要定义一个迭代器，其含义与指针类似。

int *p; 
list<int>::iterator it;

在上例两个变量定义中，指针p的类型为"int *"，指向的是int类型，同理，迭代器it的类型为 list::iterator，其中iterator和指针定义中的*类似，it所指向的类型为list。

• 代码：

#include <bits/stdc++.h>
using namespace std;
list<int> lst;
list<int>::iterator it;//定义迭代器it 
int main()
{
	int n, x;
	cin >> n;
	for(int i = 1; i <= n; i++) lst.push_back(x);
	for(it = lst.begin(); it != lst.end(); it++){
		//需要注意的是不能用大于小于来判断，必须用不等于 
		cout << *it << " ";//注意it为指针 
	}
	return 0;
}