纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

ArrayList和LinkedList对比 浅谈ArrayList和LinkedList到底谁更快

伟衙内   2021-06-10 我要评论
想了解浅谈ArrayList和LinkedList到底谁更快的相关内容吗,伟衙内在本文为您仔细讲解ArrayList和LinkedList对比的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:ArrayList和LinkedList对比,Java,ArrayList,Java,LinkedList,下面大家一起来学习吧。

一、ArrayList和LinkedList究竟谁快

在Java中应该都知道ArrayList和LinkedList,

一直以来的概念呢是

ArrayList在get(index)这个应该比LinkedList快;

LinkedList比ArrayList在add(index,element)快;

两者共同遍历呢,应该是一样快的,毕竟都要循环遍历一遍。

直到我写了一个测试类

package com.lw;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
import org.junit.Test;
 
public class TestJDKList {
	
	List<Integer> linkedList = new LinkedList<>();
	List<Integer> arrayList = new ArrayList<>();
	
	int length = 1000000;
	
	
	
	@Test
	public void testLinkedInsert(){
		
		for (int i = 0; i < length; i++) {
			linkedList.add(i);
		}
		
		long currentMi2 = System.currentTimeMillis();
		linkedList.add(length/2,3);
		long endTime2 = System.currentTimeMillis();
		System.out.println("testLinkedInsert:" + (endTime2 - currentMi2)); // 9
	}
	
	@Test
	public void testArrayInsert(){
		
		for (int i = 0; i < length; i++) {
			arrayList.add(i);
		}
		
		long currentMi2 = System.currentTimeMillis();
		arrayList.add(length/2,3);
		long endTime2 = System.currentTimeMillis();
		System.out.println("testArrayInsert:" + (endTime2 - currentMi2)); // 1
	}
	
	@Test
	public void testLinkedGet(){
		
		for (int i = 0; i < length; i++) {
			linkedList.add(i);
		}
		
		long currentMi2 = System.currentTimeMillis();
		linkedList.get(length/2);
		long endTime2 = System.currentTimeMillis();
		System.out.println("testLinkedGet:" + (endTime2 - currentMi2)); // 5
	}
	
	@Test
	public void testArrayGet(){
		
		for (int i = 0; i < length; i++) {
			arrayList.add(i);
		}
		
		long currentMi2 = System.currentTimeMillis();
		arrayList.get(length/2);
		long endTime2 = System.currentTimeMillis();
		System.out.println("testArrayGet:" + (endTime2 - currentMi2)); // 0
	}
	
	
 
	@Test
	public void testLinkedIter(){
		
		for (int i = 0; i < length; i++) {
			linkedList.add(i);
		}
		
		long currentMi2 = System.currentTimeMillis();
		for (Integer i : linkedList) {
			
		};
		long endTime2 = System.currentTimeMillis();
		System.out.println("testLinkedIter:" + (endTime2 - currentMi2)); // 26
	}
	
	@Test
	public void testArrayIter(){
		
		for (int i = 0; i < length; i++) {
			arrayList.add(i);
		}
		
		long currentMi2 = System.currentTimeMillis();
		for (Integer i : arrayList) {
			
		};
		long endTime2 = System.currentTimeMillis();
		System.out.println("testArrayIter:" + (endTime2 - currentMi2)); // 11
	}
	
	@Test
	public void testLinkedAdd() {
 
		
		long currentMi2 = System.currentTimeMillis();
		for (int i = 0; i < length; i++) {
			linkedList.add(i);
		}
		long endTime2 = System.currentTimeMillis();
		System.out.println("testLinkedAdd:" + (endTime2 - currentMi2)); // 53
	}
 
	@Test
	public void testArrayAdd(){
		long currentMi1 = System.currentTimeMillis();
		for (int i = 0; i < length; i++) {
			arrayList.add(i);
		}
		long endTime1 = System.currentTimeMillis();
		System.out.println("testArrayAdd:" + (endTime1 - currentMi1)); // 35
 
	}
}

二、结果

运行了两遍结果如下:

testLinkedInsert:7
testArrayInsert:0

testLinkedAdd:218
testArrayAdd:23

testLinkedGet:4
testArrayGet:0

testLinkedIter:14
testArrayIter:11

----------------第二遍分割线---------------------------------

testLinkedInsert:12
testArrayInsert:0

testLinkedIter:13
testArrayIter:12

testLinkedGet:3
testArrayGet:0

testLinkedAdd:119
testArrayAdd:23

颠覆三观,ArrayList竟然无论怎样都比LinkedList快??

三、循环Add

ArrayList的add源码,它是把数据放在一个数组中

transient Object[] elementData;
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

而LinkedList源码,是把数据放在Node对象中,有个前后指针。

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++;
    }
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;
        }
    }

难道是前后指针这里花时间了么?

四、指定位置Get

再看get方法,

ArrayList的get,因为是连续的内存,所以取数据很快。

public E get(int index) {
        rangeCheck(index);
 
        return elementData(index);
    }
 
 
E elementData(int index) {
        return (E) elementData[index];
    }

再看LinkedList的get,是通过指针遍历的,直到是这个index为止。

这里还有判断size,如果是size的前一半,则通过first节点往后去找,如果在后一半则通过last节点往前找,这样会更快,所以LinkedList的查找其实也不慢。

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
 
 
Node<E> node(int index) {
        // assert isElementIndex(index);
 
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

五、指定位置Add

ArrayList的add(index,element)

这里是可以扩容的,将index后半段拷贝到index+1,然后在index插入一个新的,但没想到这么快。

其实也能想到System.arraycopy是native,所以快也能理解

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++;
    }

然后是LinkedList的add(index,element)

无非是指针的指向变化而已,但没想到比上面的System.arraycopy还要慢,果然不愧为native方法。

public void add(int index, E element) {
        checkPositionIndex(index);
 
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
 
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
 
 
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++;
    }

所以项目中大部分用ArrayList也就是可以理解。

不过ArrayList是连续的内存空间,在内存空间很紧张情况下,LinkedList内存利用率更高。


相关文章

猜您喜欢

  • springboot opencv人脸识别 springboot集成opencv实现人脸识别功能的详细步骤

    想了解springboot集成opencv实现人脸识别功能的详细步骤的相关内容吗,御剑长歌在本文为您仔细讲解springboot opencv人脸识别的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:springboot,opencv人脸识别,opencv人脸识别,下面大家一起来学习吧。..
  • TensorFlow2识别验证码 教你使用TensorFlow2识别验证码

    想了解教你使用TensorFlow2识别验证码的相关内容吗,刘润森!在本文为您仔细讲解TensorFlow2识别验证码的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:TensorFlow2,识别验证码,TensorFlow2,验证码,下面大家一起来学习吧。..

网友评论

Copyright 2020 www.9aisf.com 【就爱软件站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式