手撕LinkedList

Doubly-linked list implementation of the {@code List} and {@code Deque}

interfaces.  Implements all optional list operations, and permits all
elements (including {@code null}).

//底层数据结构，为一个双向链表    
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);
		//使用一次二分法，确定获取的数据在上半区还是下半区，进而在半区中循环查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }