发布于2021-06-12 14:46 阅读(951) 评论(0) 点赞(21) 收藏(3)
本文基于 JDK 1.8.0_191
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
它们都实现 List 接口,说明具备列表的增加、删除、遍历元素等特性。
ArrayList、Vector 额外实现 RandomAccess 接口,说明他们能在常量时间复杂度内快速随机访问元素。
LinkedList 额外实现 Queue 接口,具备队列的入队、出队等特性。
ArrayList
private static final int DEFAULT_CAPACITY = 10; // 定义初始大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 定义列表存储元素数量最大值
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // 现有元素数量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 增加后元素的数量 = 1 + 0.5
if (newCapacity - minCapacity < 0) // 增加后的元素数量 < 现有的空间,不扩容
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity); // 增加后的元素数量 > 大于最大值,尝试分配 Integer.MAX_VALUE 个元素,可能会抛出 OutOfMemoryError
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Vector
public Vector() {
this(10);
}
protected int capacityIncrement; // 扩容数量值,Vector 初始化不指定时默认为 0
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); // 当扩容数量值小于 0,那么扩容比例为原来的两倍;否则扩容的数量为这个值。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
LinkList
transient int size = 0;
ArrayList
protected transient int modCount = 0;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Vector
protected transient int modCount = 0;
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
Vector add() 方法上增加了 synchronized 关键字,使得 Vector 支持多线程环境下的元素增加删除修改操作。
根据数据结构中知识:
顺序表查找元素时间复杂度为 O(1),适用于随机查找元素的场景。
链表增减元素时间复杂度为 O(1),适用于增减元素比较多的场景。
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
LinkedList linkedList = new LinkedList();
Vector vector = new Vector();
long t1, t2;
t1 = System.nanoTime();
for (int i = 0; i < 10000; i++) {
arrayList.add(i);
}
t2 = System.nanoTime();
System.out.println("ArrayList add:" + (t2 - t1));
t1 = System.nanoTime();
for (int i = 0; i < 10000; i++) {
linkedList.add(i);
}
t2 = System.nanoTime();
System.out.println("linkedList add:" + (t2 - t1));
t1 = System.nanoTime();
for (int i = 0; i < 10000; i++) {
vector.add(i);
}
t2 = System.nanoTime();
System.out.println("vector add:" + (t2 - t1));
}
ArrayList add:6810212
linkedList add:3463194
vector add:4442985
添加元素,ArrayList 花费时间比 LinkList 时间长。
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
LinkedList linkedList = new LinkedList();
Vector vector = new Vector();
long t1, t2;
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
linkedList.add(i);
vector.add(i);
}
t1 = System.nanoTime();
for (int i = 0; i < 10000; i++) {
arrayList.get(i);
}
t2 = System.nanoTime();
System.out.println("ArrayList get:" + (t2 - t1));
t1 = System.nanoTime();
for (int i = 0; i < 10000; i++) {
linkedList.get(i);
}
t2 = System.nanoTime();
System.out.println("linkedList get:" + (t2 - t1));
t1 = System.nanoTime();
for (int i = 0; i < 10000; i++) {
vector.get(i);
}
t2 = System.nanoTime();
System.out.println("vector get:" + (t2 - t1));
}
ArrayList get:72482
linkedList get:107975370
vector get:242634
查找元素上,ArrayList 最快
将 ArrayList、LinkList 和 Vetor 进行了简单对比,总体来说:
参考:
ArrayList vs LinkedList vs Vector 区别
原文链接:https://blog.csdn.net/u013151053/article/details/117717788
作者:长这么胖
链接:http://www.javaheidong.com/blog/article/222358/4a11613c4cda6fbfa53a/
来源:java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 java黑洞网 All Rights Reserved 版权所有,并保留所有权利。京ICP备18063182号-2
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!