Java集合（六）List概括,总结-白红宇

Java集合（六）List概括,总结

阅读量：6298 次

发布时间：2019-06-22

本文共 7779 字，大约阅读时间需要 25 分钟。

第1部分 List概括

先回顾一下List的框架图

Java集合（八）LinkedList、ArrayList和Vector等使用场景和性能分析总结_www.fengfly.com

List 是一个接口，它继承于Collection的接口。它代表着有序的队列。

AbstractList 是一个抽象类，它继承于AbstractCollection。AbstractList实现List接口中除size()、get(int location)之外的函数。

AbstractSequentialList 是一个抽象类，它继承于AbstractList。AbstractSequentialList 实现了“链表中，根据index索引值操作链表的全部函数”。

ArrayList, LinkedList, ~~Vector, Stack~~是List的4个实现类。

ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。

LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率低。

~~Vector~~ 是~~矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现~~~~。但是ArrayList是非线程安全的，而Vector是线程安全的。~~

~~Stack~~ 是~~栈，它继承于Vector~~~~。它的特性是：先进后出(FILO, First In Last Out)。~~

http://my.oschina.net/zhaoqian/blog/348843 参考此篇.了解为什么不使用Vector和Stack.

第2部分 List使用场景

单线程环境下

(01) 对于需要快速插入，删除元素，应该使用LinkedList。

(02) 对于需要快速随机访问元素，应该使用ArrayList。

测试DEMO

