最近准备把集合框架再深入了解一下，目前看到ArrayList和LinkedList，根据网上资料摘抄做的部分笔记：
关于ArrayList：
顺序容器，底层是Object数组，以便容纳任意类型的对象。区别容量(Capactiy)和当前存储元素个数。没有实现同步。size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比，其余方法大都是线性时间。
方法解析
初始容量大小：private static final int DEFAULT_CAPACITY = 10;
扩容大小：int newCapacity = oldCapacity + (oldCapacity >> 1);即原来的1.5倍
方法和操作数组类似，注意如add()方法中需要扩容时，使用Arrays.copyOf()进行旧数组的扩容，以下是扩容操作：
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//以1.5倍原长度进行扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//使用Arrays.copyOf()进行扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
如remove()方法删除元素后，为了让GC起作用，必须显式的为最后一个位置赋null值。因为如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。使用System.arraycopy()进行移位操作，以下是remove()方法
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);
//清除该位置的引用，让GC起作用
elementData[--size] = null;
return oldValue;
}
其余方法主要是对数组的操作，可以直接参考JDK源码。
关于LinkedList:
LinkedList同时实现了List和Deque接口，既可以看做顺序容器，也可以看做队列，以及栈，不过关于栈和队列，现在首选是ArrayDeque(在该方面有更好的性能)。LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首尾操作元素只需要常数时间。为追求效率LinkedList没有实现同步，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。
底层：双向链表，每个节点用内部类Node表示
//Node内部类
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
方法解析
关键在于正确操作节点内的next和prev两个引用。具体方法可以直接查看JDK源码。 |
|
收藏
淘帖
踩
