Создание связанного класса списка и определение методов в python

Question

Я создаю класс LinkedList, и я хочу определить метод удаления, который удалит узел из хвоста.

До сих пор у меня есть:

class LinkedList: 

    def __init__(self): 
     self.head = None 

    def print_things(self): 
     current = self.head 
     while current != None: 
      print(current.get_data()) 
      current = current.get_next() 

    def add(self, item): 
     temp = Node(item) 
     temp.set_next(self.head) 
     self.head = temp  

    def remove(self): 
     current = self.head 
     previous = None 
     found = False 
     while not found: 
      if current.get_data() != current: 
       found = True 
      else: 
       previous = current 
       current = current.get_next() 

     if previous == None: 
      self.head = current.get_next() 
     else: 
      previous.set_next(current.get_next()) 
     return previous 

Используя это, я пытаюсь запустить следующий код:

letter_list = LinkedList() 

my_list.add('d') 
letter_list.add('c') 
letter_list.add('b') 
letter_list.add('a') 

print(letter_list.remove()) 
print(letter_list.remove()) 
print(letter_list.remove()) 

print('l') 
letter_list.print_things() 

который дает выход:

None 
None 
None 
l 
d 

Даже если я ожидалось:

d 
c 
b 
l 
a 

И это класс узел используется:

class Node: 
def __init__(self, init_data): 
    self.data = init_data 
    self.next = None 

def get_data(self): 
    return self.data 

def get_next(self): 
    return self.next 

def set_data(self, new_data): 
    self.data = new_data 

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

Я не могу видеть, что я сделал неправильно в моем методе удалить, но на основе вывода кажется я возвращаюсь в ту переменную.

Answer 1

Ваша проблема в том, что эта проверка всегда верно:

if current.get_data() != current: 

data поле ваших Node объектов никогда не равна узел самих объектов, так что вы никогда не исследовать больше, чем главе списка. Ваш цикл while запускается один раз, устанавливает found в True и уходит previous в None.

правильный способ сделать это было бы:

def remove(self): 
    current = self.head 
    previous = None 
    while current.next is not None: 
     previous = current 
     current = current.next 
    if previous is None: 
     self.head = current.next 
    else: 
     previous.next = current.next 
    return previous 

Некоторые модификации вне фиксируя путь вы обнаружили идущее конец списка:

1) Я не используя свои методы получения и установки , Идиоматический Python не использует геттеры или сеттеры. Вместо этого вы просто определяете нужные атрибуты и получаете доступ к ним в обычном режиме. Если вам нужно будет реорганизовать позже, чтобы добавить особое поведение при настройке или получении, вы используете декоратор property, чтобы изменить настройку или получить реализацию.

2) Сравнение с None должно быть сделано с is или is not. Это один из редких экземпляров в Python, где поиск идентичности объекта верен - None - это одноэлементный объект, поэтому None всегда относится к одному экземпляру. Сравнение сравнений равнозначно потенциально уязвимым для ошибок.

Я упоминаю об этом, потому что единственная причина для написания собственного класса списка в Python - это учебные цели, поэтому вы можете также изучать идиомы языка в этом процессе.

Вышеупомянутые уязвимы для циклических списков, например, вы должны установить, чтобы хвост был next узлу, который уже находится в списке. Существуют различные способы предотвратить это, например, установить атрибут на узлах, чтобы узнать, были ли они уже проверены. Для учебного упражнения, вероятно, достаточно просто убедиться, что вы не создаете такие списки.