链接列表与数组列表的比较

list java arraylist linked-list

2022-09-04 04:24:22

我理解这是作为双链表实现的。它在添加和删除时的性能优于，但在 get 和 set 方法上更差。LinkedListArraylist

这是否意味着我应该选择插入？LinkedListArraylist

我写了一个小测试，发现插入更快。那么链表如何比？ArrayListArrayList

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

    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);

        }

    }

答案 1

LinkedList不比插入快。由数组支持，因此插入元素是微不足道的。插入到涉及创建新实例，该实例的速度较慢。ArrayListArrayListLinkedListEntry

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

答案 2

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);

        }
}