单链表

⬅ 返回

1、静态链表实现(数组)

以下两种方法本质相同

1.1、结构体方法

struct Snode{
	int value;
	int next;
};

1.2、数组方法

int val[N],nex[N],dit=1,head;
//val[i]表示的是结点i处的值
//nex[i]表示的是结点i的下一个结点

2、动态链表

class Node{
public:
    int val;
    Node* next;
};

new的底层涉及内存分配，调用构造函数，指针转换等多种复杂且费时的操作。在算法比赛中，经常碰到操作在10w级别的链表操作，如果使用结构体这种操作，是无法在算法规定时间完成的。

3、例题

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 个插入的数后面的一个数； k
3. 在第 个插入的数后插入一个数。 k

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

4、代码

#include <iostream>
using namespace std;
const int N = 1e6+10;
struct Snode{
	int value;
	int next;
};
Snode a[N]; 
int head=-1;
int dit=1;
 
int main(){
	
	int m;
	cin>>m;
	while(m--)
	{
		char c;cin>>c;
		-------------------------------------------------
		if(c=='H')
		{
			int x;
			cin>>x;	
			a[dit].value=x;
			a[dit].next=head;
			head=dit;
			dit++;
		}else if(c=='D'){
			int k;
			cin>>k;
			if(k)
			{
				a[k].next = a[a[k].next].next;
			}else{
				head=a[head].next;
			}
		}else if(c=='I'){
			int k,x;
			cin>>k>>x;
			a[dit].value=x;
			a[dit].next=a[k].next;
			a[k].next=dit;
			dit++;
		}
		----------------------------------------------------------
	}
	for(int i=head;i!=-1;i=a[i].next)
	{
		cout<<a[i].value<<" ";
	}
	
	
}