AcWing 827. 双链表
原题链接
简单
作者:
弈剑观星
,
2021-05-08 12:17:14
,
所有人可见
,
阅读 211
python3双链表类实现
class DoublyLinkedList: # 双链表类
def __init__(self, length=100010):
self.length = length
self.val = [0] * self.length
self.left = [0] * self.length
self.right = [0] * self.length
self.right[0] = 1
self.left[1] = 0
self.cur = 2
def add(self, k, x):
self.val[self.cur] = x
self.right[self.cur] = self.right[k]
self.left[self.cur] = k
self.left[self.right[k]] = self.cur
self.right[k] = self.cur # 注意赋值顺序
self.cur += 1
def delete(self, k):
self.right[self.left[k]] = self.right[k]
self.left[self.right[k]] = self.left[k]
m = int(input())
linked = DoublyLinkedList()
for _ in range(m):
s, *p = input().split()
if s == 'L':
x = int(p[0])
linked.add(0, x)
elif s == 'R':
x = int(p[0])
linked.add(linked.left[1], x)
elif s == 'D':
k = int(p[0])
linked.delete(k + 1)
elif s == 'IL':
k, x = map(int, p)
linked.add(linked.left[k+1], x)
else:
k, x = map(int, p)
linked.add(k+1, x)
i = linked.right[0]
while i != 1:
print(linked.val[i], end=' ')
i = linked.right[i]