我对节点的用法有基本的了解，如node = node.next和self.head，以及诸如
node.next = self.head
self.head = new_node
将new_node中的内容添加到列表的开头。
然而，我对链表类的三个更新方法中的关键逻辑是如何工作的感到困惑(这些行来自的代码在底部):
在add_update ():
new_node.next = node.next
node.next = new_node
在add_before ():
prev_node.next = new_node
new_node.next = node
在remove_node ():
previous_node.next = node.next
对于"add"方法，我很困惑如何一切得到链接，并为"删除";方法，我不明白上面的代码是如何达到预期的删除效果的。
代码如下:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return self.data
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
def add_after(self, target_node_data, new_node):
for node in self:
if node.data == target_node_data:
new_node.next = node.next
node.next = new_node
return
def add_before(self, target_node_data, new_node):
if self.head.data == target_node_data:
return self.add_first(new_node)
for node in self:
if node.data == target_node_data:
prev_node.next = new_node
new_node.next = node
return
prev_node = node
def remove_node(self, target_node_data):
if self.head.data == target_node_data:
self.head = self.head.next
return
previous_node = self.head
for node in self:
if node.data == target_node_data:
previous_node.next = node.next
return
previous_node = node
llist = LinkedList(['a', 'b', 'c', 'd', 'e'])
print(repr(llist))
llist.add_after('c', Node('1'))
print(repr(llist))
llist.add_before('d', Node('2'))
print(repr(llist))
llist.remove_node('c')
print(repr(llist))
下面是您提供的代码的详细注释。希望这能让你对你的问题有所了解。
链表中的节点看起来像这样，例如:
object: node1 node2 node3 node4 node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' 'd' 'e'
name: next
contents: node2 node3 node4 node5 None
链表对象本身看起来(在这个例子中)是这样的:
object: llist
data type: LinkedList
attributes:
name: head
contents: node1
按照约定，链表的第一个节点称为链表的head，最后一个节点(即next属性等于null的节点，或python中的None)称为链表的tail。在我们的例子中，node1是头，node5是尾。
让我们看看你的LinkedList类中的关键方法(__iter__,add_after,add_before和remove_node)。
__iter__方法:
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
这个方法允许我们使用像for node in self这样的语言结构来遍历链表中的节点。在我们的例子中:
node = self.head # assigns `node1` object to variable node
while node is not None: # tests `True`
yield node # makes `node1` available to the caller on call #1
node = node.next # assigns `node2` to variable node
while node is not None: # tests `True`
yield node # makes `node2` available to the caller on call #2
node = node.next # assigns `node3` to variable node
while node is not None: # tests `True`
yield node # makes `node3` available to the caller on call #3
node = node.next # assigns `node4` to variable node
while node is not None: # tests `True`
yield node # makes `node4` available to the caller on call #4
node = node.next # assigns `node5` to variable node
while node is not None: # tests `True`
yield node # makes `node5` available to the caller on call #5
node = node.next # assigns `None` to variable node
while node is not None: # tests `False`
add_after方法:
def add_after(self, target_node_data, new_node):
for node in self:
if node.data == target_node_data:
new_node.next = node.next
node.next = new_node
return
此方法查找其data属性与target_node_data参数匹配的现有节点，并将参数new_node紧接在(或"下游")之后插入。
假设我们在我们的例子中这样使用它:
llist.add_after('c', Node('1'))
那么add_after会这样做:
for node in self: # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'c', so comparison tests False
for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node2.data is 'b', target_node_data is 'c', so comparison tests False
for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3.data is 'c', target_node_data is 'c', so comparison tests True
# we now want to "splice" new_node in place between node and node.next
new_node.next = node.next # assigns `node4` object (which is referenced by node.next) to new_node.next
node.next = new_node # update node.next to now reference new_node
# NOTE: further down in this answer, we will refer to the node object we have added here as node3_1
return # the method has finished its work, so it returns without examining any further downstream nodes
我们的链表示例中的节点现在看起来像这样:
object: node1 node2 node3 node3_1 node4 node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' '1' 'd' 'e'
name: next
contents: node2 node3 node3_1 node4 node5 None
add_before方法:
def add_before(self, target_node_data, new_node):
if self.head.data == target_node_data:
return self.add_first(new_node)
for node in self:
if node.data == target_node_data:
prev_node.next = new_node
new_node.next = node
return
prev_node = node
此方法查找其data属性与target_node_data参数匹配的现有节点，并将参数new_node直接插入(或"上游")之前。
假设我们在我们的例子中这样使用它:
llist.add_before('d', Node('2'))
那么add_before会这样做:
if self.head.data == target_node_data: # handles an edge case: if head is the node we want to add our node before, we need to update our head attribute
return self.add_first(new_node) # this method is not shown in your question, but would simply do this: new_node.next = self.head; self.head = new_node
# NOTE: does not apply in our example
for node in self: # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node1' object in variable prev_node
for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'b', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node2' object in variable prev_node
for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'c', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node3' object in variable prev_node
for node in self: # assigns `node3_1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3_1.data is '1', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node3_1' object in variable prev_node
for node in self: # assigns `node4` object to variable node by calling `__iter__`
if node.data == target_node_data: # node4.data is 'd', target_node_data is 'd', so comparison tests True
# we now want to "splice" new_node in place
prev_node.next = new_node # assigns the object referenced by the new_node argument to the next attribute of 'node3_1'
new_node.next = node # assigns 'node4' to the next attribute of new_node
# NOTE: further down in this answer, we will refer to the node object we have added here as node3_2
return # the method has finished its work, so it returns without examining any further downstream nodes
我们的链表示例中的节点现在看起来像这样:
object: node1 node2 node3 node3_1 node3_2 node4 node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' '1' '2' 'd' 'e'
name: next
contents: node2 node3 node3_1 node3_2 node4 node5 None
remove_node方法:
def remove_node(self, target_node_data):
if self.head.data == target_node_data:
self.head = self.head.next
return
previous_node = self.head
for node in self:
if node.data == target_node_data:
previous_node.next = node.next
return
previous_node = node
此方法查找其data属性与target_node_data参数匹配的现有节点，并将参数new_node直接插入(或"上游")之前。
假设我们在我们的例子中这样使用它:
llist.remove_node('c')
那么remove_node会这样做:
if self.head.data == target_node_data: # handles an edge case: if head is the node we want to remove, we need to update our head attribute
self.head = self.head.next # simply assign self.head.next to the attribute self.head
# NOTE: does not apply in our example
previous_node = self.head # save a reference to the 'node1' object in variable previous_node
for node in self: # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'c', so comparison tests False
previous_node = node # save a reference to the 'node1' object in variable previous_node
for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node2.data is 'b', target_node_data is 'c', so comparison tests False
previous_node = node # save a reference to the 'node2' object in variable previous_node
for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3.data is 'c', target_node_data is 'c', so comparison tests True
previous_node.next = node.next # update the next attribute of 'node2' to refer to the next attribute of 'node3', which is 'node3_1'
# NOTE: the object 'node3' is no longer referenced by the next attribute of any nodes in our linked list, which means it has now been removed
return # the method has finished its work, so it returns without examining any further downstream nodes
我们的链表示例中的节点现在看起来像这样:
object: node1 node2 node3_1 node3_2 node4 node5
data type: Node
attributes:
name: data
contents: 'a' 'b' '1' '2' 'd' 'e'
name: next
contents: node2 node3_1 node3_2 node4 node5 None