小九的酒窝

双链表的实现，节点ListNode跟单链表比起来多了一个prev属性，用来存储指向前一个节点的指针引用。

结点类

class DoubleNode {
   int val;
   DoubleNode next;
   DoubleNode prev;

   DoubleNode(int val) {
       this.val = val;
   }
}

链表类

class MyLinkedList {
   int size;
   DoubleNode head, tail;

   public MyLinkedList() {
       size = 0;
       head = new DoubleNode(0);
       tail = new DoubleNode(0);
       head.next = tail;
       tail.prev = head;
   }

   public int get(int index) {
       if (index < 0 || index >= size) return -1;
       DoubleNode current = head;
       //  调整一下  如果index>size/2 那么从后边开始搜索
       if (index > size / 2) {
           current = tail;
           //  结尾开始
           while (index < size) {
               current = current.prev;
               index++;
           }
       } else {
           while (index >= 0) {
               current = current.next;
               index--;
           }
       }

       return current.val;
   }

   public void addAtIndex(int index, int val) {
       if (index > size) return;
       if (index < 0) index = 0;
       DoubleNode temp = head;
       if (index > size / 2) {
           //  从后往前搜索 这次是搜索前一个结点 在其之后插入 所以多走一步
           temp = tail;
           while (index <= size) {
               temp = temp.prev;
               index++;
           }
       } else {
           while (index > 0) {
               temp = temp.next;
               index--;
           }
       }
       size++;
       DoubleNode newNode = new DoubleNode(val);
       DoubleNode backNode = temp.next;
       temp.next = newNode;
       newNode.prev = temp;
       newNode.next = backNode;
       backNode.prev = newNode;
   }

   public void addAtHead(int val) {
       addAtIndex(0, val);
   }

   public void addAtTail(int val) {
       addAtIndex(size, val);
   }

   public void deleteAtIndex(int index) {
       if (index < 0 || index > size - 1) return;
       DoubleNode temp = head;
       if (index > size / 2) {
           //  从后往前搜索
           temp = tail;
           while (index < size) {
               temp = temp.prev;
               index++;
           }
       } else {
           while (index >= 0) {
               temp = temp.next;
               index--;
           }
       }
       size--;
       DoubleNode foreNode = temp.prev;
       DoubleNode backNode = temp.next;
       foreNode.next = backNode;
       backNode.prev = foreNode;
   }
}