使用循环 link 列表插入功能

Question

这是我的代码，每次我调用插入函数时，我都会得到一个输出：<__main__.CircularList object at 0x10597fd68>。我正在尝试使用插入函数通过用 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

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

所以您首先需要决定您希望在何处插入项目？作为第一项？或者在迭代的情况下要达到的最后一项？

如果你想select最后一个，你首先必须在内存中存储第一个项：

first = current

（你当然也可以使用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

使用循环 link 列表插入功能

using circular link list insert function

python

circular-list