专栏名称: 俞其荣
向前跑 迎着冷眼和嘲笑 与 http://yuqirong.me 保持同步更新
目录
相关文章推荐
丁香生活研究  ·  长期睡不够 8 小时,要紧吗? ·  17 小时前  
丁香生活研究  ·  你们催了很久的毛戈平,价格终于打下来了! ·  17 小时前  
广东疾控  ·  不要采!不要买!不要吃! ·  昨天  
营养师顾中一  ·  牛奶会增加肝癌风险?跟你喝的奶有关系 ·  2 天前  
51好读  ›  专栏  ›  俞其荣

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 对应的节点,在速度上做了算法优化。







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