java容器 学习笔记总结 List

List接口

list接口规定了：容器存储的元素是有序的，可以重复的

实现它的实现类主要有ArrayList和LinkedList，还有几乎不用的Vector

ArrayList

内部实现

• 首先内部是用数组来实现的，一个Object数组，名为elementData

• 无参数创建一个ArrayList时，初始化赋值的是一个空数组，只有真正添加元素时，才会分配容量。

  (即向数组中添加第一个元素时，数组容量扩为10)

扩容

容器的扩容向来都是重点

ArrayList的扩容是放到add方法的逻辑的，即添加元素时，才关心扩容的事情。

添加元素（add）：
	判断扩容（ensureCapacityInternal）：//确保容量够，不会越界
		如果当前数组是空数组：//刚刚创建，尚未添加元素
			预期容量改为10 //当存储元素时，至少是要有10个大小的容量的
		否则预期容量是当前size+1
		尝试扩容（ensureExplicitCapacity）：
			如果预期容量大于现在数组的大小：
				扩容1.5倍（grow）//近似，位运算
	添加元素
           

上面的是总结的add方法添加元素的逻辑。在执行添加元素之前，需要进行判断当前容量是否够，不够的话需要进行扩容。

grow方法

• 具体的扩容操作是grow方法，这里用到了位运算
• grow的话，会传入预期容量，会取1.5倍之前容量大小与预期容量的最大值（1开始命中预期容量，后来都是1.5倍，这个也很好理解）
• 如果预期容量大于MAX_ARRAY_SIZE，则容量定位Integer.MAX_VALUE（MAX··是一个常量值）

在进行扩容时，会调用Arrays.copyOf()方法，该方法会在内部创建一个新数组，然后调用System.arraycopy()方法，将旧数组的东西复制到新数组中去。从而实现扩容的操作。

而System.arraycopy()方法，实际上的功能，是将一个数组的一部分复制到另一个数组的一部分中（可以是全部）

想对比来说：前者因为新建了数组，更适合扩容

后者一般从自己拷贝到自己，所以是更适合移动，比如insert（add(xxx,index)）这种需要移动的方法

主动扩容

因为1.5倍扩容（可以理解为0-10-15-22.5-···后面组从1.5），这种机制的话，如果用户需要进行大量存储，则会扩容多次，且每一次都需要O(n)的时间来进行拷贝数组，效率低下。

所以ArrayList还提供了方法给用户，让用户指定容量大小进行扩容，从而减少扩容次数。

ensureCapacity

在删除指定元素时，也是一样，需要调用System.arraycopy()方法，然后将index+1开始的元素移动到index上，时间复杂度O(n)

序列化

因为ArrayList内部的数组长度基本是大于实际存储元素数量的size的，所以进行序列化时，就没有必要把作为实现的内部数组给序列化，于是将elementData用transient进行修饰。

并且还写了writeObject方法和readObject方法来只序列化数组中有元素填充的那一部分。

Fail-Fast

ArrayList中用modCount变量来记录ArrayList结构发生变化的次数：添加or删除or调整数组大小（仅修改元素值不算，要修改结构才算）

这里主要用于多线程的并发安全问题

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。（来自百度百科）

在并发迭代时，进行判断，如果modcount修改了，则可以直接终止，

这个变量之前是volatile修饰的，而现在jdk1.7移除了，因为觉得并发时可以用并发包呀，这个还是留给单线程来用吧。

LInkedList

作为一个常用的List实现类，它用的非常多。

• 实现了List接口和Deque接口
• 双端链表

下面是其一些简单的方法逻辑

add方法：添加节点到尾部

• add://添加节点到尾部
  	linkLast://将节点加到尾部，此处需要判空
             

add(int index, E e)：添加节点到指定位置

• add(int index, E e):
  	如果是尾部（用长度和index来判断），linkLast
  	不是尾部，找到要插入的点（O(n)遍历到指定位置）
  	将其和输入传给linkBefore:
  		进行插入
             

addAll：将集合插入到链表尾部

• 1.检查index范围是否在size之内
  2.toArray()方法把集合的数据存到对象数组中
  3.得到插入位置的前驱和后继节点
  4.遍历数据，将数据插入到指定位置
             

addFirst：添加节点到头部

• 调用了linkFirst方法，操作很简单，没什么好说的

addLast：也是一样的

get(int index)：获取指定位置的节点

• 这个就是调用node方法

indexOf(Object o)：根据对象获得索引

• 从头开始遍历，找到索引

lastIndexOf：

• 从尾开始遍历，找到索引

contains(Object o)：检查对象是否在链表中

• 使用index来判断

整体来说，LinkedList比较简单，其和ArrayList的区别也是显而易见

随口就来，底层实现不一样，是否有高效的随机访问能力，是否有高效的插入能力，存储的效率等等，这些东西都是比较简单的，也就不细说了

Vector

这个就不细说了，和ArrayList差不多，也是通过Object数组实现的，然后其中用到了很多Synchronized关键字，所以其可以满足多线程的安全问题。但也因此性能一般。

一般不用它