'AttributeError' в связанном списке в Python

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

Попробуйте!

Последнее замечание: Python обычно не использует методы получения и установки;они добавляют многословие и не предлагают никакой подлинной защиты, поэтому я пропустил их в своем коде выше.Доверяйте своему клиенту и используйте префиксы подчеркивания для «приватных» переменных.