链表节点分配意外地更新了多个变量



我是链表的新手,刚刚开始了解链表背后的功能。我有一个关于分配节点的问题。我相信这个类似的问题已经重复过了(如果是的话,请告诉我),但我在看关于链表的视频,我没有看到他们解释我在这里要问什么。

问题是,当我有一个主节点head,并且我在类LinkedList的方法内分配了一个临时node.next时,为什么head也会被分配?

我知道你可能不会按照我的要求,但我会提供代码和图片来帮助你理解。

示例代码:

public void InsertNodeAtTail(int val)
{
LinkedListNode node = new LinkedListNode(val);
if (head == null)
head = node;
else
{
LinkedListNode current = head;
while (current.next != null)
{
current = current.next;
}
current.next = node; //???
}
}

基本上,这一切都是在类LinkedList中完成的,我在列表的尾部插入一个值。

我把评论//???放在哪里是我很好奇的一行。

我在VS2019中运行了一个控制台程序,并放置了断点来了解发生了什么。当断点出现在注释为}的那一行之后时,current.nexthead.next将同时被分配。我希望只分配current.next,而不是head

图片:

之前:https://prnt.sc/rwahho

因此,head.nextcurrent.next都是null

之后:https://prnt.sc/rwaiub

两者都已分配!我再次期待current.next只被分配。

那么,为什么他们都被分配了呢?发生这种事有什么解释吗?如果你知道有任何网站或文章可以帮助我理解这一点,请告诉我。

附言:我在那一行后面添加了head.next = current,最后我得到了一个无尽的列表。

InsertNodeAtTail将获取一个值,从中创建一个节点,遍历列表直到列表结束,然后插入节点。

链表由具有值和下一个属性(指向列表中的下一个节点)的节点组成。列表的开头由一个名为head的节点定义。遍历列表包括从头部开始,然后重复移动到.Next节点(在循环中),直到找到null值(列表中的最后一个节点将具有.Nextnull值)。

代码所做的第一件事是检查head是否为null。如果是,则意味着我们有一个空列表,因此没有"头"(或"尾"),因此插入的值变为head

如果head而不是null,那么我们将创建一个名为current的节点,用于遍历列表。我们首先将其分配给head节点,然后检查其.Next属性是否为null


回答

此时此刻,headcurrent都指向同一节点。如果.Nextnull,那么我们将新节点分配给.Next属性。由于currenthead都指向同一节点,它们的.Next值都发生了更改。


下次调用InsertNodeAtTail时,current将被分配给head.Next(因为它不是null,因为我们之前刚刚在这里插入了一个节点)。然后,通过将新值分配给节点的.Next属性来插入新值,并且head将保持不变(因为current不再引用head


视觉表示

因此,首先我们有一个NULL头,因此新节点被分配给头,其.Next:的值为null

head          
║
▼
╔═══════════╗ .Next
║ 1st value ║═══════► NULL
╚═══════════╝

下次运行时,我们将创建一个current节点,并将其指向HEAD,并检查其.Next属性。由于.Nextnull,我们在其中插入新值。此时,headcurrent都指向同一个节点,因此对其中一个节点的任何更改也会出现在另一个节点中:

head          
║
▼
╔═══════════╗ .Next   ╔═══════════╗ .Next
║ 1st value ║═══════► ║ 2nd value ║═══════► NULL
╚═══════════╝         ╚═══════════╝
▲
║
current

然后,下次运行时,current将移动列表中的最后一个节点(head.Next不为空,因此current被分配给节点),我们将在那里插入节点。这一次,head将保持不变,因为current不再指代它:

head          
║
▼
╔═══════════╗ .Next   ╔═══════════╗ .Next   ╔═══════════╗ .Next    
║ 1st value ║═══════► ║ 2nd value ║═══════► ║ 3rd value ║═══════► NULL
╚═══════════╝         ╚═══════════╝         ╚═══════════╝
▲
║
current

如果这仍然令人困惑,您可能想阅读有关引用类型的内容。

一个简单的想法是:headcurrent都"指代内存中的一个位置"。这意味着,当我们对current的属性进行更改时(如将current.Next设置为某个值),实际上是在对其所指地址处的对象进行更改

所以如果我们做current.Next = someNode,那么head.Next也将等于someNode

但是,当我们对current本身(而不是它所指的东西)进行更改时,通过将其分配给一个全新的节点,,我们就改变了它所指内存中的地址

因此,如果我们执行类似current = head.Next的赋值,那么对head.Value的任何更改都不会影响current.Value,因为它们指的是不同的节点。


另一种思考方式

假设我们在看房子,我们有两个房地产经纪人(headcurrent)。我们让其中一个人看一处房产(head = newNode;),让另一个人看同一处房产地址(current = head),然后让他们每个人向我们描述。在这种情况下,我们会从他们每个人那里得到相同的答案(它有2张床,1个浴缸,800平方英尺,等等)。

如果有人来给房子增加一个游泳池(current.Next = anotherNode),下次我们问他们中的任何一个时,他们都会告诉我们增加了一个新的游泳池。

接下来,假设我们让其中一个查看不同的地址(current = current.Next)。这一次,当我们要求每个房地产经纪人描述他们正在寻找的当前房产时,我们会得到两个完全不同的描述,因为他们正在寻找两个不同的地址。

当变量有别名时会发生这种情况。LinkedListNode current = head;不会创建head内存的深度副本,它只是给你一个额外的变量来访问它。这是必要的,因为current需要进行重新分配才能遍历链表——如果我们在像head = head.next这样的分配中直接使用它,我们会失去对类head节点的跟踪。

因此,作为内存中的对象,我们可以假设head看起来像这样(对于单个元素链表):

.------.
| val  |
| next -> null
`------`
^
|
[variable `head`]

然后,我们执行LinkedListNode current = head;(注意没有new关键字——没有分配新的内存)。程序的状态现在是:

.------.
| val  |
| next --> null
`------`
^ ^
| |
| +----[variable `current`]
|
[variable `head`]

您可以看到两个变量指向相同的内存位置。行while (current.next != null)为false,因为next为null,所以我们从不为这个退化链表输入循环体。

最后,我们执行current.next = node;:

[variable: `node`]
|
v
.------.  .------.
| val  |  | val  |
| next -->| next --> null
`------`  `------`
^ ^
| |
| +----[variable `current`]
|
[variable `head`]

我们更改了currenthead都引用的对象。这是调试器向您显示的内容,非常正常。当块结束时,head仍然指向列表的逻辑头,我们添加了新的尾部。current在这里似乎毫无意义,但如果我们有一个更长的列表,while循环就会被执行,current就会停止混淆head,使我们能够遍历到列表的末尾,而不会丢失对head的跟踪。

这看起来类似于,例如,在执行current.next = node;:之后,向3元素列表中添加一个新节点

[variable: `node`]
|
v
.------.  .------.  .------.  .------.
| val  |  | val  |  | val  |  | val  |
| next -->| next -->| next -->| next --> null
`------`  `------`  `------`  `------`
^                   ^
|                   |
|                   +----[variable `current`]
|
[variable `head`]

相关内容

  • 没有找到相关文章

最新更新