java - head.next 在单链表中是如何改变的

Question

我对简单的单链表有很大的困惑，例如:在 Java 中。

节点类:

public class node {

    public int data;
    public node next;

    public node(int data , node next) {
       this.data = data;
       this.next = next; 
    }
}

链表类:

public linked list{

    public node first;
    public node last;

    public void add(int data){

        node x = new node(data,null);

        if( first == null ) { first= x; }
        else { last.next = x; }
        last = x;

    }
}

这里很困惑，如果链表是空的，我正在尝试添加新节点，例如:add(1);

第一个节点的数据将为1，第一个节点的下一个将为空最后一个节点的数据将为1，最后一个节点的下一个将为空

现在，如果我添加一个新节点，例如:add(2);

最后一个节点的数据将为2，最后一个节点的下一个将为空第一个节点的数据仍然是 1，但第一个节点的下一个数据将是尾部，这是怎么发生的？

head.next 在单链表中是如何改变的？

Answer 1

how head.next is changed in singly linkedlist ?

简答:因为最初 first 和 last 都指向同一个节点，last.next = x 间接导致 first.next = x。

---

长答案:

它的核心是对象引用(指针)。

要了解它为何发生变化，首先您必须了解指针在 Java 中的工作原理，Java 是一种非常高级的语言，您可以在其中隐藏所有讨厌但乏味的内存操作。

tldr;我建议您观看这个关于指针的史诗视频，Binky Pointer Video .

---

指针在 Java 中的工作原理

<强>1。内存分配:

下面的语句分配新的内存来保存节点值(数据和下一个)。 x 现在保存地址值，即:0x1ACD 到实际节点值。换句话说，x 是一个节点指针。

  node x = new node(data,null); //0x1ACD

<强>2。指针取消引用:

为了访问实际的节点值，我们需要取消引用地址值。当您访问对象中的属性时会发生指针取消引用，即:node.Next。以下语句取消引用 last 和对象赋值将 x 中的地址值复制到 next(last 中的属性) .

  last.next = x;

<强>3。对象分配:

由于 Java 内部设计(内存效率)，对象赋值只复制地址值，而不是克隆整个节点值(在现实世界中，它可能很大)。

first 和 last 现在拥有与 x 相同的地址值，这是实际节点值的地址。

public void add(int data){
    ...
    first = x; 
    last = x;
    ...
}

你可能会问这有什么了不起？好吧，举个例子:

public void add(int data){
    ...
    first = x; 
    last = x;
    last.next = new node(123,null);
    ...
}

注意现在，last.next == first.next。通过 last 更改节点值似乎也会修改 first，因为它们都指向相同的节点值。

这是对how head.next is changed in single linkedlist ?

的完整回答

引用资料:

1. https://softwareengineering.stackexchange.com/questions/207196/do-pointers-really-exist-in-java
2. https://softwareengineering.stackexchange.com/questions/141834/how-is-a-java-reference-different-from-a-c-pointer

---

插图:

第 1 步:当我们add(1) 到一个空列表时:

public void add(int data) {
    ...
    first= x; 
    ...
    last = x;
    ...
} 

// after:
   [1] <- first, last           // first and last now pointing to the same `node:x`.  
    |
   [/] <- first.next, last.next // first.next, last.next pointing to null.

第 2 步:现在，当我们add(2) 到之前的列表(非空)时:

// before:
   [1] <- first, last          
    |
   [/] <- first.next, last.next // first.next, last.next pointing to null.

public void add(int data) {
    ...
    // technically, since first and last pointing to the same node[1],
    // x actually being assigned to both first.next and last.next.
    last.next= x; 
    ...
    last = x;     // update last from previous-x to current-x.
    ...
} 

// after:
   [1] <- first
    |
   [2] <- last      // first.next, last is pointing to the new `node:x`.
    |
   [/] <- last.next // last.next to null.

第 3 步等:现在，让我们添加(3) 或后续值到列表(非空):

// before:
   [1] <- first
    |
   [2] <- last      
    |
   [/] <- last.next // last.next to null.

public void add(int data) {
    ...
    last.next= x; // access previous-x and assign x to previous-x's next.
    ...
    last = x;     // update last from previous-x to current-x.
    ...
} 

// after:
   [1] <- first
    |
   [2]         
    |
   [3] <- last      // last is pointing to the new `node:x`. 
    |
   [/] <- last.next // last.next to null.

---

备注:

• first 始终指向列表中的第一个节点。

• last 始终指向列表中的最后一个节点。

• last.next 始终指向 null。通过 Add()，新节点总是通过分配给 last.next 附加到列表的末尾。