数据结构

链表与邻链表

struct Node
{
    int val;
    Node *next
}

new Node(); // 十分慢 

数组模仿单链表 动态链表

int head; // 头节点
int e[N]; // 值
int ne[N]; //next 指针
int idx; // 数组用到第几个点

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数 a
void insert_head(int a)
{e[idx] = a;
    ne[idx] = head;
    head = idx;
    idx++ ;
}

// 将头结点删除，须要保障头结点存在
void remove()
{head = ne[head];
}

// 将 a 插入到第 k 个点前面
void add(int k, int a)
{e[idx] = a;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}
// 将下标是 k 的后边的点删掉
void remove(int k)
{ne[k] = ne[ne[k]];
}

数组模仿双链表（优化某些问题）

每一个点有两个指针

int e[N];
int l[N];
int r[N];

// 初始化
void init()
{
    // 0 示意左端点（head），1 示意右端点（tail）r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 在下标是 k 的点的左边，插入 x
void add(int k, int x)
{e[idx] = x;
    r[idx] = r[k]; // 不能用 k + 1
    l[idx] = k;
    
    l[r[k]] = idx; // 不能用 k + 1
    r[k] = idx;
    
}

// 在 k 的右边插入 x
add(l[k], x);

// 删除第 k 个点
void remove(int k)
{r[l[k]] = r[k];
    l[r[k]] = l[k];
}

邻接表 存储树和图

栈与队列

栈（先进后出）

队列（先进先出）

kmp