循环链表的要点是跳过所有“如果下一个不是 None”逻辑。一开始,头指向自身,表明链表为空。没有必要创建一个空的“第一个” - 从一开始就执行以下操作:
self.head = Link(None, None)
self.head.next = self.head
然后要在其他节点之后插入一个节点,只需执行以下操作:
def insert_after(insert_node, after_node):
insert_node.next = after_node.next
after_node.next = insert_node
要在列表的开头插入,请执行以下操作:
insert_after(node, head)
在之前插入需要迭代来查找“之前”节点,因为该列表只是单向链接:
def insert_before(node, before_node):
loc = head
while loc.next is not before_node:
loc = loc.next
insert_after(insert_node, loc)
要在列表末尾插入,请执行以下操作:
insert_before(node, head)
要获取列表的所有元素,请执行以下操作:
current = self.head.next
while current is not self.head:
# do something with current.data
# advance to next element
current = current.next
但循环列表的真正威力在于使其成为双向链接,因此您可以在不迭代的情况下插入之前。