A static linked list

Recently I saw the class of YXC, it is said that the linked list implementation in the algorithm contest is to use the array to simulate the linked list, because the structure plus pointer way, will use the new operation, very slow! , so arrays are used to simulate linked lists.

Initialize the static linked list (hereinafter referred to as the linked list) : IDx represents the node to which it is currently pointing (the serial number of the node), E [IDx] represents the value field of the linked list node, ne[IDx] represents the pointer field of the linked list node.

The big guy’s example problem really can’t run. Put it aside for now. I have to find a good way to debug c++

Standard code:

#include<iostream> using namespace std; const int N=100010; int idx,head,n[N],ne[N]; int a; void add_head(int x){ n[idx]=x; ne[idx]=head; head=idx++; } void add(int k,int x){ n[idx]=x; ne[idx]=ne[k]; ne[k]=idx++; } void remove(int k){ ne[k]=ne[ne[k]]; } int main(){ head=-1; idx=0; cin>>a; while(a--){ string op; int k,x; cin>>op; if(op=="D") { cin>>k; if(! k)head=ne[head]; remove(k-1); } else if(op=="H") { cin>>x; add_head(x); } else if(op=="I"){ int k,x; cin>>k>>x; add(k-1,x); } } for(int i=head; i! = 1; i=ne[i]) cout<<n[i]<<" "; return 0; } the author: wuog links: https://www.acwing.com/solution/content/3472/ source: AcWing copyright owned by the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.Copy the code