博客

list集合，继承java.util.collection接口,是java.util包下的有序集合，允许null值

list集合特性

• 有序：list集合基础是数组，集合元素下标有序
• 非线程安全
• 元素可重复

list集合实现类

1）ArrayList： 底层数组，查询快，增删慢，需要1.5倍扩容

2）LinkedList: 底层双向链表，查询慢，增删快，链表结构无需扩容

3）Vector：底层数组，线程安全

ArrayList删除元素

因为ArrayList底层为数组，删除元素涉及到数组下标移动，所以不能直接使用list的remove方法

//数组下标越界异常
for(int l=0;l<list.size();l++) {
    if(list.get(l).equals(1)) {
        list.remove(l);
    }
}

//迭代器
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
    if(iterator.next().equals(1)) {
        iterator.remove();
    }
}

ArrayList添加元素并发异常

java.util.ConcurrentModificationException

//Collection的迭代器
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
    if(iterator.next().equals(1)) {
        list.add(6);
    }
}
		
//list的迭代器
ListIterator listIterator = list.listIterator();
while(listIterator.hasNext()) {
	if(listIterator.next().equals(1)) {
		listIterator.add(6);
	}
}

• 迭代器的next会调到checkForComodification方法，校验与其修改次数和实际修改次数，不同抛出并发异常
• collection的迭代器使用list的add，listiterator的add也调到了list的add，不同的是listiterator处理了预期修改次数和实际修改次数(this.expectedModCount = ArrayList.this.modCount)。
• 那为什么collection的remove方法不会抛出异常呢，因为迭代器的删除也有expectedModCount = modCount;

list的扩容

都知道，list的底层是数组，数组的长度必须指定且不可变，list是如何保证长度可变的呢，这就涉及到了list的扩容

1）在new一个list集合的时候，默认初始化了一个空数组

2）list默认容量为10，在添加第一个元素时，调用add方法出发第一次扩容，此时list长度为1，最大可用容量为10，将默认最小长度10与期望长度比较取最大值

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

{ return Math.max(DEFAULT_CAPACITY, minCapacity); }

3）当添加超过10个元素时触发第二次扩容，每次扩容长度为oldCapacity + (oldCapacity >> 1)即原数组长度+原数组长度/2，将现有数组copy到新定义长度数组中

4）若添加第一个元素之后再次添加15个元素，此时，判断容量值若小于期望值，则新数组长度为期望值，此时数组长度为16

if (newCapacity – minCapacity < 0) newCapacity = minCapacity;

5）扩容调用System.arraycopy方法性能消耗严重，若拷贝一个指定长度的数组，则在初始化时定义好集合长度防止多次扩容提升性能

6）扩容的优点：1）扩容采用1.5倍扩容机制，默认最小容量10，扩容呈递增，可以保证扩容前期，小容量扩容，够用且减少内存浪费，后期大容量扩容保证快速扩容提升性能

7）扩容并不是无限扩大，list的最大容量为Integer的最大值，超过jvm则不再分配内存

ArrayList和LinkedList的区别

ArrayList底层数组，有下标，查询快，但同时数组结构导致ArrayList在修改元素时需要处理元素下标和扩容问题，所以，增删相对慢

LinkedList底层链表，不需要扩容，修改元素时只需要挪动前后节点的指针即可，所以增删快，但链表结构使linkedlist在查询时需要依次查询每节点元素是否符合要求，所以，查询慢