list接口的实现类ArrayList类，Vector类，LinkedList类

list接口(基础)

特点：实现list接口的类，有顺序，并且存入时允许出现重复值;

list接口的实现类

ArrayList类(最常用的list接口的实现类)

存储结构:

ArrayList集合中是按照Object[ ]数组存储的;

//<T>中T决定数组中存放的数据的数据类型
ArrayList<String> list01 = new ArrayList<String>();

初始化：

// 使用无参构造方法，按照空数组的方式初始化内部数组
// 第一次添加元素时，长度初始化为默认值10
ArrayList<String> list1 = new ArrayList<String>(); 	
// 使用有参构造方法，按照指定的容量，初始化内部数组
// 长度初始化为指定值38
ArrayList<String> list2 = new ArrayList<String>(38);

扩容机制：

当数组容量不足时，自动扩容，扩容后的新数组长度是原数组长度的1.5倍（newCapacity = oldCapacity + (oldCapacity >> 1);）;

//ArrayList的扩容的源代码   JDK1.8
private void grow(int minCapacity) {
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	elementData = Arrays.copyOf(elementData, newCapacity);
}

当扩容时，扩容的长度小于零时,抛出OutOfMemoryError错误，最小长度大于Integer的最大值-8时，扩容的新数组长度为Integer的最大值，若是小于Integer的最大值-8，扩容的新数组长度是Integer的最大值-8;

// MAX_ARRAY_SIZE     Integer的最大值-8
// Integer.MAX_VALUE  Integer的最大值
// minCapacity    最小需要的数组长度
private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0)
		throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE:MAX_ARRAY_SIZE;
}

常用方法可参考ArrayList集合的常用方法

Vector类

特点(相比ArrayList类而言):

Vector集合的方法中大部分使用了synchronized同步锁，线程安全，不过由于加入了锁，导致性能比较差;

存储结构:

Vector集合中是按照Object[ ]数组存储的;

初始化：

// 无参构造方法创建Vector集合，内部数组长度默认为10
Vector<String> list1 = new Vector<String>();
// 有参构造方法创建Vector集合，内部数组长度由传入的参数决定
// 初始长度为18
Vector<String> list2 = new Vector<String>(18);
// 有参构造方法创建Vector集合
// 内部数组长度由出入的第一个参数决定，每次扩容增长由第二个参数决定
// 初始长度为18，每次增长5个长度
Vector<String> list3 = new Vector<String>(18,5);

扩容机制：

当数组容量不足时，自动扩容①扩容后的新数组长度是原数组长度的2倍(无参构造方法，只有一个参数的有参构造)②扩容后的新数组长度比原来的数组长度多第二个参数个(有参构造方法传入两个参数);

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //用于判断新数组长度是使用旧数组长度的二倍，还是增长第二个参数个
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    	//和ArrayList类中的hugeCapacity()方法作用一致
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

常用方法：

Vector类的常用方法与ArrayList类的常用方法基本类似；

LinkedList类

特点(相比ArrayList类而言)：

LinkedList集合在插入和删除操作速度比较快，但查询和遍历操作相对较慢;

存储结构：

LinkedList集合在存储结构上采用了双向链表的方式存储，其中每一个块存储的是一个Node对象(Node类是LinkedList中的静态内部类),在Node对象中item保存当前节点的数据，prev指向上一个节点，next指向下一个节点;

扩容方式：

由于LinkedList集合采用是双向链表存储的，因此每添加一个元素，就会创建一个Node对象，默认添加至链表尾部;

常用方法：

除去实现了List接口的类都有的方法之外，LinkedList中也包含了一些独有的方法;

(1) addFirst()方法和addLast()方法

作用：给头部添加元素(addFirst),给尾部添加元素(addLast);

参数：需要添加的元素;

返回：无;

List<String> list = Arrays.asList("AAA","BBB","CCC");
LinkedList<String> lklist = new LinkedList<String>(list);
lklist.addFirst("DDD");
System.out.println(lklist);//输出：[DDD, AAA, BBB, CCC]
lklist.addLast("EEE");	
System.out.println(lklist);//输出：[DDD, AAA, BBB, CCC, EEE]

(2) getFirst()方法和getLast()方法

作用：获取链表头部元素(getFirst),获取链表尾部元素(getLast);

参数：无;

返回：获取到的元素;

List<String> list = Arrays.asList("AAA","BBB","CCC");
LinkedList<String> lklist = new LinkedList<String>(list);
System.out.println(lklist.getFirst());//输出：AAA
System.out.println(lklist.getLast());//输出：CCC

(3) removeFirst()方法和removeLast()方法

作用：删除链表头部元素(removeFirst),删除链表尾部元素(removeLast);

参数：无;

返回：删除的元素;

//当需要删除的元素为空时抛出NoSuchElementException异常
List<String> list = Arrays.asList("AAA","BBB","CCC","DDD","EEE");
LinkedList<String> lklist = new LinkedList<String>(list);
System.out.println(lklist.removeFirst());//输出：AAA
System.out.println(lklist);//输出：[BBB, CCC, DDD, EEE]
System.out.println(lklist.removeLast());//输出：EEE
System.out.println(lklist);//输出：[BBB, CCC, DDD]

(4) peek()方法,peekFirst()方法和peekLast()方法

作用：检查头部元素是否为空(peek,peekFirst),检查尾部元素是否为空(peekLast);

参数：无;

返回：如果为空返回null,不为空返回该元素值;

List<String> list = Arrays.asList("AAA","BBB","CCC","DDD","EEE");
LinkedList<String> lklist = new LinkedList<String>(list);
System.out.println(lklist.peek());//输出：AAA
System.out.println(lklist.peekFirst());//输出：AAA
System.out.println(lklist.peekLast());//输出：EEE

(5) poll()方法,pollFirst()方法和pollLast()方法

作用：检查头部元素,并删除(poll,pollFirst),检查尾部元素，并删除(pollLast);

参数：无;

返回：如果为空返回null,不为空返回该元素值并将其删除;

// poll()方法在集合中的元素为空时,返回一个null
List<String> list = Arrays.asList("AAA","BBB");
LinkedList<String> lklist = new LinkedList<String>(list);
System.out.println(lklist.poll());//输出：AAA
System.out.println(lklist);//输出：[BBB]
System.out.println(lklist.pollFirst());//输出：BBB
System.out.println(lklist);//输出：[]
System.out.println(lklist.pollLast());//输出：null

(6) pop()方法

作用：弹出首部元素;

参数：无;

返回：被弹出的元素;

List<String> list = Arrays.asList("AAA","BBB","CCC","DDD","EEE");
LinkedList<String> lklist = new LinkedList<String>(list);
System.out.println(lklist.pop());//输出：AAA
System.out.println(lklist.pop());//输出：BBB
System.out.println(lklist);//输出：[CCC, DDD, EEE]