常见的链表是利用结构体的，但是利用结构体的链表往往写法复杂，不适合用于算法编程竞赛中。
而数组模拟实现的链表就可以保证代码简洁且高效。

单链表

存储结构

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

其中：

  • head 表示头结点的下标 == first指针

  • e[i] 表示第 i 个节点的值

  • ne[i] 表示下一个节点所在的下标
  • idx 表示下一个新建节点的下标

初始化

头节点指向 -1

下一个节点所在下标设置为0

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

头插法添加节点

常规链表头插法添加节点：

1
2
3
4
5
6
7
8
9
10
11
void CreateHead(LinkNode *&head,ElemType a[],int n) {
    LinkNode *cur;
    head = new LinkNode;
    head->next = NULL;
    for(int i = 0 ; i < n ; i++) {
        cur = new LinkNode;
        cur->data = a[i];
        cur->next = head->next;
        head->next = cur;
    }
}

数组模拟实现：

1
2
3
4
5
6
7
// 头插法添加节点 
void add(int x) {
	e[idx] = x;		// 赋值 
	ne[idx] = head;	// 下一个节点指向头结点 
	head = idx;		// 头结点指向新节点 
	idx++;
}

初始：head = -1, idx = 0

存一个 1 ：e[0] = 1, ne[0] = -1, head = 0, idx = 1

存一个 2 ：e[1] = 2, ne[1] = 0, head = 1, idx = 2

存一个 3 ：e[2] = 3, ne[2] = 1, head = 2, idx = 3

现在：head -> 3 -> 2 -> 1

i = head = 2; e[i] = e[2] = 3; i = ne[head] = ne[2] = 1;

==所以可以看出，head一般是比较大的，i 是在一个减小的过程，最后一个 i = 0==

插入节点

在idx为pos的元素后添加新节点：

1
2
3
4
5
6
7
// 插入节点 
void insert(int pos, int x) {	// 在插入到下标为pos的后一位 
	e[idx] = x;			// 赋值 
    ne[idx] = ne[pos];	// 下一个节点为原本pos位置节点的下一个 
    ne[pos] = idx;		// 原本位置的节点的下一个节点为新节点 
    idx++;
}

在第 k 个元素后添加一个新节点（从0开始数）：

1
2
3
4
5
6
7
8
9
10
11
12
void insert2(int k, int x) {
	int i = head;
	if (head < i) return;
	while (k > 0) {
		i = ne[i];
		k--;
	}
	e[idx] = x;
	ne[idx] = ne[i];
	ne[i] = idx;
	idx++;
}

删除节点

删除idx为pos的节点：

1
2
3
4
// 删除节点 
void remove(int pos) { // 删除pos后面的一个节点 
	ne[pos] = ne[ne[pos]];	
}

遍历链表

while 循环：

1
2
3
4
5
6
7
8
9
// 遍历链表
void disp() {
	int i = head;
	while (i != -1) {
		cout << e[i] << "[" << i << "]->" ;
		i = ne[i];
	}
	cout << endl;
}

for 循环：

1
2
3
4
5
6
void disp() {
    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << "[" << i << "]->";
    }
    cout << endl;
}

完整模拟代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

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

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

// 头插法添加节点 
void add(int x) {
	e[idx] = x;
	ne[idx] = head;
	head = idx++;
}

// 插入节点 
void insert(int pos, int x) {	// 在插入到下标为pos的后一位 
	e[idx] = x;
    ne[idx] = ne[pos];
    ne[pos] = idx++;
} 

// 方式二插入节点
void insert2(int k, int x) {
	int i = head;
	if (head < i) return;
	while (k > 0) {
		i = ne[i];
		k--;
	}
	e[idx] = x;
	ne[idx] = ne[i];
	ne[i] = idx++;
}

// 删除节点 
void remove(int pos) { // 删除pos后面的一个节点 
	ne[pos] = ne[ne[pos]];	
} 

// 遍历链表
void disp() {
    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << "[" << i << "]->";
    }
	cout << endl;
} 

int main () {
	init();
	add(2);
	add(5);
	add(17);
	add(8);
	disp();
	insert(2,18);
	insert2(3,19);
	remove(1);
	disp();
}

循环双链表

存储结构

1
int e[N], l[N], r[N], idx;

