当前位置: 首页 > 知识库问答 >
问题:

Linkedlist与arraylist的比较[duplicate]

施阎宝
2023-03-14

我了解到LinkedList是作为双链表实现的,它在添加和删除上的性能比Arraylist好,但在get和set方法上的性能更差。

这是否意味着我应该选择LinkedList而不是Arraylist来插入?

我写了一个小测试,发现ArrayList插入速度更快,那么链表怎么比ArrayList快呢?

请参考下面我所做的例子。

    import java.util.Date;
    import java.util.LinkedList;
    import java.util.List;

    public class TestLinkedList {

        public static void main(String[] args) {

            long lStartTime = new Date().getTime();
            System.out.println("lStartTime:: " + lStartTime);
            List<Integer> integerList = new LinkedList<Integer>();
            for (int i = 0; i < 10000000; i++) {
                integerList.add(i);
            }

            long lEndTime = new Date().getTime();
            System.out.println("lEndTime:: " + lEndTime);

            long difference = lEndTime - lStartTime;

            System.out.println("Elapsed milliseconds: " + difference);

        }

    }

共有2个答案

史英睿
2023-03-14

Linkedlist在插入上确实更快,问题在于你的例子。在你的代码中,你总是通过追加到末尾来插入。对于ArrayList来说,这和LinkedList一样简单。你应该做的是建立一个比如说5000个项目的列表,然后开始在中间插入。这里数组变得很慢——你必须一直在插入位置后移动数组的其余部分。这就是区别所在。分析这些东西是如何工作的,不难理解为什么。下面是修改后的代码:

import java.util.Date;
    import java.util.LinkedList;
    import java.util.ArrayList;
    import java.util.List;

    public class Prob {

        public static void main(String[] args) {

            long lStartTime = new Date().getTime();
            System.out.println("lStartTime:: " + lStartTime);
            List<Integer> integerList = new LinkedList<Integer>();
            for (int i = 0; i < 5000; i++) {
                integerList.add(0, i);
            }
            for (int i = 0; i < 100000; i++) {
                integerList.add(1000, i);
            }

            long lEndTime = new Date().getTime();
            System.out.println("lEndTime:: " + lEndTime);

            long difference = lEndTime - lStartTime;

            System.out.println("Elapsed milliseconds: " + difference);

        }
}
林弘文
2023-03-14

LinkedList的插入速度不快于ArrayListArrayList由数组支持,因此插入元素非常简单。插入到链接列表需要创建一个新的条目实例,这会更慢。

插入到ArrayList唯一可能较慢的时间是当插入导致ArrayList容量增加时,这需要创建一个新数组并将旧数组复制到其中。

 类似资料:
  • 问题内容: 我了解这是作为双重链接列表实现的。它在add和remove上的性能优于,但在get和set方法上却较差。 这是否意味着我应该选择在插入? 我写了一个小测试,发现插入速度更快。那如何链表比? 请参考下面的示例。 问题答案: Linkedlist确实在插入时速度更快,问题出在您的示例中。在您的代码中,您一直都需要附加到末尾。对于ArrayList,它与LinkedList一样容易。您应该做

  • 问题内容: 我在此之前的一篇帖子中写道: 对于LinkedList 得到的是O(n) 加为O(1) 删除为O(n) Iterator.remove为O(1) 对于ArrayList 得到的是O(1) add为O(1)摊销,但O(n)为最差情况,因为必须调整数组大小并复制 删除为O(n) 因此,通过查看此内容,我得出的结论是,如果只对我的集合中的序列插入(比如说5000000个元素),它将超出类别。

  • 本文向大家介绍java中ArrayList与LinkedList对比详情,包括了java中ArrayList与LinkedList对比详情的使用技巧和注意事项,需要的朋友参考一下  ArrayList,LinkedList都是Collection接口的通用实现方式,两者采用了不用的存储策略,用来适应不同场合的需要。 实现方式   ArrayList的内部采用集合的方式存储数据 唯一需要注意的是对于

  • 本文向大家介绍Arraylist 与 LinkedList 区别?相关面试题,主要包含被问及Arraylist 与 LinkedList 区别?时的应答技巧和注意事项,需要的朋友参考一下 数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。 随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 Lin

  • 我希望了解更多关于数据结构和它们的实现(在JAVA语言中)。今天我写了一个测试来比较ADT列表的不同实现(时间比较)。具体来说,我比较了add方法,下面是我的测试: 我得到了这个结果: ArrayBased:5681 LinkedList:12830 ArrayBasedInitializedSize:858

  • 我正在做一个学校作业,我必须检查ArrayList teKoop中的某些对象是否不在ArrayList mijnGames中,问题是我一直设置这个错误代码:索引1 out of length 1 out of bounds for length 1 这里有什么明显的问题吗? 如有任何帮助,我们将不胜感激。 因此indexOutOfBound错误已修复,新问题出现:s 它一直返回给我一个空的Arra