摘要：底层使用的是双向链表数据结构之前为循环链表，取消了循环。快速随机访问就是通过元素的序号快速获取元素对象对应于方法。而接口就是用来标识该类支持快速随机访问。仅仅是起标识作用。，中文名为双端队列。不同的是，是线程安全的，内部使用了进行同步。
前言
学习情况记录
时间：week 2
SMART子目标 ：Java 容器
记录在学习Java容器 知识点中，关于List的需要重点记录的知识点。
知识点概览：
ArrayList 与 LinkedList对比
ArrayList 中的 RandomAccess 接口 是什么？
LinkedList 中的 Deque 接口 是什么？
老调常谈 之 ArrayList 扩容机制
ArrayList 与 Vector 对比
ArrayList 与 LinkedList对比
底层数据结构：
ArrayList 底层使用的Object数组，默认大小 10。
**
LinkedList 底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别）。LinkedList 包含了3个重要的成员：size、first、last。size是双向链表中节点的个数，first和last分别指向第一个和最后一个节点的引用。
插入和删除是否受元素位置的影响：
由于底层实现的影响，ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。实际就是近似O(n)。
而LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）
是否支持快速随机访问：这个也是由底层实现决定的，LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用：ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放prev 指针和next 指针以及数据）。
ArrayList 中的 RandomAccess 接口 是什么？前面的图中我们可以看到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这种没有实现的来说，两种遍历方式效率差距就有点大了。这主要是因为底层实现不同。
LinkedList 中的 Deque 接口是什么？与 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) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
因为篇幅有限，具体实现源码就不带大家去分析了。
引一篇好文：搞懂 Java LinkedList 源码
老调常谈 之 ArrayList 扩容机制这是一个很频繁的面试点，故记录一下。
以下是源码部分。
从 add()方法开始入手
ensureCapacityInternal(size + 1) 确认当前数组可否容纳 size + 1 个元素，如果不够进行扩容
grow(minCapacity) 这就是具体扩容的逻辑
新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的1.5倍
扩容操作 需要 调用 Arrays.copyOf()这个方法，把原数组整个复制到新数组中，这个操作代价很高，所以 很多地方包括阿里开发手册上也会建议 在集合初始化的时候就指定好大概的容量大小，减少扩容的次数。
ArrayList 与 Vector 对比ArrayList 与 Vector 的底层实现都是 Object 数组，所以两者使用和特性上非常类似。
不同的是，
Vector 是线程安全的，内部使用了synchronized 进行同步。这导致了 Vector 性能非常不好。相比较的话，推荐用ArrayList，然后自己控制同步。
Vector 每次扩容都是2 倍大小，而不是1.5
如果是想要达到线程安全的目的，Vector 有其他的替代方案：
使用 Collections.synchronizedList() 得到一个线程安全的ArrayList（这类的Collections.synchronized*() 就是一层Wrapper，看源码就知道了）
也可以使用J.U.C中的 CopyOnWriteArrayList 读写分离，后面的内容会有详细介绍
参考搞懂 Java LinkedList 源码
《码出高效》
《疯狂Java讲义》
github cs-note
java guide
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/75364.html
摘要：而在集合中，值仅仅是一个对象罢了该对象对本身而言是无用的。将这篇文章作为集合的总结篇，但觉得没什么好写就回答一些面试题去了，找了一会面试题又觉得不够系统。 前言 声明，本文用的是jdk1.8 花了一个星期，把Java容器核心的知识过了一遍，感觉集合已经无所畏惧了！！(哈哈哈....)，现在来总结一下吧~~ 回顾目录： Collection总览 List集合就这么简单【源码剖析】 Ma...
摘要：体现的就是适配器模式。数组对象集合世界中的机制机制集合世界中比较常见的错误检测机制，防止在对集合进行遍历过程当中，出现意料之外的修改，会通过异常暴力的反应出来。而在增强循环中，集合遍历是通过进行的。 前言 学习情况记录 时间：week 2 SMART子目标 ：Java 容器 记录在学习Java容器 知识点中，关于List的重点知识点。 知识点概览： 容器中的设计模式 从Array...
摘要：今天主要讲解的是本文力求简单讲清每个知识点，希望大家看完能有所收获一和回顾线程安全的和我们知道是用于替代的，是线程安全的容器。使用迭代器遍历时不需要显示加锁，看看与方法的实现可能就有点眉目了。 前言 只有光头才能变强 showImg(https://segmentfault.com/img/remote/1460000016931828?w=1120&h=640); 前一阵子写过一篇C...
摘要：线程不安全底层数据结构是链表。的默认初始化容量是，每次扩容时候增加原先容量的一半，也就是变为原来的倍删除元素时不会减少容量，若希望减少容量则调用它不是线程安全的。 前言 声明，本文用得是jdk1.8 前一篇已经讲了Collection的总览：Collection总览，介绍了一些基础知识。 现在这篇主要讲List集合的三个子类： ArrayList 底层数据结构是数组。线程不安全 ...
摘要：集合中成员很丰富，常用的集合有，，等。实现接口的集合主要有。集合中不能包含重复的元素，每个元素必须是唯一的。而以作为实现的构造函数的访问权限是默认访问权限，即包内访问权限。与接口不同，它是由一系列键值对组成的集合，提供了到的映射。 原文地址 Java集合 Java集合框架：是一种工具类，就像是一个容器可以存储任意数量的具有共同属性的对象。 Java集合中成员很丰富，常用的集合有Arra...
阅读 2569·2021-09-06 15:02
阅读 3198·2021-09-02 10:18
阅读 2820·2019-08-30 15:44
阅读 684·2019-08-30 15:43
阅读 1947·2019-08-30 14:08
阅读 2757·2019-08-30 13:16
阅读 1395·2019-08-26 13:52
阅读 930·2019-08-26 12:21
