Проблема с переборами связанного списка в Python

Question

Я пытаюсь реализовать связанный список с нуля в Python 3.7, и после многих попыток у меня не получается получить метод print_values ​​() для печати всех значений узлов в ожидаемом (последовательном) порядке. На данный момент я не уверен, что проблема в методе append () или методе print_values ​​().

    class Node:
        def __init__(self, node_value):
            self.node_value = node_value
            self.nextNode = None


    class SinglyLinkedList:
        # methods that should be available: get_size, insert_at, append, remove, 
        # update_node_value
        def __init__(self):
            self.head_node = None
            self.tail_node = None
            self.size = 0

        def get_list_size(self):
            """This returns the value for the size variable which get incremented 
               every time a new node is added.
               This implementation is better because it has a running time of O(1) 
               as opposed to iterating through the
               whole list which has a running time of O(n)"""
            return self.size

        def append(self, value):
            new_node = Node(value)
            if self.head_node is None:
                self.head_node = new_node
                self.size += 1
            else:
                while self.head_node.nextNode is not None:
                    self.head_node = self.head_node.nextNode
                self.head_node.nextNode = new_node
                self.size += 1

        def print_values(self):
            current_node = self.head_node
            list_values = []
            while current_node.nextNode is not None:
                list_values.append(current_node.node_value)
                if current_node.nextNode.nextNode is None:
                    list_values.append(current_node.nextNode.node_value)
                current_node = current_node.nextNode
            if list_values is not None:
                print("Linked list: " + str(list_values))
            else:
                print("Linked List is currently empty.")


# Helper code below.
new_ll = SinglyLinkedList()
new_ll.append("alpha")
print(new_ll.get_list_size())
new_ll.append("beta")
print(new_ll.get_list_size())
new_ll.append("gamma")
print(new_ll.get_list_size())
new_ll.append("delta")
print(new_ll.get_list_size())
new_ll.append("epsilon")
print(new_ll.get_list_size())
new_ll.append("zeta")
print(new_ll.get_list_size())
new_ll.print_values()

И все, что я получаю на выходе, это:

1
2
3
4
5
6
Linked list: ['epsilon', 'zeta']

Answer 1

Обычно односвязный список отслеживает только голову. (А не хвост). Так что self.tail_node = None обычно не используется.

При работе с linkedlist или tree вам будет намного проще работать с рекурсией, а не использовать циклы. Циклы работают нормально, если вы просто хотите просмотреть список, но если вы хотите изменить его, я бы порекомендовал рекурсивное решение.

Как говорится, проблема не в вашем print, а в вашем append.

Вы можете НИКОГДА не перемещать головной узел. Вы всегда должны указывать, так что это вызвало проблему:
self.head_node = self.head_node.nextNode

Fix:

def append(self, value):
    new_node = Node(value)
    if self.head_node is None:
        self.head_node = new_node
        self.size += 1
    else:
        temp_head = self.head_node
        while temp_head.nextNode is not None:
            temp_head = temp_head.nextNode
        temp_head.nextNode = new_node
        self.size += 1

Рекурсивное решение:

def append(self, value):
    new_node = Node(value)
    self.size += 1
    self.head_node = self.__recursive_append(self.head_node, new_node)
def __recursive_append(self, node, new_node):
    if not node:
        node = new_node
    elif not node.nextNode:
        node.nextNode = new_node
    else:
        node.nextNode = self.__recursive_append(node.nextNode, new_node)
    return node

Как говорится, я не осознавал этого до тех пор, пока я не переделал ваш отпечаток, поэтому вот более чистый способ печати с использованием генератора питонов, который может вам помочь.

Генераторы - это то, что вы можете использовать с python, которое вы не можете обычно использовать с другими языками программирования, и это делает что-то вроде , превращая связанный список в список значений действительно легко делать:

def print_values(self, reverse=False):
    values = [val for val in self.__list_generator()]
    if values:
        print("Linked list: " + str(values))
    else:
        print("Linked List is currently empty.")

def __list_generator(self):
    '''
    A Generator remembers its state.
    When `yield` is hit it will return like a `return` statement would
    however the next time the method is called it will
    start at the yield statment instead of starting at the beginning
    of the method.
    '''
    cur_node = self.head_node
    while cur_node != None:
        yield cur_node.node_value # return the current node value

        # Next time this method is called
        # Go to the next node
        cur_node = cur_node.nextNode

Отказ от ответственности: Генератор хорош, но я сделал это только таким образом, чтобы соответствовать тому, как вы это делали (то есть получать список из списка ссылок). Если список не важен, но вы просто хотите вывести каждый элемент в связанный список, я бы просто сделал это следующим образом:

def print_values(self, reverse=False):
    cur_node = self.head_node
    if cur_node:
        print('Linked list: ', end='')
        while cur_node:
            print("'{}' ".format(cur_node.node_value), end='')
            cur_node = cur_node.nextNode
    else:
        print("Linked List is currently empty.")

Answer 2

Я согласен с ошибкой - ответ синтаксического раскаяния в том, что проблема в дополнении и теле цикла while ... вот пример в псевдокоде:

append 0:
  head = alpha

append 1:
  //skip the while loop
  head = alpha
  next = beta

append 2:
  //one time through the while loop because next = beta
  head = beta
  //beta beta just got assigned to head, and beta doesn't have next yet...
  next = gamma

append 3:
  //head is beta, next is gamma...the linked list can only store 2 nodes
  head = gamma //head gets next from itself
  //then has no next
  next = delta

...etc.