package org.credo.jdk.util;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Stack;import java.util.Vector;public class ListCompareTest{	private static final int COUNT = 100000;	private static LinkedList linkedList = new LinkedList();	private static ArrayList arrayList = new ArrayList();	private static Vector vector = new Vector();	private static Stack stack = new Stack();	public static void main(String[] args)	{		// 换行符		System.out.println();		// 插入		insertByPosition(stack);		insertByPosition(vector);		insertByPosition(linkedList);		insertByPosition(arrayList);		// 换行符		System.out.println();		// 随机读取		readByPosition(stack);		readByPosition(vector);		readByPosition(linkedList);		readByPosition(arrayList);		// 换行符		System.out.println();		// 删除		deleteByPosition(stack);		deleteByPosition(vector);		deleteByPosition(linkedList);		deleteByPosition(arrayList);	}	// 获取list的名称	private static String getListName(List list)	{		if (list instanceof LinkedList)		{			return "LinkedList";		} else if (list instanceof ArrayList)		{			return "ArrayList";		} else if (list instanceof Stack)		{			return "Stack";		} else if (list instanceof Vector)		{			return "Vector";		} else		{			return "List";		}	}	// 向list的指定位置插入COUNT个元素，并统计时间	private static void insertByPosition(List list)	{		long startTime = System.currentTimeMillis();		// 向list的位置0插入COUNT个数		for (int i = 0; i < COUNT; i++)			list.add(0, i);		long endTime = System.currentTimeMillis();		long interval = endTime - startTime;		System.out.println(getListName(list) + " : insert " + COUNT + " elements into the 1st position use time："				+ interval + " ms");	}	// 从list的指定位置删除COUNT个元素，并统计时间	private static void deleteByPosition(List list)	{		long startTime = System.currentTimeMillis();		// 删除list第一个位置元素		for (int i = 0; i < COUNT; i++)			list.remove(0);		long endTime = System.currentTimeMillis();		long interval = endTime - startTime;		System.out.println(getListName(list) + " : delete " + COUNT + " elements from the 1st position use time："				+ interval + " ms");	}	// 根据position，不断从list中读取元素，并统计时间	private static void readByPosition(List list)	{		long startTime = System.currentTimeMillis();		// 读取list元素		for (int i = 0; i < COUNT; i++)			list.get(i);		long endTime = System.currentTimeMillis();		long interval = endTime - startTime;		System.out.println(getListName(list) + " : read " + COUNT + " elements by position use time：" + interval				+ " ms");	}}

输出:

Stack : insert 100000 elements into the 1st position use time：987 msVector : insert 100000 elements into the 1st position use time：940 msLinkedList : insert 100000 elements into the 1st position use time：13 msArrayList : insert 100000 elements into the 1st position use time：947 msStack : read 100000 elements by position use time：6 msVector : read 100000 elements by position use time：5 msLinkedList : read 100000 elements by position use time：5655 msArrayList : read 100000 elements by position use time：2 msStack : delete 100000 elements from the 1st position use time：1625 msVector : delete 100000 elements from the 1st position use time：959 msLinkedList : delete 100000 elements from the 1st position use time：5 msArrayList : delete 100000 elements from the 1st position use time：1356 ms

从上可以发现,insert操作和delete操作,LinkedList是完胜的.而基于数组的arrayList,~~vector,stack~~都是在read上完胜.

第3部分 LinkedList和ArrayList性能差异分析

下面我们看看为什么LinkedList中插入元素很快，而ArrayList中插入元素很慢！

LinkedList.java中向指定位置插入元素的代码如下：

// 在index前添加节点，且节点的值为element  public void add(int index, E element) {      addBefore(element, (index==size ? header : entry(index)));  }   // 获取双向链表中指定位置的节点  private Entry
    
      entry(int index) {      if (index < 0 || index >= size)          throw new IndexOutOfBoundsException("Index: "+index+                                              ", Size: "+size);      Entry
     
       e = header;      // 获取index处的节点。      // 若index < 双向链表长度的1/2,则从前向后查找;      // 否则，从后向前查找。      if (index < (size >> 1)) {          for (int i = 0; i <= index; i++)              e = e.next;      } else {          for (int i = size; i > index; i--)              e = e.previous;      }      return e;  }   // 将节点(节点数据是e)添加到entry节点之前。  private Entry
      
        addBefore(E e, Entry
       
         entry) {      // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e      Entry
        
          newEntry = new Entry
         
          (e, entry, entry.previous); // 插入newEntry到链表中 newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }

从中，我们可以看出：通过add(int index, E element)向LinkedList插入元素时。先是在双向链表中找到要插入节点的位置index；找到之后，再插入一个新节点。

双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。

接着，我们看看ArrayList.java中向指定位置插入元素的代码。如下：

// 将e添加到ArrayList的指定位置  public void add(int index, E element) {      if (index > size || index < 0)          throw new IndexOutOfBoundsException(          "Index: "+index+", Size: "+size);       ensureCapacity(size+1);  // Increments modCount!!      System.arraycopy(elementData, index, elementData, index + 1,           size - index);      elementData[index] = element;      size++;  }

ensureCapacity(size+1) 的作用是“确认ArrayList的容量，若容量不够，则增加容量。”

真正耗时的操作是 System.arraycopy(elementData, index, elementData, index + 1, size - index);

Sun JDK包的java/lang/System.java中的arraycopy()声明如下

public

static

native

void

arraycopy(Object src,

int

srcPos, Object dest,

int

destPos,

int

length);

arraycopy()是个JNI函数，它是在JVM中实现的。sunJDK中看不到源码，不过可以在OpenJDK包中看到的源码。网上有对arraycopy()的分析说明，请参考：

实际上，我们只需要了解： System.arraycopy(elementData, index, elementData, index + 1, size - index); 会移动index之后所有元素即可。这就意味着，ArrayList的add(int index, E element)函数，会引起index之后所有元素的改变！

通过上面的分析，我们就能理解为什么LinkedList中插入元素很快，而ArrayList中插入元素很慢。

“删除元素”与“插入元素”的原理类似，这里就不再过多说明。

接下来，我们看看 “为什么LinkedList中随机访问很慢，而ArrayList中随机访问很快”。

先看看LinkedList随机访问的代码

// 返回LinkedList指定位置的元素  public E get(int index) {      return entry(index).element;  }   // 获取双向链表中指定位置的节点  private Entry
    
      entry(int index) {      if (index < 0 || index >= size)          throw new IndexOutOfBoundsException("Index: "+index+                                              ", Size: "+size);      Entry
     
       e = header;      // 获取index处的节点。      // 若index < 双向链表长度的1/2,则从前先后查找;      // 否则，从后向前查找。      if (index < (size >> 1)) {          for (int i = 0; i <= index; i++)              e = e.next;      } else {          for (int i = size; i > index; i--)              e = e.previous;      }      return e;  }

从中，我们可以看出：通过get(int index)获取LinkedList第index个元素时。先是在双向链表中找到要index位置的元素；找到之后再返回。

双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。

下面看看ArrayList随机访问的代码

// 获取index位置的元素值  public E get(int index) {      RangeCheck(index);       return (E) elementData[index];  }   private void RangeCheck(int index) {      if (index >= size)          throw new IndexOutOfBoundsException(          "Index: "+index+", Size: "+size);  }

从中，我们可以看出：通过

get(int index)

获取ArrayList第index个元素时。直接返回数组中index位置的元素，而不需要像LinkedList一样进行查找。