List接口、ArrayList类和LinkedList类

1.List接口继承了Collection接口，ArrayList类和LinkedList类实现了List接口。
  扩展方法：1.AnyType get(int index);
           2.AnyType set(int index,AnyType newValue);
           3.void add(int index,AnyType newValue);
           4.void remove(int index);
           5.ListIterator<AnyType> listIterator(int pos);向前向后遍历


2.ArrayList类和LinkedList类的区别。
  ArrayList:get,set快，add,remove慢，在表头插入删除的时候最慢，得移动整个数组
  LinkedList:add,remove快，get,set慢，每次get都得从表头开始遍历O(n)


3.实例说明ArrayList类和LinkedList类的区别。
      {1,2,3,4,5,6,7,8}去除偶数项。
   1.Collection在遍历的时候不能add和remove,否则会报java.util.ConcurrentModificationException。
     我们实现的方式有两种，new一个新的list，然后遍历oldList,把奇数add到newList.第二种方法是使用迭代器遍历，使用迭代器删除偶数。

方法一

private List<Integer> removeEvens1(List<Integer> list) {
		List<Integer> newList = new LinkedList<Integer>();
		for(Integer i : list){
			if(i%2==1){
				newList.add(i);
			}
		}
		return newList;
	}

方法二

private List<Integer> removeEvens2(List<Integer> list) {
		Iterator<Integer> iterator = list.iterator();
		while(iterator.hasNext()){
			int nextValue = iterator.next();
			if(nextValue%2==0){
				iterator.remove();
			}
		}
		return list;
	}

  方法一和方法二说明:
     (1)去除偶数项，LinkedArray，remove()比ArrayList快。
     (2)方法二不需要新new一个list,可以在Intertor中直接删除偶数项。
      (3)for循环遍历，ArrayList耗时O(n),LinkedList耗时O(n*n)。Itertor遍历，所有Collection耗时O(n)。
    总结：效率最高使用LinkedList和第二种方法，耗时O(n)。
     
     
4.ArrayList类的优化方法。
  ensureCapacity(int size),预定义数组长度，如果列表数据大的时候，使用ensureCapacity(int size)可以大大减少因增大数组容量而复制数组的时间。
  trimToSize()，去除数组多余的空间。在arrayList确定的时候，调用该方法可以节省空间。