Vector, ArrayList, LinkedList分析

原创
2014/03/10 20:09
阅读数 2.2K

Vector分析:

主要特性:有序,可随机访问,可变长,可重复,线程安全等。

其结构图:

其基本属性有:

//存放元素的数组
protected Object[] elementData;
//元素个数
protected int elementCount;
//容量扩容指标,默认以2倍增长
protected int capacityIncrement;

从其构造函数中可以看出,Vector默认容量为10,capacityIncrement默认设为0(<=0时就以2倍扩容):

public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

看几个比较重要的方法,add(), remove():

add方法:

public synchronized boolean add(E e) {
     modCount++;
     ensureCapacityHelper(elementCount + 1); //扩容检测
     elementData[elementCount++] = e; //添加,改变引用
     return true;
 }

 private void ensureCapacityHelper(int minCapacity) {
      if (minCapacity - elementData.length > 0)
            grow(minCapacity);
 }

 private void grow(int minCapacity) {
      int oldCapacity = elementData.length;
      //默认2*oldCapacity, 
      int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                       capacityIncrement : oldCapacity);
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      elementData = Arrays.copyOf(elementData, newCapacity);//拷贝新数组
 }

remove方法,可见删除操作要做复制操作:

public synchronized E remove(int index) {
     modCount++;
     if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
     E oldValue = elementData(index); 
     int numMoved = elementCount - index - 1; //被删除元素后面元素个数
     if (numMoved > 0)
         System.arraycopy(elementData, index+1, elementData, index,
                             numMoved); //将被删除元素后面的元素往前挪
     elementData[--elementCount] = null; //这点很重要,让gc能够回收无引用对象,防止"内存泄漏"
     return oldValue;
}

Vector实现是比较简单明了的,其大部分方法都synchronized同步了,因此线程安全。

ArrayList分析:

其主要特性:有序,可随机访问,可变长,可重复,非线程安全等。

其结构图:

其主要属性:

//默认容量
private static final int DEFAULT_CAPACITY = 10;
//空标志
private static final Object[] EMPTY_ELEMENTDATA = {};
//存放元素的数组
private transient Object[] elementData;
//元素个数
private int size;
其构造方法有(不能设置ArrayList的扩容机制):
public ArrayList(int initialCapacity) { //可指定初始容量
     super();
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
     this.elementData = new Object[initialCapacity];
}

public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA; //空数组
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
看看其主要方法add, remove:

public boolean add(E e) {
     ensureCapacityInternal(size + 1);  //扩容
     elementData[size++] = e;
     return true;
}

private void ensureCapacityInternal(int minCapacity) {
     if (elementData == EMPTY_ELEMENTDATA) {
         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
     }
     ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
     modCount++;
     // overflow-conscious code
     if (minCapacity - elementData.length > 0)
          grow(minCapacity);
}

private void grow(int minCapacity) {
     int oldCapacity = elementData.length;
     int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容为原来的3/2倍
     if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
     if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
     // minCapacity is usually close to size, so this is a win:
     elementData = Arrays.copyOf(elementData, newCapacity);
}

remove方法, 基本同上面Vector。

LinkedList分析:

其主要特性:可变长,可重复,不可随机访问,非线程安全等。

LinkedList不同于Vector,ArrayList(由数组实现),基于双链表实现:

其结构图:

其主要特性:可重复,不可随机访问,非线程安全。

其主要属性:

//长度
transient int size = 0;
//头
transient Node<E> first;
//尾
transient Node<E> last;

其将我们的元素抽象为Node类:

private static class Node<E> {
     E item; //元素对象
     Node<E> next; //后节点引用
     Node<E> prev; //前节点引用
     Node(Node<E> prev, E element, Node<E> next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
     }
 }
还是看看其主要方法, add,remove:

add方法:

public boolean add(E e) {
     linkLast(e); //接到尾上
     return true;
 }

 void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null) //空链表
          first = newNode;
    else
          l.next = newNode;
    size++;
    modCount++;
 }
remove方法, 主要由unlink方法实现:
E unlink(Node<E> x) {
   // assert x != null;
   final E element = x.item;
   final Node<E> next = x.next;
   final Node<E> prev = x.prev;

   if (prev == null) { //头节点
       first = next;
   } else {
       prev.next = next;
       x.prev = null;
   }

   if (next == null) { //尾节点
       last = prev;
   } else {
       next.prev = prev;
       x.next = null;
   }

   x.item = null;
   size--;
   modCount++;
   return element;
}

上面就讲了有关List集合的3个实现类,对于这三个类我们该如何选取,就的根据具体情况:

对于Vector和ArrayList, 需要同步时,则可用Vector, 或Collections.synchronizedList(),不需同步则用ArrayList, 对于这三种做了些性能测试:

  • Vector与SynchronizedList并发插入性能:5个线程,每个线程插入100w元素,Vector要更快。
  • ArrayList与LinkedList插入性能: 当数据量比较小时,LinkedList更快(前者由于复制操作耗时),当数据量比较大时(如>=50W), ArrayList更快(后者由于遍历操作耗时)。

不吝指正。

展开阅读全文
加载中
点击加入讨论🔥(6) 发布并加入讨论🔥
6 评论
51 收藏
0
分享
返回顶部
顶部