Java集合类详解二List接口

ArrayList

简介

ArrayList可调整大小的数组的实现List接口,实现所有可选列表操作，并允许所有元素，包括null，不同步。源代码分析

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	private static final int DEFAULT_CAPACITY = 10；

}

它继承了AbstractList类，实现了List、RandomAccess、Cloneable、java.io.Serializable接口，所以是一个有序集合，有随机访问的功能，可以被克隆和序列化，默认初始容量为10

主要方法：

1.isEmpty

 public boolean isEmpty() {
        return size == 0;
    }
//判断是否为空

2.indexOf

public int indexOf(Object o) {
      if (o == null) {
          for (int i = 0; i < size; i++)
              if (elementData[i]==null)
                  return i;
      } else {
          for (int i = 0; i < size; i++)
              if (o.equals(elementData[i]))
                  return i;
      }
      return -1;
  }
  //给定对象，返回下标

3.get

public E get(int index) {    
     rangeCheck(index);     
     return elementData(index);
    }
//返回此列表中指定位置的元素。

4.add

public void add(int index, E element) {         
  rangeCheckForAdd(index);      
  ensureCapacityInternal(size + 1);  // Increments modCount!!
 System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
  elementData[index] = element;
  size++;
    }
    //在此列表中的指定位置插入指定的元素。

5.remove

public E remove(int index) {        
  rangeCheck(index);        
  modCount++;
  E oldValue = elementData(index);        int numMoved = size - index - 1;
  if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
  elementData[--size] = null; // clear to let GC do its work        
  return oldValue;
    }
//删除该列表中指定位置的元素。

6.clear

public void clear() {        
 modCount++;         // clear to let GC do its work
 for (int i = 0; i < size; i++)
            elementData[i] = null;       
             size = 0;
    }
    //清空所有元素

7.iterator

public Iterator<E> iterator() {
        return new Itr();
    }
    //以正确的顺序返回该列表中的元素的迭代器。

特点：

ArrayList内部封装了一个Object类型的数组，所以增加删除都是数组移位操作，把后面的向前移动，所以删除增加的效率低，插入同理，如果插入到队列首，需要全部移位，所以效率低，get方法直接取第几个下标复杂度为O(1),add直接在后面插，复杂度O(1)。总结，ArrayList查询效率高，增加删除效率低.

遍历

1）Iterator：迭代输出，是使用最多的输出方式
2）Listerator：是Iterator的子接口，专门用于输出List中的内容
3）foreach：增强for循环
4）for循环

LinkedList

简介

LinkedList本质是一个双向链表，它也可以被当作堆栈、队列或双端队列进行操作。源代码分析：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
}

它继承了AbstractSequentiaList类，实现了List、Deque、Cloneable、java.io.Serializable接口，所以是一个有序集合，可以当双端队列，可以被克隆和序列化，并且可以为null，不同步。

主要方法

1.getFirst

public E getFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return f.item;
   }
   //返回此列表中的第一个元素。

2.getLast

public E getLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return l.item;
   }
   //返回此列表中的最后一个元素。

3.removeFirst

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    //从此列表中删除并返回第一个元素。

4.removeLast

public E removeLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return unlinkLast(l);
   }
   //从此列表中删除并返回最后一个元素

5.addFirst

public void addFirst(E e) {
       linkFirst(e);
   }
   //在该列表开头插入指定的元素。

6.addLast

public void addLast(E e) {
        linkLast(e);
    }
    //在该列表末尾插入指定的元素。

7.contains

public boolean contains(Object o) {
       return indexOf(o) != -1;
   }
   //如果此列表包含指定的元素，则返回 true 。

8.add

public void add(int index, E element) {         
checkPositionIndex(index);        
 if (index == size)
   	linkLast(element);
 else
         linkBefore(element, node(index));
    }
    //在此列表中的指定位置插入指定的元素。

9.remove

public E remove(int index) {
       checkElementIndex(index);
       return unlink(node(index));
   }
   //删除该列表中指定位置的元素。

10.indexOf

public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            } }
        return -1;
    }
    //返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。

特点：

LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。它包含一个非常重要的内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。它不存在LinkedList容量不足的问题。
LinkedList是链表结构，虽然不需要维护容量大小，但是每次增加都需要新建entry对象，对性能有影响，LinkedList插入位置效率非常高，删除时，首先通过循环找到删除的元素，如果在前半段则从前面开始找，如果在后半段则从后半段找，效率非常高，但如果元素在中间，则几乎要遍历半个List，在拥有大量元素的情况下，效率很低，get方法需要依次遍历，时间复杂度O(n);remove、add（E）、时间复杂度O(1),add(index,E)添加几个元素后，需要先查找到第几个元素，直接指针指向元素，复杂度O(n).
总结：增加，删除效率高，查找效率低。

遍历

1）Iterator：迭代输出，是使用最多的输出方式
2）Listerator：是Iterator的子接口，专门用于输出List中的内容
3）foreach：增强for循环
4）for循环

Vector

简介

Vector和ArrayLis结构差不多，最主要区别，Vector中的操作是线程安全的。线程安全，所以效率低。

综合比较

ArrayList:基于动态数组，占用空间连续，寻址容易，查询速度快，但是，增加和删除效率非常低，线程不安全。 ArrayList想要在指定位置插入或删除元素时，主要耗时的是System.arraycopy动作，会移动index后面所有的元素。
LinkedList:基于双向链表，占用空间不连续，寻址困难，查询速度慢，但是，增加和删除效率非常高，线程不安全。LinkedList主耗时的是要先通过for循环找到index，然后直接插入或删除。

Vector：是基于JDK1.0，线程安全。但是效率低，已经不用了。