每日一算法----设计链表（java）

class MyLinkedList {
    static class ListNode {
        int val;
        int index;
        ListNode prev;
        ListNode next;

        public ListNode(int val, int index, ListNode prev, ListNode next) {
            this.val = val;
            this.index = index;
            this.prev = prev;
            this.next = next;
        }

        public ListNode(int val, int index) {
            this.val = val;
            this.index = index;
        }
    }

    ListNode head; // 虚拟头节点
    ListNode tail; // 虚拟尾节点
    
    /*
        在构造方法中初始化虚拟头结点和虚拟尾节点
    */
    public MyLinkedList() {
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 返回index索引处节点的值
     */
    public int get(int index) {
        if (index == 0) {
            return head.next.val; // index为0，返回头结点的值
        }
        ListNode curr = head.next;
        // 在链表中查找index索引处的节点
        while (curr != null && curr.index != index) {
            curr = curr.next;
        }
        if (curr == null) {//没找到
            return -1;
        } else { // 找到
            return curr.val;
        }
    }

    /**
     * 添加新的链表头节点
     */
    public void addAtHead(int val) {
        ListNode oldHead = head.next; // 旧的链表头节点
        ListNode newHead = new ListNode(val, 0, head, oldHead);
        head.next = newHead; // 虚拟节点的next指向新的链表头节点
        oldHead.prev = newHead; // 旧的链表头节点的prev指向新的链表头节点
        // 链表头部添加了一个节点，后序链表中的节点index索引需要全部++
        ListNode curr = oldHead;
        while (curr != tail) {
            curr.index++;
            curr = curr.next;
        }
    }

    /**
     * 添加新的链表尾节点
     */
    public void addAtTail(int val) {
        ListNode oldTail = tail.prev; // 旧的链表尾节点
        ListNode newTail = new ListNode(val, oldTail.index + 1, oldTail, tail);
        // 旧的链表尾节点的next指向新的链表尾节点
        oldTail.next = newTail;
        // 虚拟节点的prev指向新的链表尾节点
        tail.prev = newTail;
    }

    /**
     * 在链表第index个节点前面插入一个节点
     */
    public void addAtIndex(int index, int val) {
        ListNode curr = head.next;
        // 在链表中查找index-1索引的节点
        while (index != 0 && curr != null && curr.index != index - 1) {
            curr = curr.next;
        }
        // 如果index为0，相当于在链表头部插入节点
        if (index == 0) {
            addAtHead(val);/
            return;
        }
        if (curr == null) { // 没找到
            return;
        } else {
            // 在index索引处加入新的节点
            ListNode oldNode = curr.next;
            ListNode addNode = new ListNode(val, index, curr, oldNode);
            curr.next = addNode;
            oldNode.prev = addNode;
            // 在index处加入了新的节点，则后序节点的index值需要全部++
            ListNode c = oldNode;
            while (c != tail) {
                c.index++;
                c = c.next;
            }
        }
    }

    /**
     * 删除链表的第index个节点的数值
     */
    public void deleteAtIndex(int index) {
        ListNode curr = head.next;
        // 在链表中查找index-1索引的节点
        while (index != 0 && curr != null && curr.index != index - 1) {
            curr = curr.next;
        }
        // 如果index为0，相当于删除头节点，此时只需要将虚拟头结点的next指针向后移动一位
        if (index == 0) {
            head.next = curr.next;
            return;
        }
        if (curr == null) { // 没找到
            return;
        } else { //找到
            if (curr.next == tail) {
                return;
            }
            ListNode deleted = curr.next; // 待删除节点
            curr.next = deleted.next; // 删除节点操作
            deleted.next.prev = curr; // 重新建立双向链表
            ListNode c = deleted.next; 
            while (c != tail) {
                c.index--; // 删除一个节点，后序节点的index全部需要-1
                c = c.next;
            }
        }
    }
}