java - Linkedlist 与 arraylist 的比较

Question

我明白了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);

        }

    }

Answer 1

LinkedList 的插入速度并不比 ArrayList 快。 ArrayList 由数组支持，因此插入元素很简单。插入 LinkedList 需要创建一个新的 Entry 实例，速度较慢。

唯一一次向 ArrayList 插入可能会变慢，因为插入会导致 ArrayList 容量增加，这需要创建一个新数组并使用旧数组数组复制到它。