关于dummyhead的问题

Question

bobo老师你好，在学到dummyhead的时候，dummyhead初始化其内容和next都是空的，dummyhead.next应该是空节点，把它赋给prev节点的时候为什么prev.next是链表的第一个节点呢，请老师帮忙解答，谢谢。

public void add(int index, E e){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Add failed. Illegal index");

        Node prev = dummyhead;
        for (int i = 0; i < index; i++)
            prev = prev.next;
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;

        size++;
    }

Answer 1

liuyubobobo 2019-03-22 01:34:40

首先，dummyHead不是空的，是有内容的。只是这个内容是多少我们不care，他和我们的链表数据无关。但是，dummyHead != null

所以，在有虚拟头结点的情况下，我们向一个空链表添加第一个元素，本质就是在dummyHead的后面添加一个元素。

在链表的一个节点的后面添加元素，这个过程，请在回顾复习一下课程的4-2小节的介绍，理解一下其中的逻辑。在这里，我们写的代码逻辑，其实是完全相同的。

比较一下4-2小节我们的添加代码：

public void add(int index, E e){    

    if(index < 0 || index > size)    
        throw new IllegalArgumentException("Add failed. Illegal index.");    

    if(index == 0)    
        addFirst(e);    
    else{    
        Node prev = head;    
        for(int i = 0 ; i < index - 1 ; i ++)    
            prev = prev.next;    

        // Node node = new Node(e);    
        // node.next = prev.next;    
        // prev.next = node;    
        
        prev.next = new Node(e, prev.next);    
        size ++;    
    }    
}

可以看到，这一小节，我们的代码完全是4-2小节实现的添加代码else部分的逻辑框架。只是，在4-2小节，由于我们没有虚拟头结点，需要对在链表头添加节点进行单独处理。但是，当我们设立了虚拟头结点之后，所有的添加操作，都可以理解为在某一个节点后添加节点。在链表头添加节点，变成了在dummyHead后添加节点。所以，我们不再需要这个if else了。

最后，由于我不很确定我完整的理解了你的问题。所以，对于初始情况下，我们向链表添加第一个节点，这个代码是如何运转的，解释一下。

// 如果我们向一个空链表添加第一个节点。
// 注意1：此时index肯定为0
// 注意2：在有虚拟头结点的情况下，即使整个链表没有元素，dummyHead也不是null

// prev指向dummyHead
Node prev = dummyhead;

// 注意：当index == 0的时候，这个循环不会运行
// 因为i = 0 < 0是false，直接跳出
for (int i = 0; i < index; i++)
    prev = prev.next;
        

// 所以在这里，prev依然指向dummyHead
// 以下的代码就是在dummyHead后面添加一个新节点的代码       
Node node = new Node(e);
node.next = prev.next;
prev.next = node;

如果有需要，单步调试跟踪，再仔细理解试试看？

加油！：）

• 提问者 慕神55941 #1

  非常感谢！是我自己想的时候陷入误区了

• lemonlxn #2

  老师好，我这样说是否有误？初始化dummyhead的时候，只是 dummyhead.e = null 且 dummyhead.next = null ，但dummyhead对象本身不为null

• liuyubobobo 回复 lemonlxn #3

  对的。dummyhead不是null，我们在构造函数new空间了：）