单链表应用

应用1：模拟栈

栈：先进后出。

单链表只操作头节点。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int e[N], ne[N], idx;
int head = -1;

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

void pop(){
    head = ne[head];
}

int main(){
    push(1);
    push(2);
    push(3);

    while(head != -1){
        cout << e[head] << " ";
        head = ne[head];
    }

    return 0;
}

应用2：邻接表

图的存储：

int e[N], ne[N], h[N], idx;

每条边使用链表连接。