java链表之虚拟头结点

链表操作中，可以使用原链表来直接进行删除操作，也可以设置一个虚拟头结点在进行删除操作，

但是在原来链表上操作要考虑待删除节点是不是头节点的问题，而当我们给链表中加上了一个虚拟头结点后头结点也就有了一个虚拟出来的前驱，这样我们队链表的删除就简单的多了。

public class SingleListWithHead {
    private int size;
    // 添加虚拟头结点
    private Node dummyhead=new Node(-1);
    //添加元素
    public void addIndex(int index,int val){
        //合法性检测
        if(index<0||index>size){
            System.err.println("index erro");
            return;
        }
        Node prev=dummyhead;
        Node node=new Node(val);
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }
        node.next=prev.next;
        prev.next=node;
        size++;
    }
    public void addFist(int val){
        addIndex(0,val);
    }
    public void addLast(int val){
        addIndex(size,val);
    }
    public String toString(){
        String ret="";
        Node node=dummyhead.next;
        while(node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;
        }
        ret+="null";
        return ret;

    }
    public void removeIndex(int index){
        if (index<0||index>size){
            System.err.println("index erro");
        }
        Node prev=dummyhead;
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }
        prev.next=prev.next.next;
        size--;

    }

}

这个是加上虚拟头结点的添加和删除操作，下面在对比一下直接在原来的链表上操作的代码：

  public void removeIndex(int index){


        if (rangecheck(index)) {
            if (index == 0) {
                Node temp = head;
                head = head.next;
                temp.next = null;
                size--;
            } else {
                Node prve = head;
                for (int i = 0; i < index - 1; i++) {
                    prve = prve.next;
                }
                Node cur = prve.next;
                prve.next = cur.next;
                cur.next = null;
                size--;
            }
        }
    }

可以显而易见的看出来，就删除这一操作就少了很多代码，操作也更简单了。