Java集合框架之ArrayList、LinkedList的区别(四)

时间:2021-06-06 19:22:22

一、List集合概括

List集合与Collection的继承关系:

Java集合框架之ArrayList、LinkedList的区别(四)


1. List是一个接口,它继承与Collection接口,代表有序的队列。

2. AbstractList是一个抽象类,它继承与AbstractCollection。AbstractList实现了List接口中除了size()、get(int location)之外的方法。

3. AbstractSequentialList是一个抽象类,它继承与AbstrctList。AbstractSequentialList实现了“链表中,根据index索引值操作链表的全部方法”。

4. ArrayList、LinkedList、Vector和Stack是List的四个实现类。

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

6. Stack是基于数组实现的。继承了Vector相关特点,同时具有“先进后出”特性。

二、ArrayList和LinkedList的区别

  1. LinkedList是基于双向链表结构实现了。是个双向链列表,也可做堆栈、队列使用。
  2. ArrayList是基于数组结构实现的。是个数组队列,可动态扩容数组的容量。
  3. ArrayList在随机访问set和get比LinkedList的效率更高,因为在LinkedList要通过遍历查询移动指针,而ArrayList只需通过index在数组直接取出即可。
  4. 在网上看了很多资料,都说LinkedList在插入和删除(add和remove)元素上,效率比ArrayList更高,因为ArrayList在插入或删除要复制并移动数组。对于添加和删除,ArrayList和LinkedList在速度上并没有谁快谁慢,这是相对的。

下面重点比较分析LinkedList和ArrayList。

  ArrayList中的随机访问、添加和删除部分源码如下

//获取index位置的元素值
public E get(int index) {
    rangeCheck(index); //首先判断index的范围是否合法

    return elementData(index);
}

//将index位置的值设为element,并返回原来的值
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

//将element添加到ArrayList的指定位置
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //将index以及index之后的数据复制到index+1的位置往后,即从index开始向后挪了一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index); 
    elementData[index] = element; //然后在index处插入element
    size++;
}

//删除ArrayList指定位置的元素
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        //向左挪一位,index位置原来的数据已经被覆盖了
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //多出来的最后一位删掉
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

 LinkedList中的随机访问、添加和删除部分源码如下:

//获得第index个节点的值
public E get(int index) {
	checkElementIndex(index);
	return node(index).item;
}

//设置第index元素的值
public E set(int index, E element) {
	checkElementIndex(index);
	Node<E> x = node(index);
	E oldVal = x.item;
	x.item = element;
	return oldVal;
}

//在index个节点之前添加新的节点
public void add(int index, E element) {
	checkPositionIndex(index);

	if (index == size)
		linkLast(element);
	else
		linkBefore(element, node(index));
}

//删除第index个节点
public E remove(int index) {
	checkElementIndex(index);
	return unlink(node(index));
}

//定位index处的节点
Node<E> node(int index) {
	// assert isElementIndex(index);
	//index<size/2时,从头开始找
	if (index < (size >> 1)) {
		Node<E> x = first;
		for (int i = 0; i < index; i++)
			x = x.next;
		return x;
	} else { //index>=size/2时,从尾开始找
		Node<E> x = last;
		for (int i = size - 1; i > index; i--)
			x = x.prev;
		return x;
	}
}

程序测试:

public class ListTest {

	private static final int COUNT=100000;//10万
	static LinkedList<Integer> linkedList = new LinkedList<Integer>();
	static ArrayList<Integer> arrayList=new ArrayList<Integer>();

	public static void main(String[] args) {
		 
		System.out.println("------插入10万数据------");
		insertData(linkedList);
		insertData(arrayList);
		System.out.println();
		System.out.println("------读取10万数据------");
		readData(linkedList);
		readData(arrayList);
		System.out.println();
		System.out.println("------删除10万数据------");
		removeData(linkedList);
		removeData(arrayList);
		
		
		
	}

	/**
	 * 插入数据,计算插入10万条所需的时间
	 */
	@SuppressWarnings("unused")
	public static void insertData(List<Integer> list) {
	
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < COUNT; i++) {
			list.add(0,i);
			
		}
		long endTime = System.currentTimeMillis();
		
		if (list instanceof LinkedList) {
			System.out.println("LinkedList插入时间:"+(endTime-startTime)+"ms");
		}
		
