我不明白节点在链表中是如何工作的
I don't understand how nodes work in a linked list
我对 node = node.next 和 self.head 以及
等节点的用法有基本的了解
node.next = self.head
self.head = new_node
将 new_node 中的任何内容添加到列表的开头。
但是，我对链表class的三个更新方法中的关键逻辑如何工作感到困惑（这些行的代码在底部）：
在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”方法，我对所有内容如何链接感到困惑，对于“remove”方法，我不明白上面的代码如何达到预期的删除效果。
代码如下：
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的节点， or None in python) 被称为链表的tail。在我们的示例中，node1 是头部，node5 是尾部。
让我们看看您的 LinkedList class 中的关键方法（__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
我对 node = node.next 和 self.head 以及
node.next = self.head
self.head = new_node
将 new_node 中的任何内容添加到列表的开头。
但是，我对链表class的三个更新方法中的关键逻辑如何工作感到困惑（这些行的代码在底部）：
在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”方法，我对所有内容如何链接感到困惑，对于“remove”方法，我不明白上面的代码如何达到预期的删除效果。
代码如下：
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的节点， or None in python) 被称为链表的tail。在我们的示例中，node1 是头部，node5 是尾部。
让我们看看您的 LinkedList class 中的关键方法（__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