其中：

  • e[i] 表示第 i 个节点的值
  • l[i] 表示第 i 个节点的前一个节点所在的下标
  • r[i] 表示第 i 个节点的后一个节点所在的下标
  • idx 表示下一个新建节点的下标

初始化

设置节点0为起始节点，节点1为为尾节点，下标从2开始。不设head指针

==注意：下面这样是不循环双向链表==

1
2
3
4
5
void init() {
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

这样是循环双向链表：

1
2
3
4
5
6
7
void init() {
	r[0] = 1;
	l[0] = 1;
	l[1] = 0;
	r[1] = 0;
	idx = 2;
}

插入

插入到idx为k的节点的右边：

1
2
3
4
5
6
7
8
9
void insert(int k, int x) {
	e[idx] = x;		// 赋值 
	l[idx] = k;		// 新节点的左节点 
	r[idx] = r[k];	// 新节点的右节点 
    // 下面两步要注意顺序，如果先改变了r[k]此时的l[r[k]]就会受到影响
    l[r[k]] = idx;	// 原节点的右节点的左节点 
	r[k] = idx;		// 原节点的右节点 
    idx++;
}

特殊位置插入：

  1. 插入到idx为k的节点的左边：

    insert(l[k], x)

  2. 插入到第一个节点前

    insert(0, x)

    因为初始化时，第一个节点是 0

  3. 插入到最后一个节点后

    insert(l[1], x)

    因为初始化时，最后一个节点是 1

删除

1
2
3
4
void remove(int k) { // 删除idx为k的节点的
	r[l[k]] = r[k];
	l[r[k]] = l[k];
}

遍历

可以分为向左遍历和向右遍历两种。两者的差异就是代码中的 r 和 l

注意一般来说，i = 0 和 i = 1 的节点是不用输出的。

向左遍历：

1
2
3
4
5
6
7
8
9
10
11
void dispL(int k) { // 从下标为k的位置遍历链表 ,向左遍历 
	int i = k;
	while (l[i] != k) {
		if (i != 0 && i != 1)
			cout << e[i] << "[" << i << "]->" ;
		i = l[i];
	} 
	if (i != 0 && i != 1)
		cout << e[i] << "[" << i << "]->" ;
	cout << endl;
}

向右遍历：

1
2
3
4
5
6
7
8
9
10
11
void dispR(int k) { // 从下标为k的位置遍历链表 ,向右遍历 
	int i = k;
	while (r[i] != k) {
		if (i != 0 && i != 1)
			cout << e[i] << "[" << i << "]->" ;
		i = r[i];
	} 
	if (i != 0 && i != 1)
		cout << e[i] << "[" << i << "]->" ;
	cout << endl;
}

完整模拟代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

void init() {
	r[0] = 1;
	l[0] = 1;
	l[1] = 0;
	r[1] = 0;
	idx = 2;
} 

void insert(int k, int x) { // 在idx为k的节点后面插入一个新节点 
	e[idx] = x;		// 赋值 
	l[idx] = k;		// 新节点的左节点 
	r[idx] = r[k];	// 新节点的右节点 
	l[r[k]] = idx;	// 原节点的右节点的左节点 
	r[k] = idx;		// 原节点的右节点 
	idx++;
}

void remove(int k) { // 删除idx为k的节点的
	r[l[k]] = r[k];
	l[r[k]] = l[k];
}

void dispR(int k) { // 从下标为k的位置遍历链表 ,向右遍历 
	int i = k;
	while (r[i] != k) {
		if (i != 0 && i != 1)
			cout << e[i] << "[" << i << "]->" ;
		i = r[i];
	} 
	if (i != 0 && i != 1)
		cout << e[i] << "[" << i << "]->" ;
	cout << endl;
}

void dispL(int k) { // 从下标为k的位置遍历链表 ,向左遍历 
	int i = k;
	while (l[i] != k) {
		if (i != 0 && i != 1)
			cout << e[i] << "[" << i << "]->" ;
		i = l[i];
	} 
	if (i != 0 && i != 1)
		cout << e[i] << "[" << i << "]->" ;
	cout << endl;
}

int main() {
	init();
	insert(0, 1);
	insert(0, 2);
	insert(0, 3);
	dispR(0);
	dispL(0);
}