双链表

⬅ 返回

1、静态链表

struct Snode{
	int previous;
	int value;
	int next;
};

初始化

a[0].next=1;
a[1].previous=0;

a[0].next指向第一个元素

a[1].previous指向最后一个元素

从a[0].next开始遍历到a[1]结束

例题

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

在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

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

代码

#include <iostream>
using namespace std;
const int N = 1e6+10;
struct Snode{
	int previous;
	int value;
	int next;
};
Snode a[N];
int dit=2;
 
int main(){
	int m;
	cin>>m;
	a[0].next=1;
  a[1].previous=0;
	for(int i=0;i<m;i++)
	{
		string str;
		cin>>str;
		if(str=="L")
		{
			int x;
			cin>>x;
			a[dit].value=x;
			a[dit].next=a[0].next;
			a[dit].previous=0;
			a[a[0].next].previous=dit; 
			a[0].next=dit;
			
			dit++;
			
		}else if(str=="R"){
			int x;
			cin>>x;
			a[dit].value=x;
			a[dit].previous=a[1].previous;
			a[dit].next=1;
			a[a[1].previous].next=dit;
			a[1].previous=dit;
			dit++;
			
		}else if(str=="D"){
			int k;
			cin>>k;
			k+=1;
			a[a[k].previous].next=a[k].next;
			a[a[k].next].previous=a[k].previous;
			
		}else if(str=="IL"){
			int k,x;
			cin>>k>>x;
			k+=1;
			a[dit].value=x;
			a[dit].next=k;
			a[dit].previous=a[k].previous;
			a[a[k].previous].next=dit;
			a[k].previous=dit;
			dit++;
			
		}else if(str=="IR"){
			int k,x;
			cin>>k>>x;
			k+=1;
			a[dit].value=x;
			a[dit].next=a[k].next;
			a[dit].previous=k;
			a[a[k].next].previous=dit;
			a[k].next=dit;
			dit++;	
		}
	}
	-----------------------------------------------------
	for(int i=a[0].next;i!=1;i=a[i].next)//从a[0].next即第一个元素开始遍历，到i=1时遍历结束
			cout<<a[i].value<<" ";
	
	
}