我一直是一个简单使用的人:

List<String> names = new ArrayList<>();

我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。

LinkedList何时应用于ArrayList,反之亦然?


当前回答

我知道这是一篇老帖子,但我真的不敢相信没有人提到LinkedList实现了Deque。只需查看Deque(和Queue)中的方法;如果您希望进行公平的比较,请尝试对ArrayDeque运行LinkedList,并进行功能比较。

其他回答

ArrayList扩展了AbstractList并实现了List接口。ArrayList是动态数组。可以说,它的创建基本上是为了克服数组的缺点LinkedList类扩展了AbstractSequentialList并实现了List、Deque和Queue接口。表演arraylist.get()是O(1),而linkedlist.getarraylist.add()为O(1),linkedlist.add)为0(1)arraylist.contains()为O(n),linkedlist.contans()为0(n)arraylist.next()为O(1),linkedlist.next()为0(1)arraylist.remove()是O(n),而linkedlist.remove()是0(1)在arraylistiterator.remove()是O(n),而在linkedlist迭代器.remove

这取决于您将在列表中执行更多操作。

ArrayList访问索引值更快。插入或删除对象时,情况更糟。

要了解更多信息,请阅读任何关于数组和链接列表之间区别的文章。

我在这里看到的一个测试只进行一次测试。但我注意到的是,您需要多次运行这些测试,最终它们的时间会收敛。基本上JVM需要预热。对于我的特定用例,我需要向列表中添加/删除项目,该列表将增加到大约500个项目。在我的测试中,LinkedList的发布速度更快,LinkedList约为50000 NS,ArrayList约为90000NS。。。给予或索取。请参见下面的代码。

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}

ArrayList是您想要的。LinkedList几乎总是一个(性能)bug。

为什么LinkedList很糟糕:

它使用了大量小内存对象,因此影响了整个过程的性能。许多小对象不利于缓存位置。任何索引操作都需要遍历,即具有O(n)性能。这在源代码中并不明显,导致算法O(n)比使用ArrayList时慢。获得好的表现是很棘手的。即使big-O性能与ArrayList相同,它也可能会明显变慢。在源代码中看到LinkedList很刺耳,因为它可能是错误的选择。

以下是ArrayList和LinkedList以及CopyOnWrite ArrayList中的Big-O符号:

阵列列表

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

链表

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite阵列列表

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

基于这些,您必须决定选择什么。:)