LinkedList内部原理解析

俞其荣 · 简书 · · 2018-02-04 16:35

正文

请到「今天看啥」查看全文

其实在 first 之前，还有一个为 null 的 head 节点。head 节点的 next 才是 first 节点。

add(int index, E element)

    public void add(int index, E element) {
        // 检查 index 有没有超出索引范围
        checkPositionIndex(index);
        // 如果追加到尾部，那么就跟 add(E e) 一样了
        if (index == size)
            linkLast(element);
        else
        // 否则就是插在其他位置
            linkBefore(element, node(index));
    }

在 add(int index, E element) 中主要就看 linkBefore(element, node(index)) 方法了。注意到有一个 node(index) ，好奇究竟做了什么操作？

    Node<E> node(int index) {
        // assert isElementIndex(index);
        // 如果 index 在前半段，从前往后遍历获取 node
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            // 如果 index 在后半段，从后往前遍历获取 node
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

原来是为了索引得到 index 对应的节点，在速度上做了算法优化。