集合框架

1. 集合实现了动态保存

2. 集合提供了方便的操作方法

Collection：单列集合

List 单列集合 有序集合 可重复集合

ArrayList

1. ArrayList可以加入 NULL值，且可加入多个
   

2. ArrayList是数组实现存储的
   

3. ArrayList是线程不安全的
   

源码：

1. ArrayList中维护了一个Object[]类型的 elementData
   

2. 扩容机制：

1. 使用无参构造器构造时，初始化长度为0，插入数据后，扩容elementData长度到10，再次扩容时，扩容至原来的1.5倍
   

2. 使用有参构造器时，elementData的长度为初始的指定大小，需要扩容时，扩容至elementData长度的1.5倍

3. 扩容机制的原因：

 
// 以无参构造ArrayList的扩容为例





 
// 调用add方法后，会调用方法：ensureCapacityInternal

 
public boolean 
add
(

E e
) 
{

        
ensureCapacityInternal
(size 
+ 
1
)
;  
// Increments modCount!!

        elementData
[size
++
] 
= e
;

        
return 
true
;

    
}

 
// 先调用calculateCapacity再调用ensureExplicitCapacity

    
private 
void 
ensureCapacityInternal
(
int minCapacity
) 
{

        
ensureExplicitCapacity
(
calculateCapacity
(elementData
, minCapacity
)
)
;

    
}

 
// 在方法中calculateCapacity，判断了初始化的elementData是否为空，若为空则返回大小为DEFAULT_CAPACITY, minCapacity中的最大值，此时minCapacity = 0，而DEFAULT_CAPACITY 默认值为10

    
private 
static int 
calculateCapacity
(
Object
[
] elementData
, int minCapacity
) 
{

        
if 
(elementData 
== 
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
) 
{

            
return Math
.
max
(
DEFAULT_CAPACITY
, minCapacity
)
;

        
}

        
return minCapacity
;

    
}

 
// 判断最小需要空间是否大于目前空间的长度，若大于则需要扩容，调用grow方法

    
private 
void 
ensureExplicitCapacity
(
int minCapacity
) 
{

        modCount
++
;

//java学习交流:737251827  进入可领取学习资源及对十年开发经验大佬提问，免费解答！

        
// overflow-conscious code

        
if 
(minCapacity 
- elementData
.length 
> 
0
)

            
grow
(minCapacity
)
;

    
}

 
// 在grow方法中，首先把elementData的长度赋值给了oldCapacity，再用oldCapacity计算新的空间，此时：oldCapacity = 0；newCapacity = 0+0/2=0，minCapacity = 10；通过if判断得到最后newCapacity = 10，即未初始化长度时，第一次扩容会扩增到长度为10。

 
// 注：oldCapacity >> 1 即 oldCapacity/2 

 
// 所以 newCapacity = oldCapacity + oldCapacity/2  即扩容1.5倍

    
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
)
;

    
}

LinkedList

1. 底层的数据结构是双向链表和双端队列
   

2. 可以添加任何元素、可以重复、可以为null
   

3. 线程不安全，没有实现同步、互斥

源码：

1. LinkedList维护了size（元素个数）first（指向首节点）last（指向末节点）

2. 每个节点（Node对象）维护了prev（指向前一个节点） next（指向下一个节点） item（数据）
   

3. 增、删数据的时候是通过改变该节点前后节点的指向关系实现的，不牵扯数组，不扩容，相对效率更高
   

// add方法调用linkLast


void 
linkLast
(

E e
) 
{

     
// 创建一个Node对象l，此时l=last为null

        final Node
<
E
> l 
= last
;

     
// 创建一个Node对象newNode且自定参数，则newNode数据结构为： prev：null item：e next：null

        final Node
<
E
> newNode 
= 
new 
Node
<
>
(l
, e
, 
null
)
;

     
// last 指向newNode节点

        last 
= newNode
;

     
// 此时为ture

        
if 
(l 
== 
null
)

            
// first 指向newNode

            first 
= newNode
;

        
else

            l
.next 
= newNode
;

        size
++
;

        modCount
++
;

    
}


// 此时数据已经插入，总体结构


// 链表：first指向newNode，last指向newNode，size=1


// Node节点：prev：null item：e next：null