ArrayList 底层是一个数组，让我们了解ArrayList到底是什么。
首先ArrayList都知道查找快，增删慢，了解一下为什么？
看一下源码：
```
publicclassArrayListextendsAbstractList
implementsList,RandomAccess,Cloneable,java.io.Serializable
可以知道ArrayList中实现了RandomAccess这个接口，追踪一下：
publicinterfaceRandomAccess{
}
```
what？实现是接口是空的？那怎么回事？原来是这样啊！
既然我们知道他是在集合中，那么我就顺着他的父类寻找，先看一下List，没有发现，List在向上是collection，这时我们看看他的方法：
```
@SuppressWarnings({"rawtypes","unchecked"})
publicstaticvoidshuffle(Listlist, Random rnd){
intsize =list.size();
if(size < SHUFFLE_THRESHOLD ||listinstanceof RandomAccess) {
for(inti=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
}else{
Object arr[] =list.toArray();
// Shuffle array
for(inti=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));
// Dump array back into list
// instead of using a raw type here, it's possible to capture
// the wildcard but it will require a call to a supplementary
// private method
ListIterator it =list.listIterator();
for(inti=0; i
it.next();
it.set(arr[i]);
}
}
}
privatestaticvoidswap(Object[] arr,inti,intj){
Object tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
```
publicclassCollections
这样就特别清晰了！源码其实就是一个for循环！
ArrayList中初始长度为10，数组扩容1.5倍+1
```
privatestaticfinalintDEFAULT_CAPACITY =10;
publicbooleanadd(E e){
ensureCapacityInternal(size +1);// Increments modCount!!
elementData[size++] = e;
returntrue;
}
privatevoidensureExplicitCapacity(intminCapacity){
modCount++;
// overflow-conscious code
if(minCapacity - elementData.length >0)
grow(minCapacity);
}
privatevoidgrow(intminCapacity){
// overflow-conscious code
intoldCapacity = elementData.length;
intnewCapacity = oldCapacity + (oldCapacity >>1);//右移一位除以2
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);
}
```
缺点是向指定的索引位置插入对象或删除对象的速度较慢.因为指向索引位置插入对象时,会将指定索引位置及之后的所有对象相应向后移动一位
Vector集合与ArrayList集合没有本质区别，因为Vector中方法和ArrayList的方法是一致的，但是每个方法上都有synchronized
关键字，所以说Vector集合是线程安全，但是也正因为如此，vector更浪费资源。
LinkList底层是一个双向链表，查询慢，插入删除快。
```
voidlinkLast(E e){
finalNode l = last;
finalNode newNode =newNode<>(l, e,null);
last = newNode;
if(l ==null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
privatevoidlinkFirst(E e){
finalNode f = first;
finalNode newNode =newNode<>(null, e, f);
first = newNode;
if(f ==null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
voidlinkLast(E e){
finalNode l = last;
finalNode newNode =newNode<>(l, e,null);
last = newNode;
if(l ==null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
publicintlastIndexOf(Object o){
intindex = size;
if(o ==null) {
for(Node x = last; x !=null; x = x.prev) {
index--;
if(x.item ==null)
returnindex;
}
}else{
for(Node x = last; x !=null; x = x.prev) {
index--;
if(o.equals(x.item))
returnindex;
}
}
return-1;
}
publicintindexOf(Object o){
intindex =0;
if(o ==null) {
for(Node x = first; x !=null; x = x.next) {
if(x.item ==null)
returnindex;
index++;
}
}else{
for(Node x = first; x !=null; x = x.next) {
if(o.equals(x.item))
returnindex;
index++;
}
}
return-1;
}
```
