我是链表的新手,刚刚开始了解链表背后的功能。我有一个关于分配节点的问题。我相信这个类似的问题已经重复过了(如果是的话,请告诉我),但我在看关于链表的视频,我没有看到他们解释我在这里要问什么。
问题是,当我有一个主节点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.next
和head.next
将同时被分配。我希望只分配current.next
,而不是head
。
图片:
之前:https://prnt.sc/rwahho
因此,head.next
和current.next
都是null
。
之后:https://prnt.sc/rwaiub
两者都已分配!我再次期待current.next
只被分配。
那么,为什么他们都被分配了呢?发生这种事有什么解释吗?如果你知道有任何网站或文章可以帮助我理解这一点,请告诉我。
附言:我在那一行后面添加了head.next = current
,最后我得到了一个无尽的列表。
InsertNodeAtTail
将获取一个值,从中创建一个节点,遍历列表直到列表结束,然后插入节点。
链表由具有值和下一个属性(指向列表中的下一个节点)的节点组成。列表的开头由一个名为head
的节点定义。遍历列表包括从头部开始,然后重复移动到.Next
节点(在循环中),直到找到null
值(列表中的最后一个节点将具有.Next
的null
值)。
代码所做的第一件事是检查head
是否为null
。如果是,则意味着我们有一个空列表,因此没有"头"(或"尾"),因此插入的值变为head
。
如果head
是而不是null
,那么我们将创建一个名为current
的节点,用于遍历列表。我们首先将其分配给head
节点,然后检查其.Next
属性是否为null
。
回答
此时此刻,head
和current
都指向同一节点。如果.Next
是null
,那么我们将新节点分配给.Next
属性。由于current
和head
都指向同一节点,它们的.Next
值都发生了更改。
下次调用InsertNodeAtTail
时,current
将被分配给head.Next
(因为它不是null
,因为我们之前刚刚在这里插入了一个节点)。然后,通过将新值分配给节点的.Next
属性来插入新值,并且head
将保持不变(因为current
不再引用head
。
视觉表示
因此,首先我们有一个NULL头,因此新节点被分配给头,其.Next
:的值为null
head
║
▼
╔═══════════╗ .Next
║ 1st value ║═══════► NULL
╚═══════════╝
下次运行时,我们将创建一个current
节点,并将其指向HEAD,并检查其.Next
属性。由于.Next
是null
,我们在其中插入新值。此时,head
和current
都指向同一个节点,因此对其中一个节点的任何更改也会出现在另一个节点中:
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
如果这仍然令人困惑,您可能想阅读有关引用类型的内容。
一个简单的想法是:head
和current
都"指代内存中的一个位置"。这意味着,当我们对current
的属性进行更改时(如将current.Next
设置为某个值),实际上是在对其所指地址处的对象进行更改。
所以如果我们做current.Next = someNode
,那么head.Next
也将等于someNode
。
但是,当我们对current
本身(而不是它所指的东西)进行更改时,通过将其分配给一个全新的节点,,我们就改变了它所指内存中的地址
因此,如果我们执行类似current = head.Next
的赋值,那么对head.Value
的任何更改都不会影响current.Value
,因为它们指的是不同的节点。
另一种思考方式
假设我们在看房子,我们有两个房地产经纪人(head
和current
)。我们让其中一个人看一处房产(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`]
我们更改了current
和head
都引用的对象。这是调试器向您显示的内容,非常正常。当块结束时,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`]