Python中的循环链表帮助 [英] Help with Circular Linked List in Python

问题描述

我正在尝试制作一个循环的单链列表。我希望能够为一个喜欢的列表修改我的代码，但遇到了一些麻烦。

I'm trying to make a circular singly linked list. I'd like to be able to modify my code for a singly liked list but I'm have some trouble.

对于我的链接列表，我有：

For my linked list I have:

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

到目前为止，对于我的通告列表，我有：

So far for my circular list I have:

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)

我的问题是如何将最后一个元素链接回第一个元素，以便可以横穿？

My question is how do I link the last element back to the first so I can transverse?

推荐答案

循环链表的重点是跳过所有的如果下一个不是None逻辑。开头时，标题指向自身，表示列表为空。不需要创建一个空的 first-首先要做：

The point of a circular linked list is to skip all of the "if next is not None" logic. At the beginning, the head points to itself, indicating that the list is empty. There is no need to create an empty "first" - at the very start do:

self.head = Link(None, None)
self.head.next = self.head

然后在之后插入节点其他节点，只需执行以下操作：

Then to insert a node after some other node, you just do:

def insert_after(insert_node, after_node):
    insert_node.next = after_node.next
    after_node.next = insert_node

要在列表的开头插入，请执行以下操作：

To insert at the beginning of the list, do:

insert_after(node, head)

在之前插入需要迭代以找到之前节点，因为列表仅是单链接的：

Insert before requires iterating to find the "before" node, since the list is only singly linked:

def insert_before(node, before_node):
    loc = head
    while loc.next is not before_node:
        loc = loc.next
    insert_after(insert_node, loc)

要在列表的末尾插入，请执行以下操作：

To insert at the end of the list, do:

insert_before(node, head)

要获取列表中的所有元素，请执行以下操作：

To get all elements of the list do:

current = self.head.next
while current is not self.head:
    # do something with current.data

    # advance to next element
    current = current.next

但是循环列表的真正作用是使其双重链接，因此您可以在插入之前迭代。

But the real power in a circular list is to make it doubly linked, so you can insert before without iterating.

这篇关于Python中的循环链表帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！