链表

什么是链表?

链表是一种在存储单元上非连续、非顺序的存储结构，通过链式结构将一堆数据以链的形式进行串联，通过ne指针有效的对链表中的元素进行访问、

链表主要分为两大类

• 单链表
• 双链表

单链表

所谓单链表就是：单向链表，我们将链表中的每个元素称之为结点/节点，单链表中的每个节点是单向的，也就是说，我们无法直接获得某一结点的前面的第一个结点，即:前驱结点。

那么如何去模拟单链表呢？

在开始之前我们需要单链表需要什么？

为了方便遍历，单链表有head必不可少，其次每一个结点我们需要使用idx进行编号

接着设置数组，主要定义两个数组，一个用来存值e，另一个用来关联另一个结点ne

初始化

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

主要实现的功能有以下几个

• 插入元素
  • 头部插入
  • 中间插入
• 删除元素

头部插入

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

在下标为k的位置插入

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

删除元素

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

注意

观察提议是否是对插入的第k个元素进行操作的，如果是的话，传入下标的时候需要- 1，因为我们操作的idx是从0开始的

完整Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int head = -1,idx = 0;
int ne[N],e[N];
void addHead(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

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

void del(int t) {
    ne[t] = ne[ne[t]];
}

int main(){
  	//mem操作可以不写，因为在插入的过程中head为-1的值始终保证在链表的最后
    //memset(ne,-1,sizeof(ne)); 
    int m,k,v;char c;
    cin >> m;
    while(m--) {
        cin >> c;
        if(c == 'H') {
            cin >> v;
            addHead(v);
        }else if(c == 'D') {
            cin >> k;
            if(!k) head = ne[head];
            else del(k - 1);
        }else {
            cin >> k >> v;
            add(k - 1,v);
        }
        
    }
    
    for(int i = head;i != -1;i = ne[i]) cout << e[i] << " ";
    return 0;
}

双链表

双链表，即双向链表，我们可以访问到某一个结点的前驱结点也可以访问到这个结点的后继结点

在双链表中我们需要定义两个单链表中的ne数组，分来获取一个结点的左右结点。

并且我们无需定义头结点，我们可以将0作为头结点，将1作为尾结点

通过r和l数组进行关联

r[0] = 1,l[1] = 0

插入数字的时候其实是在0和1之间进行插入的

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int e[N],l[N],r[N],idx;

void add(int k,int v) {
    e[idx] = v;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void del(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main(){
    int m,k,v;string s;
    cin >> m;
    l[1] = 0,r[0] = 1;
    idx = 2;
    while(m--) {
        cin >> s;
        if(s == "L") {
            cin >> v;
            add(0,v);
        }else if(s == "R") {
            cin >> v;
            add(l[1],v);
        }else if(s == "D") {
            cin >> k;
            del(k + 1);
        }else if(s == "IL") {
            cin >> k >> v;
            add(l[k + 1],v);
        }else {
            cin >> k >> v;
            add(k + 1,v);
        }
        
    }
    
    for(int i = r[0];i != 1;i = r[i]) {
        cout << e[i] << " ";
    }
    return 0;
}