数组模拟#

要包含两个方面的东西，用下标来关联：

1. valueN（值）
2. nextN（下标）

代码模板#

# head
# e:value
# ne:next
# idx:当前用到的地址

# 初始化
def init():
    head = -1
    idx = 0 # 可以从0开始分配

# x值插入头节点
def add_to_head(x):
    e[idx] = x
    ne[idx] = head
    head = idx
    idx += 1

# 将x值插入下标为k的值的后面
def add(x,k):
    e[x] = idx
    ne[x] = ne[k]
    ne[k] = idx
    idx += 1

# 将k下标之后的一个点删掉
# 有一点容易写错
def remove(k):
    ne[k] = ne[ne[k+1]]

例题：B3631 单向链表#

但是这道题的实现跟acwing讲的还是不一样。题干的要求是在对应的元素后面添加、查询、删除数字，如果用acwing的做法还需要去遍历找到那个位置。这里的优化是直接用下标代替数值，只需要一个ne数组就可以实现。

# 改进：用下表代替数值，直接在O(1)时间内完成
import sys
input = lambda:sys.stdin.readline()
N = 10**6+1
ne = [-1] * N
head = 1
q = int(input())
for _ in range(q):
	ii = list(map(int,input().split()))
	if ii[0] == 1:
		ne[ii[2]] = ne[ii[1]]
		ne[ii[1]] = ii[2]
	elif ii[0] == 2:
		print(ne[ii[1]] if ne[ii[1]] != -1 else 0)
	else:
		ne[ii[1]] = ne[ne[ii[1]]]

洛谷上的一个pypy3满分解法是用字典，跟我用数值直接对应下标的原理是相同的。

还有直接用列表的函数的。用数组确实会快很多。

n = int(input())

l = [1, 0]

for i in range(n):
    k = [int(x) for x in input().split()]
    if k[0] == 1:
        (x, y) = k[1:3]
        l.insert(l.index(x) + 1, y)
    elif k[0] == 2:
        print(l[l.index(k[1]) + 1])
    else:
        del(l[l.index(k[1]) + 1])

数组模拟#

相比于单链表：一个指向前，一个指向后

1. valueN（值）
2. leftN（下标）
3. rigthN（下标）

同时，对于节点下标，0表示最左侧，1表示最右侧

代码模板#

# e:value
# l:left
# r:right
# idx:当前用到的地址
# 0表示最左侧，1表示最右侧

# 初始化
def init():
    r[0] = 1
    l[1] = 0
    idx = 2 # 0和1已经被占用了

# 在k节点的右边插入一个点
def add(k,x):
    e[idx] = x
    # 先处理新的点，r[k]最后才能改变
    l[idx] = k
    r[idx] = r[k]
    l[r[k]] = idx
    r[k] = idx

# 在k节点的左边插入一个点等价于在k左边节点的右边插入一个点
def add_left(k,x):
    add(l[k],x)

# 删除第k个点
def remove(k):
    r[l[k]] = r[k]
    l[r[k]] = l[k]

例题：B4324 【模板】双向链表#

为了判断链表是否为空，在1和N前后都添加了0和N+1。看了几个基本上都是用的r[head] == n+1判断的，应该还不错！

import sys
input = lambda:sys.stdin.readline()
n,m = map(int,input().split())
l = [(i-1) for i in range(n+2)]
r = [(i+1) for i in range(n+2)]
head = 0
for _ in range(m):
	od = list(map(int,input().split()))
	if od[0] == 1 and od[1] != od[2]:
		# 删除xs
		r[l[od[1]]] = r[od[1]]
		l[r[od[1]]] = l[od[1]]
		# 插入到y左边
		r[l[od[2]]] = od[1]
		l[od[1]] = l[od[2]]
		r[od[1]] = od[2]
		l[od[2]] = od[1]
	elif od[0] == 2 and od[1] != od[2]:
		# 删除x
		r[l[od[1]]] = r[od[1]]
		l[r[od[1]]] = l[od[1]]
		# 插入到y右边
		r[od[1]] = r[od[2]]
		l[r[od[2]]] = od[1]
		r[od[2]] = od[1]
		l[od[1]] = od[2]
	else:
		r[l[od[1]]] = r[od[1]]
		l[r[od[1]]] = l[od[1]]
if r[head] == n+1:
	print("Empty!")
	exit()
while r[head] != n+1:
	print(r[head],end = ' ')
	head = r[head]

数组模拟#

栈从下标为1开始加入。

1. valueN
2. 栈顶

代码模板#

# value:stk[N]
# 栈顶

# 初始
tt = 0

# 插入
stk[++tt] = x

# 栈顶元素
stk[tt]

# 弹出
tt -= 1

# 判断栈是否为空
if tt > 0: not empty
else:empty

例题：B3614 【模板】栈#

import sys
input = lambda:sys.stdin.readline()
t = int(input())
for _ in range(t):
	n = int(input())
	stk = [0] * (n+1)
	tt = 0
	for i in range(n):
		od = list(input().split())
		if od[0] == "push":
			tt += 1
			stk[tt] = od[1]
		elif od[0] == "query":
			if tt > 0: print(stk[tt])
			else: print("Anguei!")
		elif od[0] == "pop":
			if tt > 0: tt -= 1
			else: print("Empty")
		else: print(tt)

数组模拟#

队列从下标为0开始加入。

1. valueN
2. 头
3. 尾

代码模板#

# value:q[N]
# 头:hh
# 尾:tt

# 初始化
tt = -1
hh = 0

# 拆入元素
q[++tt] = x

# 弹出
hh += 1

# 判断是否为空
if hh <= tt： not empty
else:empty

# 取出队头或者队尾元素
q[hh]
q[tt]

例题：B3616 【模板】队列#

注意区分清楚hh为队首，tt为队尾，在队尾加入，在队首输出

import sys
input = lambda:sys.stdin.readline()
n = int(input())
q = [0] * n
hh = 0
tt = -1
for i in range(n):
	od = list(map(int,input().split()))
	if od[0] == 1:
		tt += 1
		q[tt] = od[1]
	elif od[0] == 2:
		if hh <= tt: hh += 1
		else: print("ERR_CANNOT_POP")
	elif od[0] == 3:
		if hh <= tt: print(q[hh])
		else: print("ERR_CANNOT_QUERY")
	else:
		print(tt-hh+1)