请问对于链表的添加头节点void addFirst(E elem)方法，我这样写对吗?

Question

public void addFirst(E elem) 
 {                      
      if(size ==0)
      {
           head.next = new Node(elem);
           size++;
      }
      else
      {
           Node newNode = new Node(elem);
           newNode.next = head.next;
           head.next = newNode;

         size++;
      }
 }

    我是这么想的:

(1) newNode.next = head.next; 的意思是让newNode和head指向同一个结点 ,这样一来，就可以让新结点（就是newNode） 指向了头结点指向的那个结点

 (2) head.next = newNode; 的意思是让head指向的结点是newNode，这样，就可以让head指向了newNode结点，从而实现了向链表头添加元素

 具体过程如图。

视频中代码 head后都不加.next, 而我的head后都加了.next , 不知道我这样想有没有什么问题？

我之后的视频没怎么看，根据我的想法，我测试了一下代码，也没有抛出异常，不知道我这么想对不对？

Answer 1

liuyubobobo 2018-06-30 05:07:48

有问题。你的算法逻辑和课程中所介绍的逻辑是一样的。你的所有中文描述也是没有问题，但是在代码层面的具体实现不对，关键就在于head.next这个用法上。

在这一小节，我们的代码没有设立测试用例。你的代码只不过是没有编译错误，但是随便拿一个测试用例运行一下，都会报空指针异常。试一下基于你的代码运行以下Main函数：

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.addFirst(666);
    }
}

你就会看到错误：）

这里的核心问题是：head是一个Node的引用，head.next是另一个Node的引用！head指向整个链表的第一个节点，head.next指向的是两一个节点！是整个链表的第二个节点！head和head.next不一样！你在size==0的情况下，运行了head.next = new Node(elem);，其实是让head的下一个节点指向了新创建的Node。但此时head == null，所以调用head.next，就会报空指针异常。

如果你想让head指向这个新创建的Node，应该是：head = new Node(elem);。请再仔细理解一下：head和head.next是两回事儿，是两个引用！

如果理解了head和head.next是两个引用，用同样角度理解，相信你也会明白else部分的问题：）

加油！

• 提问者 alexMerce #1

  非常感谢！

• 提问者 alexMerce #2

  我又想了一下，发现的确如此，按我这么写，代码会报空指针
  现在明白了 谢谢老师

Answer 2

慕粉1221151877 2018-06-30 04:35:14

newNode.next = head.next;
head.next = newNode;

这两句在我看来结果是将newNode添加到了head.next, 也就是第二个节点的地方啊, 而之前的head节点并没有改变

• 提问者 alexMerce #1

  现在明白了。
  head 和tail都是Node类型的变量。
  
  Node类型的引用类型变量内部都包括两个数据:
  
  (1)E 泛型的data，它是每个元素内部存储的数据。
  (2)Node类型的next。它是一个指针，指向下一个元素.
  
  
  比如Node newNode = new Node (elem),就是创建一个新结点，内部数据为elem，它指向null。
  
  如果令head = newNode，则意味着head.data = newNode.data, head.next = newNode.next。
  此时则可以说head 指向了newNode，意思是head就代表了newNode 。
  而head.next 与 newNode.next代表的含义一致，就是说head.next 代表的是newNode指向的那个下一个结点,
  而head 代表的就是newNode , 即head指向newNode。

Answer 3

提问者 alexMerce 2018-06-30 02:20:23

我这样跟视频上7分09秒的addFirst方法有点不同，视频里面是

 Node newNode = new Node(elem);

newNode.next = head;

head = newNode;

跟我的代码有点差别，我是先没看视频里面代码，自己琢磨着写出来的，我想知道有没有.next 这个东西，会不会影响到代码的效果?

• 提问者 alexMerce #1

  我是这样想的，首先内部类Node中有两个成员变量，E data 和Node next,这个data代表保存的数据，而next代表指针，它可以指向null或者其他结点 。
  那么XX.next = YY.next 的意思就应该是Node类型变量XX 和YY都指向同一个结点。 
  而 XX.next = YY 则代表 XX指向 YY。 
  不知道我这么想对不对？

• 提问者 alexMerce #2

  刚才测试了一下，貌似我这么写，也没出异常，程序可以跑。那我这样的理解也对吧？ 
  感觉对我而言，这样考虑比较容易理解

• 提问者 alexMerce #3

  我是这样认为的，head.next 代表的是头节点(也就是head)指向的那个结点，
  而head 代表的是头节点(也就是head)本身。