当前位置： 文江博客话题详情

我不了解节点在链接列表中的工作方式

发布于 2025-01-28 20:45:56 字数 1457 浏览 7 评论 0原文

原文

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（1）

绝情姑娘 2025-02-04 20:45:56

这是您提供的代码的详细注释。希望这将为您的问题要问的事情提供一些见解。

例如，链接列表中的节点看起来像：

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> head链接列表和最后一个节点（即带有Next属性等于null或none in Python中的节点）被称为tail 。在我们的示例中，node1是头部，node5是尾巴。

让我们看一下linkedlist类中的关键方法（__ ITER __，add_after，add_before and code> remove_node ）。

__ ITER __方法：

    def __iter__(self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

此方法使我们可以在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_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方法：< /strong>

    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

emover_node方法：< /strong>

    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

Here is a detailed annotation of the code you have supplied. Hopefully this will provide some insight into the things your question is asking about.

The nodes in a linked list look like this, for example:

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

The linked list object itself looks (in this example) like this:

object:        llist
data type:     LinkedList
attributes:
    name:      head
    contents:  node1

By convention, the first node of a linked list is known as the head of the linked list, and the last node (namely, the node with a next attribute equal to null, or None in python) is known as the tail of the linked list. In our example, node1 is the head and node5 is the tail.

Let's look at the key methods in your LinkedList class (__iter__, add_after, add_before and remove_node).

The __iter__ method:

    def __iter__(self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

This method allows us to use language constructs like for node in self to iterate through the nodes in the linked list. In our example:

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`

The add_after method:

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

This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately after (or "downstream" of) the matching node.

Suppose we use it like this for our example:

llist.add_after('c', Node('1'))

Then add_after would do this:

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

The nodes in our linked list example now look like this:

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

The add_before method:

    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

This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately before (or "upstream" of) the matching node.

Suppose we use it like this for our example:

llist.add_before('d', Node('2'))

Then add_before would do this:

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

The nodes in our linked list example now look like this:

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

The remove_node method:

    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

This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately before (or "upstream" of) the matching node.

Suppose we use it like this for our example:

llist.remove_node('c')

Then remove_node would do this:

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

The nodes in our linked list example now look like this:

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
回复 原文
~没有更多了~

关于作者

巴黎夜雨

暂无简介

文章
评论
28 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

狼性发作

文章 0 评论 0

美煞众生

文章 0 评论 0

黑凤梨

文章 0 评论 0

慕巷

文章 0 评论 0

virou

文章 0 评论 0

两仪

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文