使用数组模拟链表相对于使用结构指针,拥有更高的效率(省去了动态分配内存的环节)
c++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| #include <iostream> using namespace std;
const int N = 1e6+10;
int head;
int idx;
int e[N];
int ne[N];
void init(){ head = -1; idx = 0; }
void insert_head(int x){ e[idx] = x; ne[idx] = head; head = idx++; }
void insert(int k,int x){ e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; }
void remove(int k){ ne[k] = ne[ne[k]]; }
void out(){ for(int i=head;i!=-1;i=ne[i]){ int value = e[i]; ... } }
|
以下是图解各个操作的执行流程
初始化链表
(打错字了,不是“执行”,是指向)
插入头节点
在k后方插入一个新的节点
删除k的下一个节点