前言
在日常的java开发中,我们经常用到各种集合类,而List是其中最常见的一种;以前我们在使用数组的时候,无论是c++或者java,都要指定它的大小;而List居然不用指定大小,太神奇了,接下来让我们仔细分析一下它们的实现
LinkedList:
- 主要成员变量:
transient int size = 0; //List长度
transient Node<E> first;//头指针
transient Node<E> last;//尾指针
- add方法(将元素放入List尾部):
public boolean add(E e) {
linkLast(e);
return true;
}
再看linkLast方法:
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++;
}
也就是说,每次添加一个节点到末尾时,都是新申请一个链表节点,然后再缝缝补补,把相关的链表指针接在一起;复杂度为O(1);
再看看另外一个add方法:
- add(int index, E element)(将元素插入到某个下标位置):
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
<p>
再看node()方法(找到下标对应的链表节点):
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;
}
}
其寻址复杂度是O(n)的,唯一的优化点就在于,看下标离头指针近还是离尾指针近,复杂度做了常数上的优化,从n下降到n/2, 但还是O(n);
剩下的删查都涉及到寻址的时间损耗,复杂度也都是O(n),它们的实现都是类似的,就不赘诉了。
小优化:其实如果我们自己实现一个LinkedList,完全可以把指针信息加在节点上,这样就可以避免一些寻址上的时间损耗了。
ArrayList(与c++里的vector类似)
- 成员变量:
transient Object[] elementData; // 存储元素的载体是数组
private int size;//List当前长度
- 主构造方法:
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);
}
}
没有什么特别的,就是申请一个定长的数组
- add(E e)方法:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
第一行是确保数组载体容量足够,后边就是把下标为size+1的元素赋值成e;
它调用了ensureCapacityInternal()方法:
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
又调用了ensureExplicitCapacity()方法:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
再看grow()方法:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
里边关键的一句代码就是:
int newCapacity = oldCapacity + (oldCapacity >> 1);
意思就是,新的数组容量变成原数组的大约1.5倍(看不懂的可以去了解一下位运算),新的数组申请内存之后,再把老的数组里的元素全copy到新数组就完成了;
那么为什么每次容量不足的时候,要扩充到1.5倍呢?通过分析我们可以发现,每次扩充1.5倍容量,那么假设最后容量扩充为n,那么总体上的申请空间的数量近似于:f(n) = n + n * 2/3 + n * (2/3)^2 + n * (2/3)^3 + ... ,根据等比数列公式可以知道,这个表达式的值为: f(n) = 3 * n = O(n)
采用倍增的方法扩容,优点在于总体的复杂度数量级是线性的,但是也不可避免的可能会有空间浪费;在最极端的情况下,会有接近1/3的空间是没有利用上的;因此,在List会很大,且能预先大致估算出List会有多大的前提下,为了减少系统的内存消耗和频繁GC,应尽量使用以下构造方法来申请List:
public ArrayList(int initialCapacity);
- add(int index, E element)方法(将元素插入到指定下标):
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
跟add(E element)方法的最大的差别就在于,在赋值之前,要先把该下标以及后面的元素全都向后移一位,其复杂度为O(n);
- 接下来看get(int index)方法:
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
检查下标合法性,再调用elementData():
E elementData(int index) {
return (E) elementData[index];
}
直接是数组的根据下标随机访问的操作,复杂度是O(1),再强转成E类型就返回了;
- remove(int index)方法:
public E 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;
}
在删除指定下标的元素时,如果这个元素不是最后一个,那么要将后面的元素全部向前移一位,复杂度也是O(n), 另外还有一点就是,删除了这个元素之后,要把最大下标的那个元素赋值成null,方便系统进行GC(系统GC时,会根据对象是否被引用来判断对象是否可以回收)
- remove(Object o)方法:
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
定位到元素位置复杂度为O(n), fastRemove(index)的复杂度也是O(n);
另外,初看这段代码,感觉写得有点“啰嗦”,但实际上确实是有必要的:List元素允许为空,所以要特判该元素是否为空,为空时直接用==null来判断,而不为空时,才能调用equals方法进行比较,否则会有空指针异常;所以这段代码也是JDK严谨性的一种体现;
- 以下表格列出了两者在各种操作下的复杂度:
| 操作\List实现类 | LinkedList | ArrayList |
| ------------- |:-------------:| -----:|
| add(E e) | O(1) | O(1) |
| add(int index, E element) | O(n) | O(n) |
| get(int index) | O(n) | O(1) |
| remove(int index) | O(n) | O(n) |
| remove(Object o) | O(n) | O(n) |
从上表看,LinkedList几乎没有比ArrayList优越的地方;另外,LinkedList相比ArrayList没有0.5倍的空间浪费,但是其每个节点都有前后指针的内存占用,且每次新增一个元素时都要新申请一个Node,而ArrayList则是一次性批量申请;所以,当List长度比较大的时候,肯定是ArrayList效率比较高。
如果说LinkedList有优点的话,可能就是它不需要申请连续的内存,所以建议大家除了极端情况,大部分时候都使用ArrayList。
网友评论