leetcode||707.双向链表

1.思路：设置虚拟头节点和虚拟尾节点

2.为了提高查询效率，在根据索引查找节点的值时注意头尾虚拟节点的选择。

java代码

public class DoubleList707 {
    //1.双向链表的结构
    private class ListNode{
        int value;
        ListNode pre;
        ListNode next;
        public ListNode(){};
        public ListNode(ListNode pre,int value,ListNode next){
            this.pre=pre;
            this.value=value;
            this.next=next;
        }
    }
    //虚拟头节点
    ListNode head;
    //虚拟尾节点
    ListNode tail;
    //记录链表长度
    int size;
    //2.初始化
    public DoubleList707(){
        head = new ListNode(null,-1,null);
        tail = new ListNode(null,-1,null);
        head.next=tail;
        tail.pre=head;
        size=0;
    }

    //3.遍历
    //注意p!=tail
    public void ForEach11(Consumer<Integer> consumer){
        for (ListNode p =head.next;p!=tail;p=p.next){
            consumer.accept(p.value);
        }
    }
    //4.根据索引得到对应节点的值
    public int get(int index){
        if(index<0 ||index >=size){
            return -1;
        }
        ListNode p = head.next;
        //判断从头节点节点历时最短还是尾节点历时最短
        if(index>=(size>>1)){
            p=tail;
            for (int i = 0; i < (size-index); i++) {
                p=p.pre;
            }
        }else{
            for (int i = 0; i < index; i++) {
                p=p.next;
            }
        }

        return p.value;
    }
    //5.从头部添加节点
    public void FistInsert(int value){
        insert(value,0);
    }
    //6.尾部添加节点
    public void listInsert(int value){
        insert(value,size);
    }
    //7.根据索引（某节点前）插入节点
    public void insert(int value,int index){
        if(index > size){
            return;
        }
        if(index<0){
            index = 0;
        }
        ListNode p = head.next;
        for (int i = 0; i < index; i++) {
            p=p.next;
        }
        ListNode prenode=p.pre;
        ListNode cur = new ListNode(prenode,value,p);
        prenode.next=cur;
        p.pre = cur;
        size++;

    }
    //8.根据索引删除对应节点
    public void delete(int index){
        if(index<0 ||index >=size ){
            return;
        }
        ListNode p = head.next;
        for (int i = 0; i < index; i++) {
            p=p.next;
        }
        ListNode prenode = p.pre;
        ListNode nextnode = p.next;
        prenode.next=nextnode;
        nextnode.pre=prenode;
        size--;

    }
}

测试：

@Test
    public void test11(){
        DoubleList707 list = new DoubleList707();
        list.ForEach11(s-> System.out.println(s));
        list.FistInsert(1);
        list.FistInsert(6);
        list.FistInsert(9);
        list.FistInsert(8);
        list.FistInsert(2);
        System.out.println("2->8->9->6->1");
        list.ForEach11(s-> System.out.println(s));
        list.delete(0);
        System.out.println("8->9->6->1");
        list.ForEach11(s-> System.out.println(s));
        list.delete(1);
        System.out.println("8->6->1");
        list.ForEach11(s-> System.out.println(s));
        list.delete(2);
        System.out.println("8->6");
        list.ForEach11(s-> System.out.println(s));
        list.insert(1,1);
        System.out.println("8->1->6");
        list.ForEach11(s-> System.out.println(s));
        list.insert(9,3);
        System.out.println("8->1->6->9");
        list.ForEach11(s-> System.out.println(s));
        System.out.println("-----------------------");
        System.out.println(list.get(3));
    }