add(E e)
方法的时候, ArrayList 会默认将该元素追加到此列表的末尾,这种情况的时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element)
),那么时间复杂度就为 O(n-i),因为在进行上述操作的时候,集合中第 i 和第 i 个元素之后的 (n-i) 个元素,都要执行向后/前位移一位的操作。 ② LinkedList 采用的是链表存储,所以插入、删除元素时间复杂度不受元素位置的影响,都是近似 O(1),而数组为近似 O(n);get(int index)
方法);public interface RandomAccess {
}
查看源码可以看到, RandomAccess 接口中什么都没有定义。所以,这就是个标识接口,标识那些实现了这个接口的类,具有随机访问的功能。
在 binarySearch()
方法中,它要判断传入的 List 是否是 RamdomAccess 的实例。如果是,则调用 indexedBinarySearch()
方法;如果不是,那么就调用 iteratorBinarySearch()
方法
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
ArrayList 实现了 RandomAccess 接口, 而 LinkedList 没有实现。为什么呢?还是和底层数据结构有关。ArrayList 底层是数组,而 LinkedList 底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以支持快速随机访问。而链表需要遍历到特定的位置,才能访问特定位置的元素,时间复杂度为 O(n),所以不是快速高效的随机访问。
ArrayList 实现了 RandomAccess 接口,表明了具有快速随机访问的功能。不过 RandomAccess 接口只是一个标识,并不是说 ArrayList 实现 RandomAccess 接口,才具有快速随机访问的功能!
总结 List 的遍历方式选择:
双向链表
双向链表: 包含两个指针,一个 prev 指针指向前一个节点(第一个 prev 指向 nil),一个 next 指针指向后一个节点(最后一个 next 同样指向 nil);
双向循环链表: 最后一个节点的 next 指针指向第一个节点的 head,而第一个节点的 head 的 prev 指针指向最后一个节点,所以是构成一个循环。
双向循环链表