数据结构-单链表
作者:
成理第一深情
,
2024-01-06 15:32:54
,
所有人可见
,
阅读 65
Acwing 826.单链表
- 用法:邻接表,用于存储图和树
- 注意事项
- 头指针:用于指向第一个结点的指针,头指针是链表必须的
- 头结点:非必要元素。为了操作的统一
e = [0] * 1000010 # 用于存储结点的值
ne = [0] * 1000010 # 用于存储next指针
head, idx = -1, 0 # head是头指针,idx是当前还没有被分配的空间的下标
def add_to_head(x):
global e, ne, head, idx
e[idx] = x
ne[idx] = head
head = idx
idx += 1
def remove(k):
global e, ne, head, idx
ne[k] = ne[ne[k]]
def insert(k, x):
global e, ne, head, idx
e[idx] = x
ne[idx] = ne[k]
ne[k] = idx
idx += 1
if __name__ == "__main__":
m = int(input())
for i in range(m):
opt = input().split(' ')
if opt[0] == "H":
x = int(opt[1])
add_to_head(x)
elif opt[0] == "D":
k = int(opt[1])
if k == 0:
head = ne[head]
else:
remove(k - 1)
else:
k = int(opt[1])
x = int(opt[2])
insert(k - 1, x)
i = head
while i != -1:
print(e[i], end=' ')
i = ne[i]