- ArrayList
- 底层结构就是Object[] 数组，该数组特点是可以存储任意类型的对象，向上转型，在使用时需要向下转型为实际的类型
Object[] o = new Object[2];
o[0] = new String("ss");
o[1] = new Integer(1);
boolean b =(o[0] instanceof String); //true
boolean b2 =(o[1] instanceof String); //false
boolean b3 =(o[1] instanceof Integer); //true
Integer i = (Integer) o[1]; // need cast when using
- 初始容量是10，如果添加时超过容量时，每次扩容为1.5倍
- ArrayList有 Itr内部类，实现Iterator接口，每次调用iterator()方法时，返回new Itr()
- ArrayList实现 RandomAccess 接口，实现随机访问查找，使用index查询的时间复杂度是o1
- remove() 实际上调用复制数组方法，时间复杂度On
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;
}
- LinkedList
- 数据结构是双向队列，有first和last Node
- 其中Node是静态内部类，有prev 和 next 两个指针
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;
}
}
-
队列的最常用方法：
-- offer(E e) 调用 add()/addLast() 最终调用 linkLast()
-- poll() 首先判断Node first 是否为空，空的话返回null，不为空调用removeFirst()
-- peek() 和poll类型，允许返回null -
栈的最常用方法：
-- push(E e) 调用 addFirst() 最终调用 linkFirst()
-- pop() 直接调用 removeFirst() 头结点为空，报异常 因此调用前需要确保 LinkedList非空
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
- get(int index) 调用 node(int index) 时间复杂度为On
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;
}
}
- CopyOnWriteArrayList
- 位于java.util.concurrent 包下
- 是线程安全类，主要使用了ReentrantLock， array 前加了 volatile 修饰
/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
- 写入之前加锁，并且在写入过程中先使用临时数组保存修改好的数组，然后使用setArray方法修改array变量，保证写的原子性
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); // 增加临时数组修改数据
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock(); // 使用完之后务必释放锁
}
}
- 删除时和写入类似，都采用 加锁+新建临时数组
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
- get(int index) 无须加锁，如果在get时其他线程正在修改 array，get方法虽然得不到最新的值，但是不会阻塞线程的执行。
- CopyOnWrite并发容器用于读多写少的并发场景。比如白名单，黑名单，商品类目的访问和更新场景，假如我们有一个搜索网站，用户在这个网站的搜索框中，输入关键字搜索内容，但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中，黑名单每天晚上更新一次。当用户搜索时，会检查当前关键字在不在黑名单当中，如果在，则提示不能搜索