Head.Next如何在单个linkedlist中更改

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，最后一个节点的下一个将是null，第一个节点的数据仍然是1，但第一个节点的下一个将是tail，这是如何发生的？

Head.Next如何在单独的linkedlist中更改？

Answer 1

Head.Next如何在单独的linkedlist中更改？

简而言之：因为最初first和last都指向同一个节点，所以last.next=x间接导致first.next=x。

长答：

它的核心是对象引用（指针）。

1.内存分配：

语句分配新的内存来保存节点值(data&next)。x现在保留地址值，即0x1ACD为实际节点值。换句话说，x是一个节点指针。

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

2.指针取消引用：

为了访问实际的节点值，我们需要取消引用地址值。当您访问Object（即node.next）中的属性时，会发生指针解引用。下面的语句取消引用last，而html" target="_blank">对象赋值将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，因为两者都指向相同的节点值。

这就是Head.Next如何在单独的linkedlist中更改的完整答案？

参考资料：

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

步骤1：当我们将(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：现在，当我们将(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将一个新节点追加到列表末尾。