链表头指针和虚拟头节点小结
零 头指针
链表是由一个一个的节点串联在一起，实际存放数据的是节点，每个节点中包含一个数据，以及指向下一个节点的指针。
头指针就是指向第一个节点的指针。有了头指针之后，我们便可以逐个找到链表中的所有元素。除了第一个节点之外，每个节点都有1个前驱节点。因此，我们在链表的任意位置插入元素时，就得考虑一种特殊情况：在链表第一个元素之前添加新元素。另外，如果想要删除任意元素时，也得考虑删除的是第1个元素的特殊情况。
初始化链表时，头指针指向NULL。
一 虚拟头节点
头节点就是在第1个节点之前，额外添加的1个虚拟的节点，让它所指向的下一个节点就整个链表中的真正的第1个节点。虚拟头节点对用户是不可见的，是我们人为手工给链表加上去的。初始化链表时，虚拟头节点指向的是1个空的节点。
头结点就是为了解决上述问题：针对第1个元素前添加新元素/删除第1个元素的特殊情况。
一旦设立了虚拟头节点，整个链表中的所有节点都有1个前驱节点，这样一来，我们在任意位置处执行的增删改查都将变得简单了，可以统一操作了。而不再需要额外考虑第1个位置处的特殊情况了。
二初始化链表
1 带头指针的链表
public class LinkedList<E>{
private class Node<E>{
private E e;
private Node next;
public Node(E e,Node next){
this.e=e;
this.next=next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
}
//头指针
private Node head;
private int size;
public LinkedList(){
//头指针指向NULL，不存在的节点，此时链表为空
head=null;
size=0;
}
......
}2带虚拟头节点的链表
public class LinkedList<E>{
//内部类，构建节点
private class Node<E>{
private E e;
private Node next;
public Node(E e,Node next){
this.e=e;
this.next=next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
}
private Node dummyHead;
private int size;
//初始化链表时，虚拟头节点是实际存在的，只不过它存放的元素是NULL，指向的下一个节点也是空。
public LinkedList(){
dummyHead=new Node(null,null);
size=0;
}
}三虚拟头节点的好处
对于整个链表而言，在第index位置处执行增加元素、删除元素操作时，我们的思路是这样的：先找到index处的前一个元素pre。如果是新增元素，则new一个节点newNode，让newNode.next()指向pre.next()，最后让pre.next()指向这个新加的节点newNode()。这样就完成了添加。可问题是，如果要添加的位置在第1个，则不太好处理，因为它没有前一个元素。
换个思路，如果我们人为的给第1个节点预先添加1个虚拟的节点，使其有了前驱节点，这样一来，我们对整个链表的任意位置处的元素执行增加、删除操作都变得统一了。
链表中选择人为的构建1个虚拟头节点，跟循环队列中，人为的浪费1个存储空间，进而使循环队列的出队时间复杂度降低到O(1)。都是一种编程上的小技巧tips。
