学习情况记录
记录在学习Java容器 知识点中,关于 List
的需要重点记录的知识点。
10
。 * *
size
、 first
、 last
。 size
是双向链表中节点的个数, first
和 last
分别指向第一个和最后一个节点的引用。
add(E e)
方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话( add(int index, E element)
)时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。实际就是 近似O(n) 。 get(int index)
方法)。
前面的图中我们可以看到ArrayList 继承了三个接口,后面两个都是比较熟悉的,分别是标识对象可复制和可序列化。
那么 RandomAccess
接口代表什么呢?
前面的关于ArrayList 与 LinkedList 的对比当中,有一点就是,
是否支持快速随机访问 :这个也是由底层实现决定的,LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。 快速随机访问就是通过元素的序号快速获取元素对象 (对应于 get(int index)
方法)。
而 RandomAccess
接口 就是用来 标识该类支持快速随机访问。 查看源码可以发现,这个接口内部没有任何的定义。仅仅是起标识作用。
比如在 Collections.binarySearch()
方法中,
实现了RandomAccess接口的List使用索引遍历,而未实现RandomAccess接口的List使用迭代器遍历。
总结一句话:实现RandomAccess接口的List可以通过for循环来遍历数据比使用iterator遍历数据更高效,未实现RandomAccess接口的List可以通过iterator遍历数据比使用for循环来遍历数据更高效。当然对于ArrayList来说,for循环遍历和Iterator方式遍历差距不大,但是对于LinkedList这种没有实现的来说,两种遍历方式效率差距就有点大了。这主要是因为底层实现不同。
与 ArrayList 相对应的,LinkedList 中也有一个值得好好研究的接口,那就是 Deque
接口。
Deque - double-ended queue
,中文名为双端队列。
我们都知道 Queue
是一个队列,遵循 FIFO 准则,我们也知道 Stack
是一个栈结构,遵循 FILO 准则。 而 Deque
这个双端队列就厉害了,它既可以实现栈的操作,也可以实现队列的操作,换句话说,实现了这个接口的类, 既可以作为栈使用也可以作为队列使用 。
如何作为队列使用呢? Deque
实现了 Queue
,所以 Queue
所有的方法 Deque
都有,下面比较的是 Deque
区别 Queue
的方法:
Queue | Deque |
---|---|
add(e) | addLast() |
offer(e) | offerLast() |
remove() | removeFirst() |
poll() | pollFirst() |
element() | getFirst() |
peek() | peekFirst() |
如何作为栈使用呢? 下面我们来看看下双端队列作为栈 Stack
使用的时候方法对应关系。
Stack | Deque |
---|---|
push(e) | addFist(e) |
pop() | removeFirst() |
peek() | peekFirst() |
因为篇幅有限,具体实现源码就不带大家去分析了。
引一篇好文: 搞懂 Java LinkedList 源码
这是一个很频繁的面试点,故记录一下。
以下是源码部分。
add()
方法开始入手 ensureCapacityInternal(size + 1)
确认当前数组可否容纳 size + 1
个元素,如果不够进行扩容 grow(minCapacity)
这就是具体扩容的逻辑
oldCapacity + (oldCapacity >> 1)
,也就是旧容量的 1.5
倍 Arrays.copyOf()
这个方法,把原数组整个复制到新数组中, 这个操作代价很高,所以 很多地方包括阿里开发手册上也会建议 在集合初始化的时候就指定好大概的容量大小,减少扩容的次数 。
ArrayList 与 Vector 的底层实现都是 Object 数组,所以两者使用和特性上非常类似。
不同的是,
如果是想要达到线程安全的目的,Vector 有其他的替代方案:
Collections.synchronizedList()
得到一个线程安全的ArrayList(这类的Collections.synchronized * () 就是一层Wrapper,看源码就知道了)