ArrayList和LinkedList、Vector的优缺点?
一般在面试中可能会被问到arraylist、linkedlist、vector三者相关的区别!
一般来说我想大概都会回答如下的这些:
arraylist底层是数组结构,查询快,增删慢,线程不安全,效率高。
linkedlist底层是链表数据结构,查询慢,增删快,线程不安全,效率高。
vector底层是数组结构,查询快,增删慢,线程安全,效率低。
以上就是最基本的一个优缺点,但是他们的内部结构,具体怎么实现添加查询这一块的,我想应该有一部分人还是不太清楚。
下面我将带领一起去集合的内部看一看具体的代码实现。
arraylist:
首先是arraylist的一个实例化,java提供了一个有参构造和无参构造。下面一起查看代码:
/** * constructs an empty list with the specified initial capacity.
构造具有指定初始容量的空列表。 * * @param initialcapacity the initial capacity of the list 初始容量列表的初始容量 * @throws illegalargumentexception if the specified initial capacity 如果指定的初始容量为负,则抛出illegalargumentexception * is negative */ public arraylist(int initialcapacity) { if (initialcapacity > 0) { this.elementdata = new object[initialcapacity]; } else if (initialcapacity == 0) { this.elementdata = empty_elementdata; } else { throw new illegalargumentexception("illegal capacity: "+ initialcapacity); } }
通过上述我们可以看到,这是arraylist的有参构造,可以自定义集合的初始化长度,否则如果输入的是0那么就使用arraylist自带的默认的数组缓存区。
/** * constructs an empty list with an initial capacity of ten. 构造初始容量为10的空列表。 */ public arraylist() { this.elementdata = defaultcapacity_empty_elementdata; }
使用无参构造,将会创建一个默认长度的数组。初始长度为10。
/** * default initial capacity. 默认初始容量 */ private static final int default_capacity = 10; /** * shared empty array instance used for empty instances. 用于空实例的共享空数组实例 */ private static final object[] empty_elementdata = {};
* 解析add添加方法的全过程,下面的add方法相关的所有源代码,
/** * appends the specified element to the end of this list. 将指定的元素追加到列表的末尾 * * @param e element to be appended to this list 将追加到此列表中的e元素 * @return <tt>true</tt> (as specified by {@link collection#add}) */ public boolean add(e e) {
// 调用自动扩容存储机制,确保自动数组有存储新元素的能力。 ensurecapacityinternal(size + 1); // increments modcount!!
// 自动扩容存储机制处理后,将元素添加到集合的末尾 elementdata[size++] = e; return true; }
private void ensurecapacityinternal(int mincapacity) {
// 判断该数组是否是一个新创建的实例对象 if (elementdata == defaultcapacity_empty_elementdata) {
// 如果是,就设置数组的长度为默认长度 10 mincapacity = math.max(default_capacity, mincapacity); } // 确保能够有储存能力 ensureexplicitcapacity(mincapacity); }
private void ensureexplicitcapacity(int mincapacity) {
// 保存这个列表在结构上被修改的次数。 modcount++; // overflow-conscious code
// 如果默认的长度减去实际数组的长度大于0,那么就调用grow()方法
if (mincapacity - elementdata.length > 0) grow(mincapacity); }
private void grow(int mincapacity) { // overflow-conscious code int oldcapacity = elementdata.length; // 获取数组原始的长度 int newcapacity = oldcapacity + (oldcapacity >> 1); // 获取新的数组的长度 (0 + 0/2) if (newcapacity - mincapacity < 0) // 如果新的值 - 最小值小于0 (0-10) newcapacity = mincapacity; // 将默认值 10 赋值给 新的值 if (newcapacity - max_array_size > 0) // 如果新的值 - 最大长度 大于 0 (0 - 2147483639) > 0 newcapacity = hugecapacity(mincapacity); // 调用方法 // mincapacity is usually close to size, so this is a win: elementdata = arrays.copyof(elementdata, newcapacity); // 复制原本的数组,定义长度,赋值给自己,来达到自动扩容 }
* 总结以上,在arraylist被无参实例化的时候就会被创建一个空的数组,在添加第一个值时,arraylist底层的自动扩容机制将会被执行,也就是private void grow(int mincapacity)这个方法会被调用,给内部的elementdata数组定义初始长度为10,然后再将值添加到数组的末尾。这里面主要就是牵涉到一个自动扩容机制,在每一次添加之前,都会去判断,当前数组长度是否有实际的存储能力,如果没有那么自动扩容机制就会根据当前数组长度+当前长度/2来计算的方式,对当前数组进行扩容。
linkedlist:
* 链接内部结构图
* 查看linkedlist的无参构造和有参构造
* 无参构造
/** * constructs an empty list. // 构造一个空列表 */ public linkedlist() { }
* 有参构造
/** * constructs a list containing the elements of the specified 构造包含指定元素的列表 * collection, in the order they are returned by the collection's 集合,按照集合返回的顺序 * iterator. 迭代器 * * @param c the collection whose elements are to be placed into this list * @throws nullpointerexception if the specified collection is null */ public linkedlist(collection<? extends e> c) { this(); addall(c); }
* 解析add添加方法:
/** * appends the specified element to the end of this list. 将指定的元素追加到列表的末尾 * * <p>this method is equivalent to {@link #addlast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link collection#add}) */ public boolean add(e e) { linklast(e); return true; }
/** * links e as last element. 链接做为最后一个元素 */ void linklast(e e) {
// 将最后一个节点临时存储起来 final node<e> l = last;
// 创建一个新的节点,设置新的节点的上一个节点和当前节点的值 final node<e> newnode = new node<>(l, e, null);
// 将新创建的节点重新存储到专门用于保存最后一个节点的值的对象 last = newnode;
// 判断是否是第一次添加,如果是第一次添加值,那么上一个值一定是null,否则就会一个值 if (l == null)
// 如果是第一次添加,那么我们就要将新创建的节点保存到链表的头first first = newnode; else // 否则就设置l的下一个节点为新的节点
l.next = newnode;
// 长度增加 size++;
// 修改次数 modcount++; }
* 总结以上:从源代码上我们可以看到,linkedlist内部采用的实际上是通过多个节点来保存值,每个节点对象中对它的上一个节点和下一个节点继续记录,以此将所有的节点串联起来,就形成了链表。
vector:
vector其实本质上和arraylist是一样的,底层都是使用了数组来完成,只是vector是从jdk1.0版本开始,arraylist是1.2版本开始,可以理解的是arraylist其实就是用来代替vector的。vector和arraylist最大的区别就是一个是线程安全,一个是线程不安全的。这个我们可以通过查看底层代码来得知。
* 解析add代码
/** * appends the specified element to the end of this vector. 将指定的元素附加到这个向量的末尾 * * @param e element to be appended to this vector * @return {@code true} (as specified by {@link collection#add}) * @since 1.2 */ public synchronized boolean add(e e) { modcount++; ensurecapacityhelper(elementcount + 1); elementdata[elementcount++] = e; return true; }
* 总结上述可得知:相比较arraylist的add方法,我们可以看出,vector的add方法添加的同步锁。
------------------------------------------------------ 分割 -------------------------------------------------------------------
学无止境,永远不要轻言放弃。
推荐阅读
-
基准测试了 ArrayList 和 LinkedList ,发现我们一直用 ArrayList 也是没什么问题的
-
网站推广 内容党和标题党两种软文推广的优缺点
-
【转载】C#中ArrayList集合类和List集合类的比较
-
比较顺序表和链表的优缺点
-
JavaScript之继承的多种方式和优缺点
-
细数ATI和NVIDIA驱动的优缺点
-
Java集合系列(二):ArrayList、LinkedList、Vector的使用方法及区别
-
ArrayList和LinkedList区别(蚂蚁金服面试题)
-
长连接和短连接的定义,优缺点以及使用场景介绍
-
【Java】自定义能储存和装载不同(class)数据类型的ArrayList