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

来源:4-2 在链表中添加元素

alexMerce

2018-06-30

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结点,从而实现了向链表头添加元素

 具体过程如图。//img.mukewang.com/szimg/5b367f1b00018b2007561008.jpg

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

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

写回答

3回答

liuyubobobo

2018-06-30

有问题。你的算法逻辑和课程中所介绍的逻辑是一样的。你的所有中文描述也是没有问题,但是在代码层面的具体实现不对,关键就在于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部分的问题:)


加油!

0
2
alexMerce
我又想了一下,发现的确如此,按我这么写,代码会报空指针 现在明白了 谢谢老师
2018-06-30
共2条回复

慕粉1221151877

2018-06-30

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

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

0
1
alexMerce
现在明白了。 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。
2018-06-30
共1条回复

alexMerce

提问者

2018-06-30

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

 Node newNode = new Node(elem);

newNode.next = head;

head = newNode;

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

0
3
alexMerce
我是这样认为的,head.next 代表的是头节点(也就是head)指向的那个结点, 而head 代表的是头节点(也就是head)本身。
2018-06-30
共3条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程