单链表
#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;
//初始化单链表
void init()
{
head = -1;
idx = 0;
}
//在头节点后插入一个节点
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
//在第k个节点后插入一个节点
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//删除第k个节点后面的一个节点
void remove(int k)
{
ne[k] = ne[ne[k]];
}
//从头打印所有节点的值
void printAllNode()
{
int current = head;
while (current != -1)
{
cout << e[current] << " ";
current = ne[current];
}
}
int main()
{
init();
add_to_head(3);
add_to_head(1);
add_to_head(2);
add(2,5);
remove(2);
printAllNode();
return 0;
}
双链表
#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], l[N], r[N], idx;
//初始化双链表
void init()
{
r[0] = 1;
l[1] = 0;
idx = 2;
}
//在第k个节点的右边插入x
//想在第k个节点的左边插入x需使k = l[k]
void add(int k, int x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
//删除第k个节点
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
//正向遍历输出
void printForward()
{
int current = 0;
while (true)
{
current = r[current];
if (current == 1)
break;
cout << e[current] << " ";
}
}
//反向遍历输出
void printBackward()
{
int current = 1;
while (true)
{
current = l[current];
if (current == 0)
break;
cout << e[current] << " ";
}
}
int main()
{
init();
add(0, 1);
add(2, 2);
add(3, 3);
printForward();
cout << "\n";
printBackward();
cout << "\n";
remove(2);
printForward();
return 0;
}