关于JDK1.7中LinkedList索引方法的思考

原创
2015/11/10 14:38
阅读数 1.9K

前几天无意中看到LinkedList的部分源码,发现一个很有趣的问题,跟大家一起分享一下。

首先LinkedList底层实现是双向链表,这个毫无疑问,地球人都知道,这就使得LinkedList有了链表结构的一些特性,我们在根据下标索引查找值得时候查看关键源码如下:

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

测试代码如下:

List<Object> list = new LinkedList<>();

list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");
list.add("eee");
System.out.println(list.size());
System.out.println(list.get(2));

上述代码,我在LinkedList中添加了五个元素,此时的size=5,get(2)=ccc。那么底层是如何去索引找到ccc的呢?

细读上面LinkedList源码中node方法可以发现,在检索的时候会有一个算法调优,根据索引值与size的比较来判断从前还是从后开始进行遍历。当index < (size >> 1)成立时,从前往后遍历,反之由后往前遍历。

上述测试用例当我get(2)的时候,表达式中index=2,size=5,5右移一位为5/1*2 = 2,表达式2<2显然不成立,程序将执行else的语句。

我们看一下LinkedList的链表结构:

此时index=2时,程序应该从前往后去遍历,尽量减少遍历的次数。那么在if判断里面应该为index <= (size >> 1) 不知道这个是不是LinkedList的待优化的地方,但是至少这个地方我觉得是应该加等于号的。可能是我自己理解的问题,如有错误,欢迎大家指正,O(∩_∩)O谢谢!!!

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
3 评论
0 收藏
0
分享
返回顶部
顶部