引入虚拟头节点
- 引入虚拟头节点
dumyHead 使得 LinkedList 成了只包含虚拟头节点的数据结构，在初始化 LinkedList 的时候，为 dumyHead 分配了空间（不像 head 指针在初始化的时候没有分配空间，只是指向 null），此时 dumyHead 中，dumyHead.e = null，dumyHead.next = null；
- 由于虚拟头节点的引入，使得向 LinkedList 的指定位置添加元素时，无需针对在队首插入元素的情况做特殊处理；
- 由于链表的插入需要找到插入节点的前驱节点，因此游标
prev 要停在插入位置的前一个位置；初始时，将 prev 指向 dumyHead，当 i = 0 时，prev 向右移动一格，prev 指向索引为 0 的节点，即第一个元素（dumyHead 是第一个节点的前驱节点），所以 i = index - 1 时，prev 也指向了 index - 1 ，即：插入位置的前一个位置，从而找到了插入节点的前驱节点；
public class LinkedList<E> {
private class Node{
public E e;
public 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);
}
@Override
public String toString(){
return e.toString();
}
}
private Node dummyHead;
private int size;
public LinkedList(){
dummyHead = new Node();
size = 0;
}
// 获取链表中的元素个数
public int getSize(){
return size;
}
// 返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
// 在链表的index(0-based)位置添加新的元素e
// 在链表中不是一个常用的操作，练习用：）
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;
prev.next = new Node(e, prev.next);
size ++;
}
// 在链表头添加新的元素e
public void addFirst(E e){
add(0, e);
}
// 在链表末尾添加新的元素e
public void addLast(E e){
add(size, e);
}
}
