用数组模拟链表

用数组模拟链表

用数组模拟链表

为什么用数组模拟链表呢，因为数组模拟的链表运行的速度快，写题方便，再笔试中常用。

1.我们可以用head表示头节点，e[n]表示节点所存入的值，ne[n]表示suo存入的下一个点的地址，也就是数组的下标。

head头节点指向第一个节点，e[0]表示0号节点的值，ne[0]表示存入的下一个节点的地址，为1；

这里数组的下标为节点的地址。

 

 1.e[i]存入节点所存的值，ne[i]表示下一个节点的地址，也就是数组的下标，idx表示当前用到了哪一个地址。head为头指针

2.先进行初始化，一开始链表为空，把head初始化为-1，idx初始化为0，表示从零号点开始分配内存

void init(){
    head=-1;
    idx=0;
}

3.从头节点后插入节点

 

void add1(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}

第一步将e[idx]=x;,第二步将指针指向head指向的地址，最后head指向idx，idx++分配一个新的内存，开创一个节点。

将节点插入到k节点的后面

 

void add2(int k,int x){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}

与插入到头节点后面相同

删除k后面的节点

 

void remove(int k){
    ne[k]=ne[ne[k]];
    
}

ne[k]为k节点下一个节点的地址，ne【ne【k】】就是k点下一个下一个的地址