Python中链表中的'AttributeError'

Question

此代码处理从Python中链接列表中删除重复项。这个问题似乎是在remove函数中。

class Node(object):
  def __init__(self, data = None, next_node = None):
    self.next_node = next_node
    self.data = data

  #get data at that location

  def get_data(self):
    return self.data

  #get next element in linked list

  def get_next(self):
    return self.next_node

  #point to node specified by argument

  def set_next(self, new_next):
    self.next_node = new_next

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

  #insert element in linked list

  def insert(self, data):
    new_node = Node(data)
    new_node.set_next(self.head)
    self.head = new_node

  #remove duplicates

  def remove(self):
  #point to head
    current = self.head
    previous = None
    removed = False
  #variable to compare the current data with the rest
    new = current
    new = new.get_next()
  #while current is not None
    while current:
      if current.get_data() != new.get_data():
        previous = new
        new = new.get_next()
  #if same data, delete extra node from list
      else:
        removed = True
  #if only one element in list
        if previous is None:
          self.head = new.get_next()
        else:
          previous.set_next(new.get_next())
          new = new.get_next()
  #if 'new' reaches end of list, do this
      if new is None:
        current = current.get_next()
        previous = current
        new = current
        new = new.get_next()
    if not removed:
      print("No duplicates!")

  #print resulting linked list

  def print_result(self):
    current = self.head
    while current:
      print(current.get_data(), end = " ")
      current = current.get_next()

（我忽略了代码中的'函数调用'部分）。

我在if（在while current:函数中）的第一个remove语句中得到属性错误说：

Traceback (most recent call last):
File "python", line 64, in <module>
File "python", line 26, in remove
AttributeError: 'NoneType' object has no attribute 'get_data'

我无法理解哪个是None以及为什么。任何帮助是极大的赞赏！

Answer 1

假设您的指数运行时间正常，但您的一般方法看起来是正确的，但有些细节会导致崩溃。这是我发现的一对夫妇：

1. 如果列表长度为1，if current.get_data() != new.get_data():将崩溃，因为new是None。
2. 这些线：

   current = current.get_next()
   previous = current
   new = current
   new = new.get_next() # boom!

   到达列表末尾时会崩溃。 current是最后一个节点，你得到下一个节点，这是None，然后尝试None.get_next()。

要解决这些问题，请一次在列表中查看一个节点，并在每次None时检查next以避免崩溃。取消链接同样如此：通过将prev保持在原位并将prev.next_node和curr设置为curr.next，一次取消链接一个节点，然后在执行任何其他操作之前测试curr是否为None。

这是一个简单的工作版本：

def remove(self):
  curr = self.head

  while curr:
    runner = curr.next_node
    prev = curr

    while runner:
      if runner.data == curr.data:
        prev.next_node = runner.next_node
      else:
        prev = runner

      runner = runner.next_node

    curr = curr.next_node

我们的想法是使用curr按节点逐个遍历列表。对于每个节点，创建一个runner和prev，它将逐个节点地遍历列表的其余部分并取消链接与curr匹配的任何节点。

还有一种使用set（交易空间速度）的线性方法：

def remove_linear(self):
  seen = set()
  curr = self.head
  prev = None

  while curr:
    if curr.data not in seen:
      seen.add(curr.data)
      prev = curr
    else:
      prev.next_node = curr.next_node

    curr = curr.next_node

Try it!

最后一点：Python通常不使用getter和setter;它们增加了冗长，并没有提供任何真正的保护，所以我在上面的代码中省略了它们。信任您的客户端并使用下划线前缀作为“私有”变量。