ArrayList与LinkedList获取指定元素对比（源码分析）
ArrayList获取指定元素
- 首先在主函数中使用
ArrayList生成一个size为一千万的List实例list：
int max = 10000000; List<String> list = new ArrayList<>(max); for (int i = 0; i < max; i++) { list.add("a"); }
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { rangeCheck(index); return elementData(index); }
可以看到，首先使用rangeCheck对index进行检验；然后点进去elementData：
@SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
- 发现直接返回了
elementData数组中下标为index的元素，时间复杂度为O(1)； - 测试一下使用
get方法来获取最后一个元素所需的时间：
long startTime = System.currentTimeMillis(); list.get(max - 1).hashCode(); long endTime = System.currentTimeMillis(); System.out.println("ArrayList获取最后一个元素所需时间: "+(endTime - startTime));
运行结果如下：
ArrayList获取最后一个元素所需时间: 0
- 发现该方法运行时间几乎为0，因为无需遍历元素，直接根据
index返回数据即可；
LinkedList获取指定元素
- 首先在主函数中使用
LinkedList生成一个size为一千万的List实例list：
int max = 10000000; List<String> list = new LinkedList<>(); for (int i = 0; i < max; i++) { list.add("a"); }
来看一下LinkedList的get方法的源码：
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { checkElementIndex(index); return node(index).item; }
可以看到，首先使用checkElementIndex对index进行检验；然后点进去node：
/** * 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; } }
- 可以看出，当
index位于size的前一半时，从前往后去遍历元素；当index位于size的后一半时，从后往前去遍历元素；所以当index恰好位于中间位置时，所需时间最长； - 测试一下使用
get方法来获取中间元素所需的时间：
long startTime = System.currentTimeMillis(); list.get(max / 2).hashCode(); long endTime = System.currentTimeMillis(); System.out.println("LinkedList获取中间元素所需时间: "+(endTime - startTime));
运行结果如下：
LinkedList获取中间元素所需时间: 17
发现该方法运行时间较长，因为需要遍历元素去寻找数据；
结论
- 对于需要经常查询元素的场景，应尽量使用
ArrayList来实现，所需时间复杂度为O(1)；
