使用循环链接列表插入函数

Question

这是我的代码，每次调用insert函数时，都会得到一个输出：<__main__.CircularList object at 0x10597fd68>。 我试图使用insert函数通过使用for循环调用它来实际创建循环链表。在

class Link (object):
  def __init__ (self, data, next = None):
    self.data = data
    self.next = next

class CircularList(object):
  def __init__(self):
    self.first = None

  # Insert an element in the list
  def insert ( self, item ):
    newLink = Link (item)
    current = self.first

    if (current == None):
      self.first = newLink
      return

    while (current.next != None):
      current = current.next

    current.next = newLink
    newLink.next = self.first    

Answer 1

你的实施首先是错误的。如果使用if循环，则应将.next值明显设置为自身，否则不会有圆：

if (current == None):
    self.first = newLink
    newLink.next = newLink
    return

但接下来有一个重要的问题：通过迭代循环列表，您永远不会结束迭代，因为很明显，从您返回的那一刻起，您将执行另一轮操作。在

因此，您首先需要决定将项目插入到哪里？作为第一项？或者在迭代的情况下最后到达的项目？在

如果要选择最后一个，则必须首先将第一个项存储在内存中：

^{pr2}$

（您当然也可以使用self.first），但这可能会有点效率低下。）

下一步，遍历项目列表，每次检查current的next是否是第一个：在这种情况下，我们已经迭代了整个回合，因此：

while (current.next != first):
    current = current.next

现在，如果current.next指向first，我们就知道我们已经完成了一个完整的旅程。现在我们只需要执行一些指针记账：

current.next = newLink
newLine.next = first

所以完整的代码是：

def insert ( self, item ):
    newLink = Link (item)
    current = self.first

    if (current == None):
        self.first = newLink
        newLink.next = newLink
        return

    first = current
    while (current.next != first):
        current = current.next

    current.next = newLink
    newLink.next = first