为什么StringBuilder append()比LinkedList add()快?

Question

我正在尝试基于LinkedList结构创建新的StringBuilder。

如你所知，Java的StringBuilder的append()操作类似于数组列表add()操作(当容量超过value-array时调整大小)。

我意识到当插入String时，StringBuilder.append()比LinkedList.add()快

(*这是list的一个纯添加过程)。

下面是代码片段:

        List<String> linkedList = new LinkedList<>();
        StringBuilder stringBuilder = new StringBuilder();
        int loopCount = 5_000_000;
        long s, e;
        s = System.currentTimeMillis();
        for (int i = 0; i < loopCount; i++) {
            linkedList.add(UUID.randomUUID().toString() + "n");
        }
        e = System.currentTimeMillis();
        System.out.println("LinkedList: "+(e - s));
        s = System.currentTimeMillis();
        for (int i = 0; i < loopCount; i++) {
            stringBuilder.append(UUID.randomUUID().toString() + "n");
        }
        e = System.currentTimeMillis();
        System.out.println("String Builder: " + (e - s));

这些是基准测试结果。(按500万次插入计算)

StringBuilder: 13892 millisec
LinkedList:    19561 millisec

我也改变了add()方法与ListIterator.add()，但我没有改变任何东西。

这是我的问题:我怎样才能使列表add()方法变得比StringBuilder.append()更快?

Answer 1

当你添加一个项目到LinkedList时，新的Node对象被创建

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

Node对象包含对下一个节点和上一个节点的引用。

StringBuilder通过本地System.arraycopy将String字符追加到底层数组，因此不会创建任何实例。

当创建多个Node实例时，这可能会影响时间。