帮助解决Python中的循环链表问题

Question

我正在尝试制作一个循环单链表。我想把我的代码改成单链表，但遇到了一些问题。

对于我的链表，我有：

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


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

  def __str__(self):
    a = "["
    current = self.first
    while current != None:
      a += str(current.data) + ', ' 
      current = current.next
    a = a[:-2] + ']'  
    return a  

  def __iter__(self):
    current = self.first
    a = []
    while current != None:
      a += [current.data]
      current = current.next
    return iter(a)

  def __len__ (self):
    current = self.first
    a = []
    while current != None:
      a += [current.data]
      current = current.next
    return len(a)

  def InsertFirst(self, item):
    NewLink = Link(item, self.first)
    self.first = NewLink

  def InsertLast(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 

  def Search(self, item):
    count = 0
    current = self.first
    while current != None:
      count += 1
      if current.data == item:
        return count
      else:
        pass
        current = current.next
    return -1

  def Delete(self, item):
    current = self.first
    previous = self.first

    if (current == None):
      return None

    while (current.data != item):
      if (current.next == None):
        return None
      else:
        previous = current
        current = current.next

    if (current == self.first):
      self.first = self.first.next
    else:
      previous.next = current.next

    return current

到目前为止，我的循环链表是：

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


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

  def __str__(self):
    a = "["
    current = self.first
    while current != None:
      a += str(current.data) + ', ' 
      current = current.next
    a = a[:-2] + ']'  
    return a  

  def InsertLast(self, item):
    NewLink = Link(item)
    current = self.first

    if current == None:
      self.first = NewLink  
      return 

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

我的问题是，怎么把最后一个元素链接回第一个元素，这样我就可以遍历整个链表了？

Answer 1

class cirlist(list):
    def __init__(self,*arg):
        super(cirlist,self).__init__(*arg)
        self.m=super(cirlist,self).__getitem__(0)
        self.Index=0
    def next(self):
        if self.Index>=super(cirlist,self).__len__()-1:
            self.m=super(cirlist,self).__getitem__(0)
        else:
            self.m=super(cirlist,self).__getitem__(self.Index+1)
        if self.Index>super(cirlist,self).__len__()-1:    
            self.Index=super(cirlist,self).index(self.m)+1
        else:
            self.Index=super(cirlist,self).index(self.m)
        return self.m

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 2

创建的时候，last.next = first 是什么意思呢？

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

这可能不是有效的代码。不过，因为在创建的时候你肯定是在列表的最后部分，所以这样做也是可以的。

Answer 3

循环链表的主要目的是省去所有“如果下一个节点不是空的”这种逻辑。在一开始，头节点指向自己，这表示这个链表是空的。我们不需要创建一个空的“第一个节点”——在一开始只需要这样做：

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

不过，循环链表的真正强大之处在于将其变成双向链表，这样你就可以在不遍历的情况下直接在前面插入节点。