为何JavaScript中链表插入实测比数组慢3倍？

我们都知道，链表找到插入位置后的操作时间复杂度为O(1)，而数组插入的时间复杂度为O(n)（最坏情况插入头部时为O(n)，插入尾部时为O(1)）。但在VS Code中测试后发现，即使是在对应位置插入元素，链表插入的速度居然比数组慢3倍，这是为什么？

测试代码与场景 #

链表实现与测试 #

class Linkedlist{
    constructor(){
        this.head = null;
        this.size = 0;
    }
    add(d){
        this.head = new Node(d, this.head);
        ++this.size;
    }
    displace(){
        let d = this.head;
        this.head = d.next;
        --this.size;
        return d.data;
    }
    place(d){
        if(this.head){
            if((this.head).data >= 14)
                this.add(d);
            else{
                let pre = this.head;
                let cur = pre.next;
                while(cur && (cur.data<14)){
                    pre = cur;
                    cur = cur.next;
                }
                pre.next = new Node(d,cur);
                ++this.size;
            }
        }else
            this.add(d);
    }
}

class Node{
    constructor(data, next=null){
        this.data = data;
        this.next = next;
    }
}

let A = new Linkedlist();
A.add(29);
A.add(28);
A.add(27);
A.add(26);
A.add(25);
A.add(24);
A.add(23);
A.add(22);
A.add(21);
A.add(20);
A.add(19);
A.add(18);
A.add(17);
A.add(16);
A.add(15);
A.add(14);
A.add(13);
A.add(12);
A.add(11);
A.add(10);
const start = performance.now();
A.place(13.5);
const end = performance.now();
console.log(end-start);

测试逻辑：先在链表头部依次添加元素，最终链表顺序为10→11→12→13→14→…→29，place函数遍历链表找到第一个值≥14的节点，在其前插入13.5。测试显示链表插入耗时约0.02ms。

数组实现与测试 #

let A = [10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29];
let j;
const start = performance.now();
for(j=0; j<A.length; j++){
    if(A[j]>=14)
        break;
}
A.splice(j,0,13.5);
const end = performance.now();
console.log(end-start);

测试逻辑：遍历数组找到第一个值≥14的元素位置，用splice插入13.5。测试显示数组插入耗时约0.006ms。

核心原因分析 #

1. 时间复杂度是渐近复杂度，不代表小数据量下的表现 #

时间复杂度描述的是数据量趋近于无穷大时的性能趋势，当数据量极小时（这里仅需遍历4个元素/节点），复杂度中的常数项、底层实现的额外开销会成为性能主导因素。

2. JavaScript数组的底层优化远超预期 #

JS数组并非传统静态数组，而是动态扩容的连续内存容器，现代JS引擎（如V8）对数组操作做了大量优化：

• splice移动少量元素时，底层是连续内存的批量拷贝，CPU缓存命中率极高；
• 数组元素存储在连续内存块中，遍历和访问速度远快于分散的链表节点。

3. 链表的内存分散性与对象开销 #

• 内存不连续：每个Node是独立的JS对象，分散在堆内存的不同位置，CPU缓存无法有效利用，遍历和访问时会频繁触发缓存未命中，速度大幅下降；
• 对象创建开销：插入时需要新建Node对象，涉及内存分配、构造函数调用等额外步骤，这些开销在小数据量下占比极高。

4. 两者的遍历开销实际不对等 #

虽然两者都需要遍历4个元素/节点找到插入位置，但数组是连续内存访问，链表是跳转到不同内存地址，前者的遍历效率远高于后者，进一步拉开了性能差距。

内容的提问来源于stack exchange，提问作者Agniv Debsikdar