List接口(主要ArrayList 和LinkedList以及Vector区别(转))

实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。

(1)以下两篇是关于ArrayList和LinkedList的文章，本人觉得描述的非常到位，在此分享下，顺便也方便自己在此翻阅。

            1.ArrayList:http://286.iteye.com/blog/2178518

            2.LinkedList:http://286.iteye.com/blog/2181299

 

两者大致区别：

            1. pengcqu.iteye.com/blog/502676

 

总结： 

            1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 

            2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。 
            3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。 

但：

      ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下： 
            1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，个                     开销是统一的，分配一个内部Entry对象。

            2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

            3．LinkedList不支持高效的随机元素访问。

            4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

     可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中            的元素时,就应该使用LinkedList了。

 

 

应用场合：

        1.ArrayList底层的实现是数组，所以用下标访问的速度比较快，但是插入和删除元素，会有移动元素的开销，所以速度比LinkedList差。

        2.LikedList底层是链表实现的，所以插入和删除元素时间复杂度较LinkedList好，但是随即访问需要遍历元素，所以效率比ArrayList差。

        3.一般情况下，用ArrayList就可以了，如果涉及到频繁的插入和删除元素，这个时候考虑使用LinkedList，另外Java里面的Queue和Stack也是依赖LinkedList实现的。

       4.LinkedList内数据根本没有固定的容器存储。而是通过对象关联引用，一层一层深入下去的。简单的说，就是保存在一个对象的无限引用中，引用链有多深取决数据量的大小。 具体数据结构如下：

Entry<E> {
E element;
Entry<E> previous;
Entry<E> next;
}
所以无论是查找还是插入，删除，都要从第一个元数据开始找。这样效率自然就很低。

 

(2)：Vector

        Vector几乎和ArrayList相等，主要的区别在于Vector是同步的。正因为此，Vector比ArrayList的开销更大。通常大部分程序员都使用ArrayList，他们可以自己写代码进行同步。

     

    这里写了一个demo：    

 

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;
import java.util.concurrent.CountDownLatch;


public class ThreadAccessArrayList extends Thread {
	
	private List list;
	
	CountDownLatch countDownLatch;
	
	public ThreadAccessArrayList(List list,CountDownLatch countDownLatch){
		this.list = list;
		this.countDownLatch = countDownLatch;
	}
	
	public void run(){
		for (int i = 0; i < 2000; i++) {
			list.add("lopez" + i);
		}
		try {
			countDownLatch.countDown();//每条线程减一
		} catch (Exception e) {
			System.out.println(0000);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		CountDownLatch countDownLatch = new CountDownLatch(20);//计数器
		List list = new ArrayList();//使用ArrayList输出是：Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: 452	                         
		//List list = new Vector();//使用Vector时输出是：list的size是：40000
		ThreadAccessArrayList threadAccessArrayList = new ThreadAccessArrayList(list,countDownLatch);
		for (int i = 0; i < 20; i++) {
			new Thread(threadAccessArrayList).start();
		}
		try {
			countDownLatch.await();//，任何调用这个对象上的await()方法都会阻塞，直到这个计数器的计数值被其他的线程减为0为止。
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		System.out.println("list的size是：" + list.size());
	}

}

   以上可以看出ArrayList在多线程访问时有可能出错的，而vector则不会，所以说vector是线程安全（同步加锁）的，但开销更大。

 

  解决方案1：用java5.0新加入的ConcurrentLinkedQueue、ConcurrentHashMap、CopyOnWriteArrayList 和 CopyOnWriteArraySet . 

  用CopyOnWriteArrayList取代ArrayList:

                     缺点：性能低，以上例子，同等情况之下，用vector所需时间为：15ns；而用CopyOnWriteArrayList却用3723ns。

 

  解决方案2：使用ArrayList/HashMap和同步包装器:List list = Collections.synchronizedList(new ArrayList());;

                     耗时：15ns（推荐）在大数据量情况之下比Vector快

 遍历要注意：

synchronized (list) {
			for (String str : list) {
				System.out.println("遍历list为：" + str);
			}
		}

 

  解决方案3：使用Vector