如何将项添加到链表的末尾?

Question

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
    def add(self, item):
        self.head = Node(item, self.head)
    def is_empty(self):
        return self.head == None

我试过这样做，但是行不通。

from LinkedList import Node, LinkedList
def insert_at_end(linked_list, item):
    linked_list.add(item)

有人能帮忙吗?

Answer 1

您需要遍历链表并在末尾添加一个新节点:

def insert_at_end(linked_list, item):
    if linked_list.is_empty():
        linked_list.add(item)
    else:
        node = linked_list.head
        while node.next is not None:
            node = node.next
        node.next = Node(item, None)

如果链表为空，则重用现有方法在最开始添加节点。

演示:

>>> def print_ll(ll):  # something to print the list
...     node = ll.head
...     while node is not None:
...         print node.item,
...         node = node.next
...
>>> linked_list = LinkedList()
>>> insert_at_end(linked_list, 10)
>>> insert_at_end(linked_list, 42)
>>> insert_at_end(linked_list, 'foo')
>>> print_ll(linked_list)
10 42 foo

Answer 2

一种选择是将__iter__()魔术方法添加到您的LinkedList中，使其可迭代:

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current
            current = current.next
        else:
            raise StopIteration

现在可以遍历节点以添加到尾部:

    def add_tail(self, item):
        if self.is_empty():
            self.add(item)
            return
        # Loop to the end of the list and add the item at the end.
        for node in self:
            pass
        else:
            node.next = Node(item, node.next)

添加__iter__()魔术方法还有一个好处，即您可以使用迭代来构建链表的字符串表示。通过定义__str__()魔术方法，您可以使用print(my_list)来打印类似2->3->5的东西，并且如果您定义了__iter__()方法，则可以很容易地使用列表推导。

请注意，这实际上与@ martinjnpieters给出的答案相同，只是形式不同。您仍然循环遍历列表，直到到达末尾并在末尾添加项目。