关于dummyhead的问题
来源：4-4 链表的遍历，查询和修改
慕神55941
2019-03-21
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++;
}
写回答
1回答
-
首先，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;
如果有需要，单步调试跟踪，再仔细理解试试看？
加油！：）
032019-09-25
相似问题