python-3.x - 带有 2 个指针的 Python 链表

Question

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

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

    def insert_node(self, node_data):
        node = Node(node_data)

        if not self.head:
            self.head = node
        else:
            self.tail.next = node


        self.tail = node

# Complete the printLinkedList function below.

    def printList(self):
        while self.head is not None:
            print(self.head.data)
            self.head = self.head.next

l = LinkedList()
l.insert_node(5)
l.insert_node(10)
l.insert_node(19)
l.printList()

我正在尝试使用迭代方法实现链表。我有 2 个指针(头，尾)。所以无论如何要避免在没有递归的情况下使用 2 个指针。对于 printList 函数，只使用头指针是一个好习惯。感谢任何反馈

Answer 1

对于您当前的链表实现，self.tail 除了在末尾加速插入之外，实际上没有任何其他用途。您可以像在 printList() 方法中一样，通过让所有链表操作从头指针开始迭代来删除它。请记住，虽然这确实避免了递归，但这本质上迫使所有操作都为 O(n)；不过，这还不错，因为这是典型的简单化链接列表。

让尾指针和节点引用前一个节点的目的是让您也可以支持反向遍历。这是一个简单的优化，但改进仅变为 O(n/2) :对于短列表来说足够好，但在更大的列表中毫无意义。同样，这是在向量化、有序和树状数据结构上使用这种结构的学习点。