		if (list instanceof ArrayList) {
			System.out.println("ArrayList插入时间:"+(endTime-startTime)+"ms");
		}
		
	}
	
	/**
	 * 读取数据,计算读取10万条所需的时间
	 */
	@SuppressWarnings("unused")
	private static void readData(List<Integer> list) {
		
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < COUNT; i++) {
			list.get(i);
		}
		long endTime = System.currentTimeMillis();
		
		if (list instanceof LinkedList) {
			System.out.println("LinkedList读取时间:"+(endTime-startTime)+"ms");
		}
		
		if (list instanceof ArrayList) {
			System.out.println("ArrayList读取时间:"+(endTime-startTime)+"ms");
		}
		
	}
	
	/**
	 * 删除数据,计算删除10万条所需的时间
	 */
	@SuppressWarnings("unused")
	private static void removeData(List<Integer> list) {
		
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < COUNT; i++) {
			list.remove(0);
		}
		long endTime = System.currentTimeMillis();
		
		if (list instanceof LinkedList) {
			System.out.println("LinkedList删除时间:"+(endTime-startTime)+"ms");
		}
		
		if (list instanceof ArrayList) {
			System.out.println("ArrayList删除时间:"+(endTime-startTime)+"ms");
		}
		
	}

}

编译运行的结果:

------插入10万数据------
LinkedList插入时间:13ms
ArrayList插入时间:737ms

------读取10万数据------
LinkedList读取时间:7312ms
ArrayList读取时间:2ms

------删除10万数据------
LinkedList删除时间:7ms
ArrayList删除时间:612ms

从上面的结果可以看出:

1. ArrayList在随机访问get元素的效率明显比LinkedList高出很多,因为ArrayList只要通过index就可以直接获取元素值,而LinkedList则不同,需要通过for遍历查找,当index<size/2时,此时从集合左边向右查询,反之从右向左查询,虽然在一定程度提高了查询的效果,但相对于ArrayList还是慢了很多很多。所以在使用LinkedList时,切记一定大量进行随机访问,如果数据超大的话,可能会导致线程阻塞。

2. 从上面的结果,第一直觉得出结论就是LinkedList在添加和删除操作会比ArrayList快,其实并不然,ArrayList在添加和删除的过程中,耗时主要是System.arraycopy(……)函数所引起的,它会改变数组的索引要重新排列;而LinkedList则要通过for遍历index的所处的节点再插入或删除数据,所有一定程度很难说谁快谁慢,影响LinkedList添加操作的效率,主要看插入的位置index,同样的也可以通过程序验证:

前面测试index是0,下面修改插入的index

	/**
	 * 插入数据,计算插入10万条所需的时间
	 */
	@SuppressWarnings("unused")
	public static void insertData(List<Integer> list) {
	
		long startTime = System.currentTimeMillis();
		/**
		 * 设置临界点temp,即在temp位置插入元素
		 * 给temp设置一个默认为50000,刚好一半,接下来手动改变测试
		 */
		int temp=50000;
		for (int i = 0; i < COUNT; i++) {
			if (i>=temp) {
				list.add(temp,i);
			}else {
				list.add(0,i);
			}
			
		}
		long endTime = System.currentTimeMillis();
		
		if (list instanceof LinkedList) {
			System.out.println("LinkedList插入时间:"+(endTime-startTime)+"ms");
		}
		
		if (list instanceof ArrayList) {
			System.out.println("ArrayList插入时间:"+(endTime-startTime)+"ms");
		}
		
	}

编译结果:以中间值50000为临界点测试

temp=90000;
------插入10万数据------
LinkedList插入时间:139ms
ArrayList插入时间:574ms

temp=80000;

------插入10万数据------
LinkedList插入时间:497ms
ArrayList插入时间:435ms

temp=60000;
------插入10万数据------
LinkedList插入时间:1954ms
ArrayList插入时间:329ms


temp=50000;
------插入10万数据------
LinkedList插入时间:3027ms
ArrayList插入时间:327ms

temp=40000;
------插入10万数据------
LinkedList插入时间:4572ms
ArrayList插入时间:320ms

temp=10000;
------插入10万数据------
LinkedList插入时间:2260ms
ArrayList插入时间:536ms

temp=2000;
------插入10万数据------
LinkedList插入时间:478ms
ArrayList插入时间:699ms
 

同样的LinkedList和ArrayList在最尾部逐个添加元素测试

if (list instanceof LinkedList) {
    ((LinkedList) list).addLast(i);
 }else {
    list.add(i);
}

编译结果:

------插入10万数据------
LinkedList插入时间:8ms
ArrayList插入时间:6ms
从上面的测试结果,很难完全定义LinkedList插入效率比ArrayList高,很大程度取决插入index位置。
由于LinkedList可以实现栈、队列以及双端队列等数据结构,所以当特定需要时候,使用LinkedList;当数据量大的时候,如果只需要在靠前的部分插入或删除数据,那也可以选用LinkedList。


如果有错误之处,请留言指正 ---谢谢!!!