java - 为什么 StringBuilder append() 比 LinkedList add() 快？

Question

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

如您所知，Java 的 StringBuilder append() 操作类似于数组列表 add() 操作(当超出容量时调整值数组的大小)。

我意识到在插入 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

我还用 ListIterator.add() 更改了 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 实例时，这可能会影响时间。