带有 2 个指针的 Python LinkedList

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(：对于短列表来说足够好，但在更大的列表中毫无意义。同样，这是使用这种结构而不是矢量化、有序和树状数据结构的学习点。

Answer 2

def getList(self):
data = []
currentNode = self.head
while currentNode is not None:
data.append( currentNode.data )
currentNode = currentNode.next
return data