数组模拟实现链表_数组模拟链表

单链表

存储结构

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

其中：

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

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

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

• idx 表示下一个新建节点的下标

初始化

头节点指向 -1

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

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

头插法添加节点

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

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
8
9
10
11

数组模拟实现：

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

初始：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的元素后添加新节点：

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

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

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++;
}
1
2
3
4
5
6
7
8
9
10
11
12

删除节点

删除idx为pos的节点：

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

遍历链表

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

完整模拟代码

#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;		// 头结点指向 
	idx++;
}

// 插入节点 
void insert(int pos, int x) {	// 在插入到下标为pos的后一位 
	e[idx] = x;			// 赋值 
    ne[idx] = ne[pos];	// 下一个节点为原本pos位置节点的下一个 
    ne[pos] = idx;		// 原本位置的节点的下一个节点为新节点 
    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;
	idx++;
}

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

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

int main () {
	init();
	add(2);
	add(5);
	add(17);
	add(8);
	disp();
	insert(2,18);
	insert2(3,19);
	remove(1);
	disp();
}
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
67
68
69
70

循环双链表

存储结构

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

其中：

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

初始化

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

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

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

这样是循环双向链表：

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

插入

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

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
2
3
4
5
6
7
8
9

特殊位置插入：

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

   insert(l[k], x)

2. 插入到第一个节点前

   insert(0, x)

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

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

   insert(l[1], x)

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

删除

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

遍历

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

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

向左遍历：

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

完整模拟代码

#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);
}
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