list - 什么是假头？

Question

所以我想确定什么是链表中的虚拟头/虚拟节点。有人可以告诉我定义并举个例子吗？

Answer 1

虚拟节点更像是一种 hack，通常在您想避免为边缘情况编写额外代码时使用。
考虑以下在链表中尾部插入的情况:

void insertAtTail(Node oldTail, int i){
    Node newTail = new Node(i);
    oldTail.next = newTail;
    return newTail;
}

当 oldTail 不为空时，这可以正常工作。但是想象一下我们试图在一个空列表上执行 insertAtTail() 的场景。如果节点为空，上面编写的代码将不起作用。因此，我们必须处理检查 oldTail 是否为 null 的边缘情况:

Node insertAtTail(Node oldTail, int i){
    Node newTail = new Node(i);
    if(oldTail == null) {return newTail;}
    oldTail.next = newTail;
    return newTail;
}

在这种情况下，虚拟节点就派上用场了。想象一下，我有一个虚拟节点，如下所示:

Node dummy = new Node(0);

现在我们将这个虚拟节点传递给调用函数:

insertAtTail(dummy, 5);

当一个虚拟节点被传递给调用函数时，你会看到这里没有必要检查虚拟节点是否为空。因此，我们可以跳过对空节点的检查:

Node insertAtTail(Node dummy, int i){
    Node newTail = new Node(i);
    dummy.next = newTail;
    return newTail;
}

如您所见，我已在此处删除了对 null 的检查。