LinkedList查詢方法怎么使用

新增方法

 public boolean add(E e) {
        linkLast(e);
        return true;
    }
     /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

可見每次插入都是移動(dòng)指針，和 ArrayList 的拷貝數(shù)組來(lái)說(shuō)效率要高上不少。

查詢方法

 public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    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;
        }
    }

上述代碼，利用了雙向鏈表的特性，如果index離鏈表頭比較近，就從節(jié)點(diǎn)頭部遍歷。否則就從節(jié)點(diǎn)尾部開始遍歷。使用空間（雙向鏈表）來(lái)?yè)Q取時(shí)間。
node()會(huì)以O(shè)(n/2)的性能去獲取一個(gè)結(jié)點(diǎn),如果索引值大于鏈表大小的一半，那么將從尾結(jié)點(diǎn)開始遍歷
這樣的效率是非常低的，特別是當(dāng) index 越接近 size 的中間值時(shí)。