[数据结构与算法]数据结构基础-单链表

单链表 - xiongyuqing - 博客园 (cnblogs.com)

单链表

采用动态链表的方式：

struct Node
{
    int val;
    Node *next;
}
new Node();	// 非常慢

会非常慢，在算法竞赛中常常采用数组模拟链表，也叫静态链表

head：表示头节点下标

e[N]: 每个节点的值

ne[N]：每个节点的下一个节点编号(下标)

例如下面的链表：

初始化

// head：表示头节点的下标
// e[i]: 表示第i个节点的值
// ne[i]: 表示第i个节点的下一个节点的编号
// idx：当前用到的节点编号
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;	// 表示链表为空
    idx = 0;	// 从0开始分配
}

将值为 x 的新节点插入头节点

1. 先将插入节点指向头节点（下标）
2. 头节点指向新插入的节点（下标）

首先要存储新节点，插入完成后，节点编号++

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lvgHXfxv-1627913441287)(https://img2020.cnblogs.com/blog/1773793/202108/1773793-20210801202454008-528717756.png)]

// 将值为x的节点插入到头节点的后面
void add_to_head(int x)
{
    e[idx] = x;		// 存储新节点
    ne[idx] = head;	// 第一步
    head = idx++;	// 第二步
}

将 x 这个点插入到下标是 k 的节点后面

1. 将插入的节点存储
2. 将插入的节点的下一个节点的下标指向 k 节点的下一个节点
3. 将 k 节点的下一个节点下标指向插入节点
4. 当前用到的节点编号++

// 将值为x的节点插入到第k个节点的后面
void add(int k, int x)
{
    e[idx] = x;		// 存储新节点
    ne[idx] = ne[k];	// 将新节点指向k节点后面的节点
    ne[k] = idx ++;	// 将节点k的下一个节点指向插入节点x
}

删除节点下标是 k 的后面的节点

将下标是 k 的节点的下一个节点指向下下个节点，也就是说跳过 k 后面那个节点

// 将下标是k的节点后面的节点删除
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

例题

826. 单链表 - AcWing题库

#include <iostream>
using namespace std;

const int N = 1e5 + 5;
int e[N], ne[N], head, idx;

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

// 链表头插入元素
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

// 在下标是k的节点后插入值为x的节点
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ++;
}

// 删除下标是k节点后面的点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    init();		// 首先要初始化
    int T, x, k;
    char op;
    cin >> T;
    while(T--)
    {
        cin >> op;
        if(op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            cin >> k;
            if(k == 0) head = ne[head];	// 删除头节点
            else remove(k - 1);
        }
        else{
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for(int i = head; i != -1; i = ne[i])
        cout << e[i] << " ";
    return 0;
}