链表是指由一系列储存在非连续储存空间 结点组成的储存结构。每个结点由两部分组成：一是储存元素的数据域，一是储存下一个节点地址的指针域。用数组模拟链表可以十分清晰明了地理解这一定义。
在这里，我们简单地介绍一下单链表和双链表两种链表以及用数组模拟实现它们的方式。
单链表是指针方向单向的链表，即a结点的指针域储存着b结点的地址，而b结点的指针域内没有储存a结点的地址。在访问时，可以由a到b访问，而不能由b到a访问。
如图可以清晰地看到，各个结点的指向都是单向的。
Q: 那么，如何用数组来实现它呢？
A: 方法如下
在k结点右侧插入元素x。先将x赋值给该节点的数据域（e[idx]），然后将k结点的指针域赋值给该结点的指针域，最后将k结点的指针域储存的地址改为该节点的地址。
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
删除k结点指向的结点。这里所指的删除，是将k的指向改为该结点的指向。原本为a -> b -> c，改为a -> c，b结点依然存在，只是没有其他结点指向它，也就无法通过链表访问它，我们认为它就再链表上被删除了。
void remove(int k)
{
ne[k] = ne[ne[k]];
}
读取链表。读取链表只用注意一点，在用单指针扫描时不是将指针位置右移，而是将指针移动到该结点指向的位置。
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' '; cout << endl;
主要的操作就是如此，下边看看完整代码：
这是较为经典的写法，我个人认为有些麻烦，head不必单独拿出来写一个函数。但是有助于理解。
#include<iostream>
using namespace std;
const int M = 1e5 + 10;
int m, k, x, idx, head;
int e[M], ne[M];
void init()
{
head = -1, idx = 0;
}
void add_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx++;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
int main()
{
init();
cin >> m;
while (m--)
{
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add_head(x);
}
else if (op == 'D')
{
cin >> k;
if (!k) head = ne[head];
remove(k - 1);
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
这种写法稍微简便一些，用a[0]替代head。
#include<iostream>
using namespace std;
const int M = 1e5 + 10;
int m, k, x, idx, head;
int e[M], ne[M];
void init()
{
ne[0] = -1, idx = 1;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
int main()
{
init();
cin >> m;
while (m--)
{
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add(0, x);
}
else if (op == 'D')
{
cin >> k;
if (!k) head = ne[head];
remove(k);
}
else
{
cin >> k >> x;
add(k, x);
}
}
for (int i = ne[0]; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
双链表顾名思义就是指针方向双向的链表。
可以看到除了头尾他们的指针都是双向的。
它的实现方法如下：
创建开始和结束结点。0表示开始，1表示结束，互相指向，在插入时直接往中间插入即可。
void init()
{
r[0] = 1, l[1] = 0;
idx = 2;
}
插入结点。双链表插入结点的方法与单链表相同，但是操作要稍微复杂一些，这是在k结点右边插入一结点的代码。它要顾及结点左右的结点指向，对于两边都要操作。面临在k结点左边插入一结点时，不必单独在写一个函数，而改成在l[k]结点的右边插入一个结点。
void add(int k, int x)
{
a[idx] = x;
r[idx] = r[k], l[idx] = l[r[k]];
l[r[k]] = idx, r[k] = idx;
idx++;
}
删除节点。删除结点与插入结点同理，我就不多赘述了。
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
输出链表。可以选择输出方向，这里是从左往右输出。
for (int i = r[0]; i != 1; i = r[i])cout << a[i] << ' '; cout << endl;
以下是完整代码：
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], l[N], r[N];
int idx;
int m;
void init()
{
r[0] = 1, l[1] = 0;
idx = 2;
}
void add(int k, int x)
{
a[idx] = x;
r[idx] = r[k], l[idx] = l[r[k]];
l[r[k]] = idx, r[k] = idx;
idx++;
}
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
init();
cin >> m;
while (m--)
{
int k, x;
string op;
cin >> op;
if (op == "L")
{
cin >> x;
add(0, x);
}
else if (op == "R")
{
cin >> x;
add(l[1], x);
}
else if (op == "D")
{
cin >> k;
remove(k + 1);
}
else if (op == "IL")
{
cin >> k >> x;
add(l[k + 1], x);
}
else if (op == "IR")
{
cin >> k >> x;
add(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i])cout << a[i] << ' ';
cout << endl;
return 0;
}
