引言
List是我们能开发中最场用到的一种集合容器,也是第三方框架中最常用到的集合容器,用到的频率屈居老二,除了老大String。
其API简单上手,使用起来也很方便，我们平时很多时候都是不假思索就用起来了，我们有没有想过是不是所有场景都该用List,是不是所有场景都该用ArrayList,是不是有的场景该选择使用LinkedList呢，是否可以选择Set?
预备知识
1.两者都是Collection的子类，都实现了List接口。
2.两者都实现了Coloneable和Serializable接口,支持克隆和序列化操作。
3.两者都是AbstractList的子类。
4.使用时我们一般都是用List<TypeReference>泛型形式来构造一个集合对象。
5.两者容器大小都是静态固定的，如果下表越界的话都会抛出IndexOutOfBoundsException异常。
注意:LinkedList的首个元素没有前驱节点而末元素是没有后继节点，首尾并不相连。我们不要误以为它是循环链表。
ArrayList类图.png
LinkedList类图.png
-
不同点
本质上是一个既是一个双端队列,也是一个双向链表，
本质上是一个数组(链表)，只不过其可以动态扩容。
-
我们来说明一下
数组的容量动态大小。
扩容算法描述:当没有初始化的情况下，第一次扩容为默认10个大小,往后当size超过这个容量的时候就进行n+n/2的方式进行扩容,当有足够容量的时候，每次添加的时候就不会扩容,这样大大增加了往尾部添加元素的效率。初始化大小为10的扩容数列是:{10，15，22，33，49.........}，依次类推即可。动态数组默认的最大容量是MAX_VALUE = 0x7fffffff=2^31-1,如果在添加数据的情况下出现内存溢出也会抛出内存溢出异常。
优缺点说明
是个可动态扩容的数组,是带有下表索引数组的一个容器，适合用来检索数据.
是一个双端链表,并且每个数据都包含了Node节点，每个Node都包含了Prev(前驱结点)与Next(后继节点)以及item(数据节点).适合随机添加与插入和删除操作,LinkedList不需要动态扩容。
性能对比:
-
//ArrayList向尾部添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//LinkedList向尾部添加元素
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element。
*空时将first的后继节点指向新添入的节点，非空时将
* Last的next指向新的节点
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
-
//这是ArrayList的指定位置修改函数
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
··································································
//这是 $\color{red}{LinkedList}$的修改指定位置的元素
public E set(int index, E element) {
checkElementIndex(index);
//这里折中法查找指定位置上的Node节点,双向循环队列必须这么做啊！
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
Node<E> node(int index) {
// assert isElementIndex(index);
//
if (index < (size >> 1)) {
//如果是索引是前半段则从折中以first节点后继节点寻找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//如果是索引是前半段则从折中以last前驱节点寻找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
3.For 循环取值和迭代器取值要远远高于LinkedList的取值
。
只要对比他们的源码就可以直观地分析出来了。
//List通过索引取值时直接数组下标取值,相当于hash取值一样的效率，效率级别为O(1)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//而LinkedList 是没有数组下标的概念的，只有Node节点的概念，所以通过下表去找对象的时候只能通过节点去next或prev查找
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
4.根据索引移除元素在效率上要低于
,通过源代码分析可以确认这个结论。
public E ArrayList.remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
5.在迭代器中移除元素的效率同样也低于于
,亲测代码。
Iterator arrayListIterator = arrayList.iterator();
while (arrayListIterator.hasNext()) {
arrayListIterator.next();
arrayListIterator.remove();
}
long end = System.currentTimeMillis();
System.out.println(String.format("ArrayList 迭代器 中删除元素耗时%s毫秒", end - start));
start = System.currentTimeMillis();
Iterator linkedIterator = linkedList.iterator();
while (linkedIterator.hasNext()) {
linkedIterator.next();
linkedIterator.remove();
}
end = System.currentTimeMillis();
System.out.println(String.format("LinkedList 迭代器 中删除元素耗时%s毫秒", end - start));
作用场景描述
1.我们在平时做查询接口的时候通常都选择ArrayList集合，相比LinkedList和其他Set集合的话,ArrayList的迭代效率更快更适合做协议上的流化输出，并且ArrayList在不需要频繁扩容的情况下往尾部添加数据的效率并不低。如果需要保证线程安全的话,用Collections.SynchronizedList(List)来设置一个有同步器的集合。
2.尽量减少ArrayList的扩容次数，提高性能,知道固定大小的情况下可以设置数组的初始大小,知道大概区间就设置上限初始的Capacity大小。
3.做根据下表去删除和在中间位插入元素时尽量选择LinkedList,原因是ArrayList需要做数组移位操作。而LinkedList只需要改变节点的前驱和后继节点的指向即可。
4.因为LinkedList有双端队列的特性，所以天生适合移除首尾元素，还有更适合添加头节点元素。
ArrayList删除动作.png
补充:ArrayList的数组移位压缩并不慢,做了哪些优化呢？因为用到了System.arrayCopy)(),这个方法是JNI接口。
//Linux copy的方法
void _Copy_conjoint_jints_atomic(jint* from, jint* to, size_t count) {
if (from > to) {
jint *end = from + count;
while (from < end)
*(to++) = *(from++);
}
else if (from < to) {
jint *end = from;
from += count - 1;
to += count - 1;
while (from >= end)
*(to--) = *(from--);
}
}
//Windows
static void pd_conjoint_jints_atomic(jint* from, jint* to, size_t count) {
if (from > to) {
while (count-- > 0) {
// Copy forwards
*to++ = *from++;
}
} else {
from += count - 1;
to += count - 1;
while (count-- > 0) {
// Copy backwards
*to-- = *from--;
}
}
}
网友评论